FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Hybrid MIP-CP problem solving: concurrent solving

Description
The problem of scheduling a given set of jobs on a set of machines where durations and cost depend on the choice of the resource may be broken down into several subproblems, machine assignment and single-machine sequencing. The main problem (machine assignment) is solved as a MIP problem and the sequencing subproblems solved at the nodes of the branch-and-bound search generate new constraints that are added to the main problem using the cut manager functionality of Xpress Optimizer. Several implementations of this decomposition approach are available, either using a hybrid MIP-CP formulation or a second MIP model for solving the subproblems. The solving of the subproblems may be executed sequentially or in parallel.
  • Solving subproblems sequentially as CP problems (sched_main.mos, sched_sub.mos)
  • Solving subproblems in parallel as CP problems (sched_mainp.mos, sched_subp.mos)
  • Distributed parallel solving of CP subproblems (sched_mainpd.mos, sched_subpd.mos)
  • Solving subproblems sequentially as MIP problems (sched_mainm.mos, sched_subm.mos)
  • Solving subproblems in parallel as MIP problems (sched_mainmp.mos, sched_submp.mos)
  • Distributed parallel solving of MIP subproblems (sched_mainmpd.mos, sched_submpd.mos)
With MIP subproblems, it is also possible to implement the sequential version of the decomposition algorithm within a single Mosel model using several 'mpproblem':
  • Solving subproblems sequentially as MIP problems within a single model

    basic version: sched_singlem.mos,

    subproblem decision variables declared globally: sched_singlemg.mos

    subproblem, subproblem decision variables and constraints declared globally: sched_singlema.mos
Further explanation of this example: Xpress Whitepaper 'Hybrid MIP/CP solving', Section 'Combining CP and MIP'.


Source Files

Data Files





sched_3_12.dat

! Data file for `sched_*.mos'
        
NP: [12]
NM: [3]

!      1  2  3  4  5  6  7  8  9 10 11 12 
REL: [ 2  4  5  7  9  0  3  6 11  2  3  4 ]

DUE: [32 33 36 37 39 34 30 26 36 38 31 22 ]

COST: [12  6  7 
       13  6 10 
       10  4  6 
        8  4  5 
       12  6  7 
       10  5  6 
        7  4  5 
        9  5  5 
       10  5  7 
        8  4  5 
       15  8  9 
       13  7  7 
       ]
       
DUR:  [10 14 13  
        7  9  8  
       11 17 15  
        6  9 12  
        4  6 10  
        2  3  4  
       10 15 16  
        8 11 12  
       10 14 13  
        8 11 14  
        9 12 16  
        3  5  6  
        ]

Back to examples browserPrevious exampleNext example