Containers scheduling

containers_scheduling.ipynb Open In Colab Kaggle Gradient Open In SageMaker Studio Lab Hits

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

(wsj.com)

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
;