Hybrid MIP/CP solving

www.fico.com/en/FIResourcesLibrary/Xpress_hybridmpcp.pdf

CP model

start: array(TASKS) of cpvar 

if not cp_post(Prec(i,j)) then

send(EVENT_FAILED, 0)

-- propagate on only one constraint

initializations to "raw:"

  lbstart as "shmem:lbstart"

MIP model

initializations from "raw:"

  lbstart as "shmem:lbstart"

============================================

MASTER model

procedure products_on_machine

if getsol(use(p,m))>0.5 then  ProdMach + ={p}

function generate_cut_machine

if not solve_CP_problem(m,ProdMach,1) then

Cut := sum(p in ProdMach) use(p,m) - (size-1)

addcut(1, CT_LEQ, cut)

procedure setup_cutmanager

setcallback(XPRS_CB_CM, "generate_cuts") ! Define the cut manager callback

setcallback(XPRS_CB_UIS, "print_solution")! Define the integer solution cb.

generate_cuts calls generate_cut_machine

Bibliography

[BP03] A. Bockmayr and N. Pisaruk. Detecting Infeasibility and Generating Cuts for MIP Using CP. In Proceedings of
CP-AI-OR 2003, pages 24—34, Montreal, 2003.
[JG01] V. Jain and I.E. Grossmann. Algorithms for hybrid MILP/CLP models for a class of optimization problems.
INFORMS J. Computing, 13(4):258—276, 2001.
[Sad04] R. Sadykov. A Hybrid Branch-and-Cut Algorithm for the One-Machine Scheduling Problem. In J.C. Régin and
M. Rueher, editors, Integration of AI and OR Techniques in Constraint Programming for Combinatorial
Optimization Problems, CPAIOR 2004, pages 409—414, Berlin, 2004. Springer.
[Tim02] C. Timpe. Solving planning and scheduling problems with combined integer and constraint programming.
ORSpectrum, 24(4):431—448, 2002.