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
;

Book Example: transp

Capacity expansion of power generation