# VPSolver: Cutting & Packing Problems¶

Description: Solving cutting & packing problems using arc-flow formulations

Tags: industry, cutting-stock, bin-packing, vector-packing

Notebook author: Filipe Brandão <fdabrandao@gmail.com>

Model author: Filipe Brandão

References:

```# Install dependencies
!apt -qq install libgraphviz-dev
%pip install -q amplpy pygraphviz pyvpsolver
```
```# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

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

## Instance preparation:¶

1. Define a multiple-choice vector bin packing instance:

```from pyvpsolver import VPSolver, MVP, AFG, MPS

Ws, Cs, Qs = [(5180, 9), (5189, 9)], [1, 1], [-1, -1]
ws = [[(1120, 1)], [(1250, 1)], [(520, 1)], [(1066, 1)], [(1000, 1)], [(1150, 1)]]
b = [9, 5, 91, 18, 11, 64]
instance = MVP(Ws, Cs, Qs, ws, b)
```
1. Build an arc-flow graph for the instance defined above:

```afg = AFG(instance)
from IPython.display import SVG

afg.draw("graph_vbp.svg", lpaths=True, graph_attrs={"size": "8,8"})
SVG("graph_vbp.svg")
```
```VPSolver 3.1.3, Copyright (C) 2013-2016, Filipe Brandao
Build (method = -3)
#dp: 163
Step-3' Graph: 50 vertices and 199 arcs (0.00s)
Step-4' Graph: 39 vertices and 132 arcs (0.00s)
#V4/#V3 = 0.78
#A4/#A3 = 0.66
```

## Model¶

```%%ampl_eval
reset;
set V;
set A dimen 4;
var Flow{A} integer >= 0;

set Targets;
param Cost{Targets};
param Quantity{Targets};
minimize TotalCost:
sum{t in Targets} Cost[t] * Flow[t,'S',-1,-1];
s.t. BinQuantity{t in Targets: Quantity[t] >= 0}:
Flow[t,'S',-1,-1] <= Quantity[t];

set Items;
param Demand{Items};
s.t. SatisfyDemand{i in Items}:
sum{(u,v,i,j) in A} Flow[u,v,i,j] >= Demand[i];

s.t. FlowConservation{k in V}:
(sum{(u,v,i,j) in A: v == k} Flow[u,v,i,j]) - (sum{(u,v,i,j) in A: u == k} Flow[u,v,i,j]) == 0;
```

## Data¶

```graph = afg.graph()
ampl.set["Items"] = list(range(len(b)))
ampl.param["Demand"] = instance.b
ampl.set["Targets"] = graph.Ts
ampl.param["Cost"] = instance.Cs
ampl.param["Quantity"] = instance.Qs
ampl.set["V"] = graph.V
ampl.set["A"] = [
(u, v) + l if l != graph.LOSS else (u, v, -1, -1) for u, v, l in graph.A
]
```

## Solve¶

```ampl.option["solver"] = "highs"
ampl.solve()
```
```HiGHS 1.2.2: HiGHS 1.2.2: optimal solution; objective 33
1 branching nodes
absmipgap=7.10543e-14, relmipgap=2.15316e-15
```

## Extrat solution for the original problem¶

```values = ampl.get_data(
"{(u,v,i,j) in A: round(Flow[u,v,i,j]) > 0} round(Flow[u,v,i,j])"
).to_dict()
flows = {}
for (u, v, i, j), value in values.items():
u = u if isinstance(u, str) else int(u)
v = v if isinstance(v, str) else int(v)
l = graph.LOSS if i == -1 else (int(i), int(j))
flows[u, v, l] = int(value)
assert (u, v, l) in graph.A
graph.flow = flows
graph.labels = {(u, v, lbl): [lbl] for (u, v, lbl) in graph.A if lbl != graph.LOSS}
for i in range(len(Ws)):
total_flow = flows.get((graph.Ts[i], "S", graph.LOSS), 0)
sol = graph.extract_solution(graph.S, "<-", graph.Ts[i], flow_limit=total_flow)
assert sum(m for m, p in sol) == total_flow
print(
"Bins of type {0}: {1} {2}".format(
i + 1, total_flow, ["bins", "bin"][total_flow == 1]
)
)
for mult, patt in sol:
print(
"\t"
+ "{0} x [{1}]".format(
mult, ", ".join([f"i={it+1} opt={opt+1}" for it, opt in patt])
)
)
```
```Bins of type 1: 0 bins
Bins of type 2: 33 bins
11 x [i=3 opt=1, i=3 opt=1, i=3 opt=1, i=3 opt=1, i=3 opt=1, i=3 opt=1, i=4 opt=1, i=5 opt=1]
15 x [i=3 opt=1, i=6 opt=1, i=6 opt=1, i=6 opt=1, i=6 opt=1]
4 x [i=1 opt=1, i=1 opt=1, i=2 opt=1, i=3 opt=1, i=6 opt=1]
1 x [i=1 opt=1, i=3 opt=1, i=4 opt=1, i=4 opt=1, i=4 opt=1]
1 x [i=2 opt=1, i=3 opt=1, i=4 opt=1, i=4 opt=1, i=4 opt=1]
1 x [i=1 opt=1, i=3 opt=1, i=3 opt=1, i=3 opt=1, i=3 opt=1, i=3 opt=1, i=4 opt=1]
```