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
    license_uuid="default",  # license to use
)  # 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.

previous

AMPL - spreadsheet handling with amplxl

next

AMPL Capacitated p-Median Problem with GCG