CP-style scheduling model with the numberof operator, solved by a MIP solver#
Description: Scheduling model with the Constraint Programming numberof operator, solved with a MIP solver. New MIP solver drivers based on the MP library enable CP-style modeling.
Tags: ampl-only, constraint-programming
Notebook author: Gleb Belov <gleb@ampl.com>
Model author: AMPL logic programming examples
# Install dependencies
%pip install -q amplpy
# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["coin", "highs"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register magics
Scheduling model with the numberof operator#
We create a MIP model for a scheduling problem. Then we express the model with the syntax of the AMPL Logic and Constraint Programming extensions and use a MIP solver driver with automatic CP-to-MIP transformation.
The problem is to assign n jobs to n machines, so that each machine’s capacity is obeyed, and minimizing total cost. We formulate a parameteric model, and provide data to create a model instance. The parameters are as follows:
%%ampl_eval
param n integer > 0;
set JOBS := 1..n;
set MACHINES := 1..n;
param cap {MACHINES} integer >= 0;
param cost {JOBS,MACHINES} > 0;
For a MIP formulation we introduce n * n binary variables:
%%ampl_eval
var Assign {JOBS,MACHINES} binary;
The first set of constraints asks that each job is assigned to some machine:
%%ampl_eval
subj to OneMachinePerJob {j in JOBS}:
sum {k in MACHINES} Assign[j,k] = 1;
The second set of constraints obeys the machine capacity:
%%ampl_eval
subj to CapacityOfMachine {k in MACHINES}:
sum {j in JOBS} Assign[j,k] <= cap[k];
Objective function:
%%ampl_eval
minimize TotalCost:
sum {j in JOBS, k in MACHINES} cost[j,k] * Assign[j,k];
We need data for the model parameters:
%%ampl_eval
data;
param n := 3;
param cost:
1 2 3 :=
1 1 3 3
2 2 3 3
3 3 3 2;
param cap :=
1 2
2 3
3 1;
Solving with a MIP solver:
%%ampl_eval
option solver highs;
option highs_options 'outlev=1';
solve;
option display_1col 5; # To display a matrix
display Assign;
HiGHS 1.2.2: tech:outlev=1
Running HiGHS 1.2.2 [date: 2022-09-28, git hash: 9c7b2cf27]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Presolving model
5 rows, 9 cols, 15 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve: Optimal
Solving report
Status Optimal
Primal bound 5
Dual bound 5
Gap 0% (tolerance: 0.01%)
Solution status feasible
5 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 0
LP iterations 0 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
HiGHS 1.2.2: optimal solution; objective 5
0 branching nodes
Assign [*,*]
: 1 2 3 :=
1 1 0 0
2 1 0 0
3 0 0 1
;
Now we enter a CP-style model with the same parameters.
%%ampl_eval
reset; ## Clear model and data
param n integer > 0;
set JOBS := 1..n;
set MACHINES := 1..n;
param cap {MACHINES} integer >= 0;
param cost {JOBS,MACHINES} > 0;
The variables denote the chosen machine for each job:
%%ampl_eval
var MachineForJob {JOBS} integer >= 1, <= n;
The single set of constraints obeys for the machine capacity:
%%ampl_eval
subj to CapacityOfMachine {k in MACHINES}:
numberof k in ({j in JOBS} MachineForJob[j]) <= cap[k];
The objective function is formulated using the new MachineForJob variables:
%%ampl_eval
minimize TotalCost:
sum {j in JOBS, k in MACHINES}
if MachineForJob[j] = k then cost[j,k];
We need to re-enter the parameters:
%%ampl_eval
data;
param n := 3;
param cost:
1 2 3 :=
1 1 3 3
2 2 3 3
3 3 3 2;
param cap :=
1 2
2 3
3 1;
Solving with a MIP solver again:
%%ampl_eval
solve;
display MachineForJob;
HiGHS 1.2.2: tech:outlev=1
Running HiGHS 1.2.2 [date: 2022-09-28, git hash: 9c7b2cf27]
Copyright (c) 2022 ERGO-Code under MIT licence terms
Presolving model
8 rows, 14 cols, 29 nonzeros
8 rows, 14 cols, 26 nonzeros
Objective function is integral with scale 1
Solving MIP model with:
8 rows
14 cols (10 binary, 4 integer, 0 implied int., 0 continuous)
26 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s
T 0 0 0 0.00% 0 5 100.00% 0 0 0 6 0.0s
Solving report
Status Optimal
Primal bound 5
Dual bound 5
Gap 0% (tolerance: 0.01%)
Solution status feasible
5 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 6 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
HiGHS 1.2.2: optimal solution; objective 5
1 branching nodes
MachineForJob [*] :=
1 1
2 1
3 3
;