Containers scheduling#
Description: Scheduling model for harbor operations. It is a problem with dependences between containers, which should be dispatch the fastest possible. We are using the MP solver interfaces to model a complex system using techniques from Constraint Programming, such as indicator constraints, and logical or and forall operators. After the model is written, a couple instances are presented and Highs/Gurobi MIP solvers are used to tackle the problem.
Tags: amplpy, scheduling, industry, mip, constraint-programming, mp
Notebook author: Marcos Dominguez Velad <marcos@ampl.com>
# Install dependencies
%pip install -q amplpy
# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["highs", "gurobi"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register magics
Containers scheduling#
The harbor wants to dispath the most containers possible, so they can be shipped soon.
The container scheduling problem is a general scheduling problem where we want to move some containers (tasks) with some cranes (the agents). However, containers are dependent between themselves, as they are grouped in stacks. Then, we can’t dispatch a container until we have dispatched every container above it.
There are work periods / shifts in which machines can work.
Multiple stacks of containers
Different cranes
Model#
Sets and parameters#
Set of containers \(C\), each container is descripted by 2 coordinates: \((i,c)\). \(i\) is the stack of the container, and \(c\) the order inside the stack. Blocks/stacks of containers are independent, but 2 machines can be working on the same stack during a period of time.
Set of periods of time \(T\). These periods are assume to be equal.
Set of machines \(M\). Each machine has a work capacity to move the containers.
To dispatch a container, we have to work at least the move cost of a container.
Variables#
\(c\_moving_{m,i,c,t}\): binary variable equals 1 if machine \(m\) is working on container \((i,c)\) in period \(t\), 0 otherwise.
\(c\_end_{i,c,t}\): binary variable equals 1 if the container \((i,c)\) is already dispatched in period \(t\), 0 otherwise. If we finish a container in time \(t\), then \(c\_end\) should be 1, although it wasn’t finished at the beginning of the time period.
\(c\_progress_{m,i,c,t}\): continuous \(\geq 0\) variable that saves the amount of work we did on container \((i,c)\) in period \(t\) with machine \(m\).
The rest of the model are constraints that give meaning and bounds to these variables. We are using some Constraint Programming operators to write the model efficiently.
Constraints#
Maximum progress of container \((i,c)\):
\[
\sum \limits_{m \in M, t \in T} c\_progress_{m,i,c,t} \leq move\_cost_{i,c}
\]
in ampl:
subject to progress_limit_container{(i,c) in C}:
sum{m in M, t in T} c_progress[m,i,c,t] <= move_cost[i,c];
Maximum work of machine \(m\) in time \(t\):
\[
\sum \limits_{(i,c) \in C} c\_progress_{m,i,c,t} \leq work\_cap_m
\]
in ampl:
subject to progress_limit{m in M, t in T}:
sum{(i,c) in C} c_progress[m,i,c,t] <= work_cap[m];
Bonds between variables…
Bond between move and progress:
\[
c\_mov_{m,i,c,t} = 1 \iff c\_progress_{m,i,c,t} > 0
\]
in ampl:
subject to active_work{m in M, (i,c) in C, t in T}:
c_moving[m,i,c,t] = 1 <==> c_progress[m,i,c,t] > 0;
(logical constraints are linearize through the MP solver interfaces)
Bond between end a container and progress:
\[
c\_end_{i,c,t} = 1 \iff \sum \limits_{m \in M, \; t' = 1}^{t} c\_progress_{m,i,c,t'} = move\_cost_{i,c}
\]
subject to finish{(i,c) in C, t in T}:
c_end[i,c,t] = 1 <==> sum{m in M, t_ in 1..t} c_progress[m,i,c,t_] >= move_cost[i,c];
Containers logic constraints…
Containers are in a stack:
\[
c\_mov_{m,i,c,t} \leq c\_end_{i,c-1,t}\;, \quad \forall m \in M, (i,c) \in C: \ c \neq 1, \; t \in T
\]
in ampl:
subject to previous_container{m in M, (i,c) in C, t in T: c > 1}:
c_moving[m,i,c,t] <= c_end[i,c-1,t];
A finished container doesn’t move:
\[
c\_end_{\, i,c,t} = 1 \implies c\_mov_{m,i,c,t+1} = 0
\]
in ampl:
subject to already_finished{m in M, (i,c) in C, t in T: t <> last(T)}:
c_end[i,c,t] = 1 ==> c_moving[m,i,c,t+1] = 0;
We need to move every container.
\[
c\_end_{\, i,c,last(T)} = 1, \quad \forall (i,c) \in C
\]
in ampl:
subject to finish_all{(i,c) in C}:
c_end[i,c,last(T)] = 1;
\(c_end\) variable is monotonous, so we can write some constraints to strengthen the model so it gets solved faster.
\[
c\_end_{\, i,c,t-1} \leq c\_end_{\, i,c,t}, \quad \forall (i,c) \in C, \ \forall t \in T \setminus \{ 1 \}
\]
\[
c\_end_{\, i,c-1,t} \geq c\_end_{\, i,c,t}, \quad \forall (i,c) \in C: \ c \neq 1 \ \forall t \in T
\]
in ampl:
c_end[i,c,t-1] <= c_end[i,c,t];
c_end[i,c-1,t] >= c_end[i,c,t];
If a machine is moving a block, no other machine can use it.
\[
\sum \limits_{(i',c) \in C: \ i = i'} c\_mov_{i,c,t} \geq 1 \implies \forall_{\substack{(i', c) \in C: \ i != i'}} \ c\_mov_{i',c,t} = 0
\]
in ampl:
subject to only_one_block{m in M, i in B, t in T}:
sum{(i_,c) in C: i == i_} c_moving[m,i,c,t] >= 1 ==> forall{(i_, c) in C: i != i_} c_moving[m,i_,c,t] = 0;
Finish the partially moved containers.
\[
c\_mov_{m,i,c,t-1} = 1 \implies c\_mov_{m,i,c,t} = 1 \lor c\_end_{i,c,t-1} = 1
\]
in ampl:
subject to cant_forget_active_containers{m in M, (i,c) in C, t in T: t != last(T)}:
c_moving[m,i,c,t] = 1 ==> c_moving[m,i,c,t+1] = 1 or c_end[i,c,t] = 1;
A container is only dispatched by 1 machine:
\[
\sum \limits_{m \in M} c\_mov_{m,i,c,t} \leq 1
\]
in ampl:
subject to one_mach_per_container{(i,c) in C, t in T}:
sum{m in M} c_moving[m,i,c,t] <= 1;
Objective#
We have no objective in this problem, but if we can add some of them to get “better” feasible solutions. For example, giving some penalties to delayed blocks or unused capacity of the machines.
\[
\min \quad delay\_penalty + unused\_cap\_penalty
\]
where
\[
delay\_penalty = \sum \limits_{(i,c) \in C, \; t \in T} (1-c\_end_{\, i,c,t })
\]
\[
unused\_cap\_penalty = \sum \limits_{m \in M, \; (i,c) \in C, \; t \in T} \frac{t}{|T|} \cdot \frac{c\_progress_{m,i,c,t}}{total\_move}
\]
in ampl:
var delay_penalty = sum{(i,c) in C, t in T} (1-c_end[i,c,t]);
var unused_cap_penalty = sum{m in M, (i,c) in C, t in T} t/card(T)*c_progress[m,i,c,t]/total_move;
minimize penalty: unused_cap_penalty + delay_penalty;
With this formulation, we get a neat model easy to read despite of being a complex system.
We are using many logical constraints such as indicator constraints, logical operators (or and forall), but we can still use a MIP solver such as Highs or Gurobi to solve the problem due to the driver’s reformulation.
%%ampl_eval
reset;
# Blocks
set B;
# Time periods
set T ordered;
# Containers
set C dimen 2; # (block, container)
# Machines
set M;
# Cost per container
param move_cost{C};
param total_move := sum{(i,c) in C} move_cost[i,c];
# Work capacity of the crane
param work_cap {M};
# Vars #
# Container in progress, container is finished, container progress units
var c_moving{M,C,T} binary;
var c_end{C,T} binary;
var c_progress{m in M,C,T} >= 0 <= work_cap[m];
# Constraints #
## Container completion
# Cant progress more than available in the container
subject to progress_limit_container{(i,c) in C}:
sum{m in M, t in T} c_progress[m,i,c,t] <= move_cost[i,c];
# Cant progress more than available by the machine
subject to progress_limit{m in M, t in T}:
sum{(i,c) in C} c_progress[m,i,c,t] <= work_cap[m];
## Containers logic
# Active iff in progress:
subject to active_work{m in M, (i,c) in C, t in T}:
c_moving[m,i,c,t] = 1 <==> c_progress[m,i,c,t] > 0;
# c_moving[m,i,c,t] = 1 <==> c_progress[m,i,c,t] >= 1e-9;
# if completely moved then finish container.
subject to finish{(i,c) in C, t in T}:
c_end[i,c,t] = 1 <==> sum{m in M, t_ in 1..t} c_progress[m,i,c,t_] >= move_cost[i,c];
# A container is not active unless previous has finished:
subject to previous_container{m in M, (i,c) in C, t in T: c > 1}:
c_moving[m,i,c,t] <= c_end[i,c-1,t];
# A container is not active if it already finished:
subject to already_finished{m in M, (i,c) in C, t in T: t <> last(T)}:
c_end[i,c,t] = 1 ==> c_moving[m,i,c,t+1] = 0;
subject to finish_all{(i,c) in C}:
c_end[i,c,last(T)] = 1;
# Finished container can't go unfinished
subject to remain_finished{(i,c) in C, t in T: t <> last(T)}:
c_end[i,c,t] <= c_end[i,c,t+1];
# Cant go to other blocks
subject to only_one_block{m in M, i in B, t in T}:
sum{(i_,c) in C: i == i_} c_moving[m,i,c,t] >= 1 ==> forall{(i_, c) in C: i != i_} c_moving[m,i_,c,t] = 0;
# Cant forget containers
subject to cant_forget_active_containers{m in M, (i,c) in C, t in T: t != last(T)}:
c_moving[m,i,c,t] = 1 ==> c_moving[m,i,c,t+1] = 1 or c_end[i,c,t] = 1;
# One machine per container atmost
subject to one_mach_per_container{(i,c) in C, t in T}:
sum{m in M} c_moving[m,i,c,t] <= 1;
# Objective #
var delay_penalty = sum{(i,c) in C, t in T} (1-c_end[i,c,t]);
#var delay_penalty_scaled = sum{c in C, t in T} (1-c_end[c,t])/card({C,T});
# Scaled!!
var unused_cap_penalty = sum{m in M, (i,c) in C, t in T} t/card(T)*c_progress[m,i,c,t]/total_move;
minimize penalty: unused_cap_penalty + delay_penalty;
Solving a simple instance#
We are using the open source solver highs to solve an instance of the problem:
def container_cost(i, l):
return max(3, (i + l) % 7)
periods = 10
containers = 4
blocks = 2
machines = 2
container_costs = {
(i, l): container_cost(i, l)
for i in range(1, blocks + 1)
for l in range(1, containers + 1)
}
print(container_costs)
work_capacity = {m: 5 for m in range(1, machines + 1)}
ampl.set["T"] = range(1, periods + 1)
ampl.set["B"] = range(1, blocks + 1)
ampl.set["M"] = range(1, machines + 1)
ampl.set["C"] = [(i, l) for i in range(1, blocks + 1) for l in range(1, containers + 1)]
ampl.param["move_cost"] = container_costs
ampl.param["work_cap"] = work_capacity
ampl.solve(solver="highs")
# ampl.display('c_moving')
# ampl.display('c_end')
ampl.display(
"{m in M, (i,c) in C, t in T : c_progress[m,i,c,t] >= 1e-6} c_progress[m,i,c,t]"
)
{(1, 1): 3, (1, 2): 3, (1, 3): 4, (1, 4): 5, (2, 1): 3, (2, 2): 4, (2, 3): 5, (2, 4): 6}
HiGHS 1.7.0:HiGHS 1.7.0: optimal solution; objective 10.21818182
7327 simplex iterations
22 branching nodes
absmipgap=3.55271e-15, relmipgap=0
c_progress[m,i,c,t] :=
1 2 1 1 3
1 2 2 1 2
1 2 2 2 2
1 2 3 2 3
1 2 3 3 2
1 2 4 3 3
1 2 4 4 3
2 1 1 1 3
2 1 2 1 2
2 1 2 2 1
2 1 3 2 4
2 1 4 3 5
;
Solving a more difficult instance#
We are using Gurobi, a powerful commercial solver to solve the instance. Notice that we are using timeout=150s so Gurobi only runs for 150 seconds, which is enough for giving a good solution.
We can check some stats of the solving process through the outlev=1 option.
(If you are using a Community Edition from Google Colab, you can change to the ‘highs’ solver and try to solve the instance)
def container_cost(i, l):
return max(3, (i + l * 17) % 10)
periods = 20
containers = 8
blocks = 4
machines = 3
container_costs = {
(i, l): container_cost(i, l)
for i in range(1, blocks + 1)
for l in range(1, containers + 1)
}
work_capacity = {m: 5 + m for m in range(1, machines + 1)}
ampl.set["T"] = range(1, periods + 1)
ampl.set["B"] = range(1, blocks + 1)
ampl.set["M"] = range(1, machines + 1)
ampl.set["C"] = [(i, l) for i in range(1, blocks + 1) for l in range(1, containers + 1)]
ampl.param["move_cost"] = container_costs
ampl.param["work_cap"] = work_capacity
ampl.option["gurobi_options"] = "outlev=1 timelim=150"
ampl.solve(solver="gurobi")
# ampl.display('c_moving')
# ampl.display('c_end')
ampl.display(
"{m in M, (i,c) in C, t in T : c_progress[m,i,c,t] >= 1e-6} c_progress[m,i,c,t]"
)
Gurobi 11.0.1: Set parameter LogToConsole to value 1
tech:outlev = 1
Set parameter TimeLimit to value 150
lim:time = 150
Set parameter InfUnbdInfo to value 1
Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (linux64 - "TUXEDO OS 2")
CPU model: 13th Gen Intel(R) Core(TM) i5-1340P, instruction set [SSE2|AVX|AVX2]
Thread count: 16 physical cores, 16 logical processors, using up to 16 threads
Warning: LP warm-starts, PStart/DStart, discarded due to model modification
Optimize a model with 8472 rows, 18705 columns and 23096 nonzeros
Model fingerprint: 0x2f0d578f
Model has 9424 general constraints
Variable types: 1921 continuous, 16784 integer (0 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [3e-04, 1e+00]
Bounds range [1e+00, 6e+02]
RHS range [1e+00, 9e+00]
GenCon rhs range [1e-04, 9e+00]
GenCon coe range [1e+00, 1e+00]
User MIP start did not produce a new incumbent solution
User MIP start violates constraint R2 by 1.000000000
Presolve added 6109 rows and 0 columns
Presolve removed 0 rows and 13985 columns
Presolve time: 0.61s
Presolved: 14581 rows, 4720 columns, 74156 nonzeros
Variable types: 1952 continuous, 2768 integer (2768 binary)
Root relaxation: objective 9.834206e+01, 5835 iterations, 0.23 seconds (0.28 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 98.34206 0 345 - 98.34206 - - 1s
0 0 98.34206 0 344 - 98.34206 - - 1s
Another try with MIP start
0 0 98.89930 0 335 - 98.89930 - - 1s
0 0 100.87147 0 345 - 100.87147 - - 1s
0 0 100.88099 0 337 - 100.88099 - - 1s
0 0 100.88235 0 340 - 100.88235 - - 1s
0 0 100.88397 0 337 - 100.88397 - - 1s
0 0 100.88397 0 336 - 100.88397 - - 1s
0 0 101.05640 0 346 - 101.05640 - - 1s
0 0 101.05640 0 333 - 101.05640 - - 1s
0 0 101.05640 0 333 - 101.05640 - - 1s
0 0 101.34332 0 360 - 101.34332 - - 2s
0 0 101.36797 0 419 - 101.36797 - - 2s
0 0 101.36797 0 427 - 101.36797 - - 2s
0 0 101.36954 0 406 - 101.36954 - - 2s
0 0 101.37053 0 399 - 101.37053 - - 2s
0 0 101.37053 0 399 - 101.37053 - - 2s
0 0 101.96355 0 405 - 101.96355 - - 3s
0 0 102.11676 0 431 - 102.11676 - - 3s
0 0 102.12872 0 451 - 102.12872 - - 3s
0 0 102.13470 0 463 - 102.13470 - - 3s
0 0 102.14043 0 465 - 102.14043 - - 3s
0 0 102.14048 0 466 - 102.14048 - - 3s
0 0 102.44833 0 450 - 102.44833 - - 4s
0 0 102.44887 0 457 - 102.44887 - - 4s
0 0 102.45568 0 456 - 102.45568 - - 4s
0 0 102.45664 0 452 - 102.45664 - - 4s
0 0 102.50251 0 467 - 102.50251 - - 4s
0 0 102.50251 0 470 - 102.50251 - - 4s
0 0 102.50251 0 474 - 102.50251 - - 4s
0 0 102.56339 0 472 - 102.56339 - - 4s
0 0 102.56365 0 477 - 102.56365 - - 4s
0 0 102.59846 0 477 - 102.59846 - - 4s
0 0 102.59846 0 472 - 102.59846 - - 4s
0 0 102.59846 0 473 - 102.59846 - - 5s
0 0 102.60359 0 482 - 102.60359 - - 5s
0 0 102.61077 0 489 - 102.61077 - - 5s
0 0 102.61097 0 486 - 102.61097 - - 5s
H 0 0 135.2597633 102.61097 24.1% - 5s
H 0 0 135.2538462 102.62097 24.1% - 5s
0 0 102.62097 0 485 135.25385 102.62097 24.1% - 5s
0 0 102.62646 0 488 135.25385 102.62646 24.1% - 5s
0 0 102.62768 0 474 135.25385 102.62768 24.1% - 5s
0 0 102.62853 0 482 135.25385 102.62853 24.1% - 5s
0 0 102.62860 0 490 135.25385 102.62860 24.1% - 5s
0 0 102.63671 0 516 135.25385 102.63671 24.1% - 6s
H 0 0 132.2485207 102.63936 22.4% - 6s
0 0 102.64201 0 497 132.24852 102.64201 22.4% - 6s
0 0 102.64405 0 506 132.24852 102.64405 22.4% - 6s
0 0 102.64513 0 502 132.24852 102.64513 22.4% - 6s
0 0 102.64516 0 507 132.24852 102.64516 22.4% - 6s
0 0 102.69510 0 480 132.24852 102.69510 22.3% - 6s
0 0 102.71178 0 496 132.24852 102.71178 22.3% - 6s
0 0 102.71178 0 481 132.24852 102.71178 22.3% - 6s
0 0 102.71178 0 495 132.24852 102.71178 22.3% - 6s
H 0 0 129.2467456 102.71178 20.5% - 6s
0 0 102.71178 0 495 129.24675 102.71178 20.5% - 6s
0 0 102.71178 0 488 129.24675 102.71178 20.5% - 6s
0 0 102.71915 0 470 129.24675 102.71915 20.5% - 7s
H 0 0 129.2461538 102.72981 20.5% - 7s
0 0 102.72981 0 475 129.24615 102.72981 20.5% - 7s
0 0 102.72981 0 475 129.24615 102.72981 20.5% - 7s
0 0 102.74020 0 475 129.24615 102.74020 20.5% - 7s
0 0 102.75964 0 500 129.24615 102.75964 20.5% - 7s
0 0 102.75964 0 504 129.24615 102.75964 20.5% - 7s
0 0 102.75964 0 506 129.24615 102.75964 20.5% - 7s
0 0 102.77134 0 495 129.24615 102.77134 20.5% - 8s
H 0 0 129.2452663 102.78734 20.5% - 8s
0 0 102.78734 0 493 129.24527 102.78734 20.5% - 8s
0 0 102.78734 0 491 129.24527 102.78734 20.5% - 8s
0 0 102.78734 0 497 129.24527 102.78734 20.5% - 8s
0 0 102.80090 0 469 129.24527 102.80090 20.5% - 8s
H 0 0 128.2452663 102.80277 19.8% - 8s
0 0 102.80308 0 476 128.24527 102.80308 19.8% - 8s
0 0 102.80880 0 471 128.24527 102.80880 19.8% - 8s
0 0 102.80931 0 473 128.24527 102.80931 19.8% - 8s
0 0 102.81986 0 476 128.24527 102.81986 19.8% - 9s
0 0 102.82534 0 488 128.24527 102.82534 19.8% - 9s
0 0 102.82600 0 491 128.24527 102.82600 19.8% - 9s
0 0 102.82600 0 489 128.24527 102.82600 19.8% - 9s
0 0 102.82948 0 488 128.24527 102.82948 19.8% - 9s
0 0 102.83527 0 489 128.24527 102.83527 19.8% - 9s
0 0 102.83528 0 485 128.24527 102.83528 19.8% - 9s
0 0 102.83737 0 483 128.24527 102.83737 19.8% - 9s
0 0 102.83737 0 486 128.24527 102.83737 19.8% - 9s
0 0 102.85459 0 474 128.24527 102.85459 19.8% - 10s
0 0 102.85643 0 477 128.24527 102.85643 19.8% - 10s
0 0 102.86007 0 476 128.24527 102.86007 19.8% - 10s
0 0 102.86017 0 481 128.24527 102.86017 19.8% - 10s
0 0 102.86288 0 488 128.24527 102.86288 19.8% - 10s
0 0 102.86349 0 486 128.24527 102.86349 19.8% - 10s
0 0 102.87196 0 482 128.24527 102.87196 19.8% - 10s
0 0 102.87648 0 475 128.24527 102.87648 19.8% - 10s
0 0 102.87772 0 470 128.24527 102.87772 19.8% - 11s
0 0 102.89310 0 486 128.24527 102.89310 19.8% - 11s
0 0 102.89310 0 488 128.24527 102.89310 19.8% - 11s
0 0 102.89310 0 477 128.24527 102.89310 19.8% - 11s
0 0 102.89805 0 467 128.24527 102.89805 19.8% - 11s
0 0 102.90016 0 465 128.24527 102.90016 19.8% - 11s
0 0 102.90066 0 489 128.24527 102.90066 19.8% - 11s
0 0 102.91501 0 491 128.24527 102.91501 19.8% - 11s
0 0 102.92636 0 490 128.24527 102.92636 19.7% - 12s
0 0 102.92636 0 487 128.24527 102.92636 19.7% - 12s
0 0 102.93097 0 482 128.24527 102.93097 19.7% - 12s
H 0 0 126.2417160 102.94779 18.5% - 13s
0 0 102.94779 0 481 126.24172 102.94779 18.5% - 13s
0 0 102.94779 0 487 126.24172 102.94779 18.5% - 13s
H 0 0 126.2405325 102.94779 18.5% - 13s
0 0 102.94779 0 491 126.24053 102.94779 18.5% - 13s
0 0 102.94779 0 492 126.24053 102.94779 18.5% - 13s
0 0 102.94779 0 481 126.24053 102.94779 18.5% - 13s
0 0 102.94779 0 476 126.24053 102.94779 18.5% - 14s
0 2 102.94779 0 476 126.24053 102.94779 18.5% - 15s
H 31 48 123.2408284 103.62187 15.9% 569 17s
H 214 228 123.2393491 103.76613 15.8% 314 25s
H 215 228 122.2399408 103.76613 15.1% 314 25s
H 219 228 122.2346154 103.76613 15.1% 312 25s
H 224 228 122.2301775 103.76613 15.1% 310 25s
1315 1029 106.04866 14 252 122.23018 103.92721 15.0% 168 30s
H 2840 1921 121.2319527 104.17729 14.1% 143 35s
H 2842 1821 121.2310651 104.17729 14.1% 142 48s
H 2842 1730 121.2307692 104.17729 14.1% 142 48s
H 2842 1643 120.2298817 104.17729 13.4% 142 48s
H 2843 1561 118.2284024 104.17729 11.9% 142 54s
2844 1562 107.73994 26 432 118.22840 104.17729 11.9% 142 56s
2849 1565 107.40307 17 521 118.22840 104.64816 11.5% 142 60s
H 2849 1486 117.2295858 104.67565 10.7% 142 60s
2861 1494 105.31382 16 517 117.22959 104.81939 10.6% 142 66s
2862 1495 110.98888 28 517 117.22959 104.81939 10.6% 141 70s
2941 1560 110.83147 18 258 117.22959 104.81939 10.6% 164 76s
2957 1570 110.99844 19 242 117.22959 104.81939 10.6% 165 80s
3164 1669 111.83262 26 167 117.22959 104.81939 10.6% 175 85s
3456 1725 116.16136 37 129 117.22959 104.81939 10.6% 184 90s
4032 1837 115.48301 34 151 117.22959 105.31207 10.2% 195 95s
4741 1920 infeasible 23 117.22959 105.53595 10.0% 206 100s
5560 1991 108.86000 31 224 117.22959 105.62527 9.90% 209 105s
5902 2026 113.75177 27 245 117.22959 106.21630 9.39% 212 111s
6265 2174 112.85119 26 161 117.22959 106.31948 9.31% 214 115s
7164 2341 113.93525 33 243 117.22959 106.33309 9.30% 218 120s
7918 2781 114.11875 27 157 117.22959 106.54659 9.11% 222 125s
8840 3087 114.37338 36 171 117.22959 106.66320 9.01% 225 131s
9601 3545 113.84212 33 209 117.22959 106.87987 8.83% 229 136s
10031 3777 111.80408 30 290 117.22959 106.92011 8.79% 232 141s
10747 4110 108.92146 34 245 117.22959 107.01545 8.71% 235 146s
11638 4489 107.89782 28 285 117.22959 107.08646 8.65% 237 150s
Cutting planes:
Gomory: 7
Cover: 107
Implied bound: 40
Projected implied bound: 245
Clique: 43
MIR: 409
StrongCG: 2
Flow cover: 215
GUB cover: 16
Inf proof: 24
Zero half: 33
RLT: 69
Relax-and-lift: 60
BQP: 21
Explored 11805 nodes (2814335 simplex iterations) in 150.01 seconds (163.75 work units)
Thread count was 16 (of 16 available processors)
Solution count 10: 117.23 118.228 120.23 ... 123.239
Time limit reached
Best objective 1.172295857988e+02, best bound 1.070864611738e+02, gap 8.6524%
Gurobi 11.0.1: time limit, feasible solution
2.81434e+06 simplex iterations
11805 branching nodes
absmipgap=10.1431, relmipgap=0.0865236
c_progress[m,i,c,t] [1,1,*,*]
: 5 6 8 9 :=
4 6 3 . .
6 . 3 . .
7 . . 3 .
8 . . 3 4
[1,2,*,*]
: 3 :=
3 3
4 3
[1,3,*,*]
: 7 :=
4 3
7 3
[1,4,*,*]
: 1 2 4 :=
1 3 . .
4 3 . .
6 . 6 .
7 . . 3
8 . . 3
[2,2,*,*]
: 3 4 :=
2 6 .
6 1 3
7 . 3
[2,3,*,*]
: 5 6 7 8 :=
1 3 . . .
2 4 3 . .
3 . 4 . .
6 . . 5 .
8 . . 2 7
[2,4,*,*]
: 1 2 :=
3 5 .
5 2 7
[3,1,*,*]
: 4 5 6 :=
1 8 . .
2 . 5 .
3 . 3 .
5 . . 6
[3,2,*,*]
: 2 3 8 :=
1 8 1 .
5 . 7 .
8 . . 8
[3,3,5,7] 8
[3,4,2,1] 8
;