Detecting Infeasibility and Generating Cuts for MIP using CP
作者： Alexander Bockmayr , Nicolai Pisaruk , None
DOI:
关键词:
摘要: We study a hybrid MIP/CP solution approach in which CP is used for detecting infeasibilities and generating cuts within branch-and-cut algorithm MIP. Our framework applies to MIP problems augmented by monotone constraints that can be handled CP. illustrate our on generic multiple machine scheduling problem, compare it other algorithms.
参考文章(9)
Filippo Focacci, Andrea Lodi, Michela Milano, Cutting Planes in Constraint Programming: A Hybrid Approach principles and practice of constraint programming. pp. 187- 201 ,(2000) , 10.1007/3-540-45349-0_15
Greger Ottosson, Erlendur S. Thorsteinsson, John N. Hooker, Mixed Global Constraints and Inference in Hybrid CLP–IP Solvers Annals of Mathematics and Artificial Intelligence. ,vol. 34, pp. 271- 290 ,(2002) , 10.1023/A:1014440424150
Philippe Refalo, Linear Formulation of Constraint Programming Models and Hybrid Solvers principles and practice of constraint programming. pp. 369- 383 ,(2000) , 10.1007/3-540-45349-0_27
N Beldiceanu, E Contejean, Introducing global constraints in CHIP Mathematical and Computer Modelling. ,vol. 20, pp. 97- 123 ,(1994) , 10.1016/0895-7177(94)90127-9
Abderrahmane Aggoun, Nicolas Beldiceanu, Extending chip in order to solve complex scheduling and placement problems Mathematical and Computer Modelling. ,vol. 17, pp. 57- 73 ,(1993) , 10.1016/0895-7177(93)90068-A
Vipul Jain, Ignacio E. Grossmann, Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems Informs Journal on Computing. ,vol. 13, pp. 258- 276 ,(2001) , 10.1287/IJOC.13.4.258.9733
Alexander Bockmayr, Thomas Kasper, Branch and Infer: a Unifying Framework for Integer and Finite Domain Constraint Programming Informs Journal on Computing. ,vol. 10, pp. 287- 300 ,(1998) , 10.1287/IJOC.10.3.287
Greger Ottosson, Erlendur S. Thorsteinsson, John N. Hooker, Hak-Jin Kim, On integrating constraint propagation and linear programming for combinatorial optimization national conference on artificial intelligence. pp. 136- 141 ,(1999)
L. A. Wolsey, G. L. Nemhauser, Integer programming ,(1972)