# AMPL Bin Packing Problem with GCG¶

Description: Dantzig-Wolfe decomposition for Bin Packing Problem with GCG

Tags: GCG, bpp, amplpy, dantzig-wolfe decomposition, branch-price-and-cut, highlights

Notebook author: Jurgen Lentz <jurgenlentz26@gmail.com>

# Install dependencies
%pip install -q amplpy

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
modules=["gcg", "gurobi", "scip", "highs", "cbc"],  # modules to install
)  # instantiate AMPL object and register magics


## Bin Packing Problem¶

Given $n$ items with weights $w_{i}$ for all $i \in {1,…,n}$ and bins with capacity $C$ (for each bin), the bin packing problem assigns each item $i$ to a bin while minimizing the number of used bins. BPP can be modeled as follows:

\begin{aligned} \text{minimize} \quad &\sum_{j = 1}^{m} y_{j} \ \text{subject to} \quad &\sum_{i = 1}^{n} w_{i} x_{i j} \leq C y_{j} \quad \forall j \in {1,…,m} \ &\sum_{j = 1}^{m} x_{i j} \geq 1 \quad \forall i \in {1,…,n} \ &x_{i j} \in {0,1} \quad \forall i \in {1,…,n}, j \in {1,…,m} \ &y_{j} \in {0,1} \quad \forall j \in {1,…,m} \end{aligned}

We use suffix to feed GCG with a decomposition. Here, we select all allocation constraints to be in the master problem and $m$ knapsack subproblems (GCG aggregates the subproblems).

%%ampl_eval
param n;
param C;

suffix master IN, binary;
suffix block IN, integer;

set I = 1..n ordered;
param w {I} > 0;
param maxVal := max {i in I} w[i];
param maxbins := ceil(n / floor(C / maxVal));

set J = 1..maxbins;

var x {I,J} binary;
var y {J} binary;

minimize Cost:  sum {j in J} y[j];

subject to b_Capacity {j in J}:
sum {i in I} w[i] * x[i,j] <= C * y[j] suffix block j;

subject to m_Allocate {i in I}:
sum {j in J} x[i,j] >= 1 suffix master 1;


We generate a small instance with 50 items and bins with a capacity of 120.

ampl.param["n"] = 50
ampl.param["C"] = 120

w = [
100,
99,
98,
96,
94,
90,
89,
88,
88,
86,
84,
81,
81,
80,
79,
79,
78,
76,
72,
72,
72,
68,
68,
65,
63,
63,
63,
62,
62,
57,
57,
55,
48,
48,
47,
45,
44,
44,
41,
39,
36,
33,
31,
30,
28,
26,
25,
24,
22,
20,
]

ampl.param["w"] = {i: w[i - 1] for i in range(1, len(w) + 1)}


## Solve with GCG¶

ampl.option["solver"] = "gcg"
ampl.option["gcg_options"] = "outlev=1"
ampl.solve()


## Solve with Gurobi¶

ampl.option["solver"] = "gurobi"
ampl.option["gurobi_options"] = "outlev=1"
ampl.solve()


As seen above, GCG keeps up with Gurobi when solving this bin packing instance.

## Solve with HiGHS¶

ampl.option["solver"] = "highs"
ampl.option["highs_options"] = "outlev=1"
ampl.solve()


## Solve with SCIP¶

ampl.option["solver"] = "scip"
ampl.option["scip_options"] = "outlev=1"
ampl.solve()


## Solve with CBC¶

ampl.option["solver"] = "cbc"
ampl.option["cbc_options"] = "outlev=1"
ampl.solve()


GCG outperformes other open-source solvers solving this bin packing instance.