|
|
| |
Hybrid MIP/CP solving
The examples in this directory are explained in the whitepaper
Hybrid MIP/CP solving with Xpress Optimizer and Xpress Kalis. The MIP models are solved with Xpress Optimizer; the CP models can only be run if Xpress Kalis has been installed.
|
| Hybrid MIP-CP problem solving: sequential solving: Solving a sequence of CP subproblems, in-memory data exchange
|
| |
|
| Type: |
Project scheduling |
| Rating: |
3 (intermediate) |
| Description: |
The idea of this example is to use a Constraint Programming
(CP) model to preprocess
data for an LP problem. The constraint propagation performed by the CP solver tightens the bounds on certain decision
variables.
- solving a sequence of CP subproblems
- data exchange between several models via shared memory
|
| File(s): |
b1stadium_ka.mos, b1stadium_main.mos, b1stadium_sub.mos (submodel) |
| Data file(s): |
b1stadium.dat |
|
|
| Hybrid MIP-CP problem solving: concurrent solving: Parallel and sequential solving of subproblems
|
| |
|
| Type: |
Scheduling with machine assignment |
| Rating: |
5 (difficult) |
| 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 master 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
master 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
|
| File(s): |
sched_main.mos, sched_sub.mos (submodel), sched_mainp.mos, sched_subp.mos (submodel), sched_mainpd.mos, sched_subpd.mos (submodel), sched_mainm.mos, sched_subm.mos (submodel), sched_mainmp.mos, sched_submp.mos (submodel), sched_mainmpd.mos, sched_submpd.mos (submodel), sched_singlem.mos, sched_singlema.mos, sched_singlemg.mos |
| Data file(s): |
sched_3_12.dat, sched_4_16.dat, sched_4_20.dat |
|
|
| Constructing and loading MIP start solutions for the traveling salesman problem (TSP): CP target values, MIP start solution, MIP callbacks
|
| |
|
| Type: |
Traveling salesman problem |
| Rating: |
5 (difficult) |
| Description: |
This example shows how to construct and load solutions for the MIP branch-and-bound search.
- Model f5touroptcbrandom.mos: several heuristic start solutions are loaded into a MIP model for solving symmetric TSP via subtour
elimination constraints that are added during the MIP Branch-and-bound search.
- Model f5tour3.mos: a CP model generates a start solution
that is loaded into the Optimizer before the MIP Branch-and-bound search. With the model parameter ALG set to 2 the
CP search uses the (rounded) solution values of the LP relaxation as initial target values for its search.
- Model f5tour4.mos: a CP model is run at the
nodes of the Branch-and-bound tree using the current
LP relaxation solution as input. If a solution is found,
it is loaded into the Optimizer for
exploitation by the MIP heuristics.
|
| File(s): |
f5touroptcbrandom.mos, f5tour3.mos, f5tour4.mos |
| Data file(s): |
gr96.dat, st70.dat, gr120.dat |
|
|
|
|
|