Branch and price for submodular bin packing
Liding Xu
LIX CNRS, École Polytechnique
With: Claudia D’Ambrosio, Sonia Haddad Vanier, Emiliano Traversi
02/02/2023

Interests of research
Cloud computing is a over-competitive market.

Liding Xu

Branch and price for submodular bin packing

2 / 29Interests of research

Resource (memory, CPU, bandwidth, disk) allocation is key to success of cloudcomputing providers, e.g., AWS, GOOGLE, OVH, SCALEWAY, HETZNER,ALIBABA....

Liding Xu

Branch and price for submodular bin packing

3 / 29Research problem

On demand allocations of virtual machines: we want to preallocate virtualmachines in a physical machine while considering uncertainty.

Liding Xu

Branch and price for submodular bin packing

4 / 29

Some questions

How to model the uncertainty? Adding some nonlinearity in the classicalmodel.
Is Dantzig-Wolfe reformulation applicable in mixed-integer nonlinear programming (MINLP)? Yes, it works.
How is the practical quality of well-known heuristics/approximation algorithms
for resource allocation? Good.

Liding Xu

Branch and price for submodular bin packing

5 / 29

Overview1

Branch-and-price for submodular binpacking

2Dantzig-Wolfe reformulation

3

Conclusion

Liding Xu

Branch and price for submodular bin packing

6 / 29

Table of Contents

1

Branch-and-price for submodular binpacking

2Dantzig-Wolfe reformulation

3

Conclusion

Liding Xu

Branch and price for submodular bin packing

7 / 29

Table of Contents

1

Branch-and-price for submodular binpacking

2Dantzig-Wolfe reformulation

3

Conclusion

Liding Xu

Branch and price for submodular bin packing

8 / 29Dantzig-Wolfe reformulation and relaxation for MILP

Dantzig-Wolfe (DW): a reformulation technique for Mixed-Integer Linear
Program (MILP) with decomposable structures.
Decomposition: a main problem + a pricing sub problem, and the mainproblem has an huge LP relaxation.

Liding Xu

Branch and price for submodular bin packing

9 / 29Dantzig-Wolfe reformulation and relaxation for MILP

Dantzig-Wolfe (DW): a reformulation technique for Mixed-Integer Linear
Program (MILP) with decomposable structures.
Decomposition: a main problem + a pricing sub problem, and the main
problem has an huge LP relaxation.
Main LP relaxation: solved via column generation.
Pricing sub problem: solved via pricing algorithm.
Integer DW reformulation: solved via branch-and-price algorithm.

Liding Xu

Branch and price for submodular bin packing

9 / 29

The performance of DW reformulation
Decomposition: main problem (integer optimization) + sub problem.
the LP relaxation of the main problem is somtimes called configuration LP.
Quality of relaxations: stronger bounds than those of the naive LP relaxations.

Figure: Decomposable structures in coefficients matrix of an MILP

Liding Xu

Branch and price for submodular bin packing

10 / 29

Submodular binpacking

Classical binpacking (BP): packing unsplittable items into a minimal numberof bins (capacity usage is linear w.r.t. allocation of items).
Practical issue: sizes of items are uncertain and unprovisioned?

Liding Xu

Branch and price for submodular bin packing

11 / 29

Submodular binpacking

Classical binpacking (BP): packing unsplittable items into a minimal numberof bins (capacity usage is linear w.r.t. allocation of items).
Practical issue: sizes of items are uncertain and unprovisioned?
Motivating example: all cloud computing providers function on virtualization techniques:create virtual machines (items) on dedicated servers (bins);
receive many random requests for virtual machines;
some statistics on demands/data.

Liding Xu

Branch and price for submodular bin packing

11 / 29

Modelling

We consider static but probabilistic models (assumption on data):
BP with chance constraints;
Distributionally robust BP.
These models admit an exact MINLP reformulation (nice for us, no need forsampling): submodular binpacking.

Liding Xu

Branch and price for submodular bin packing

12 / 29

Submodular functions

Definition
A function f : {0, 1}n → R is called a submodular function, if for every
x, y ∈ {0, 1}n , f (x) + f (y ) ≥ f (max(x, y )) + f (min(x, y )), where max, min are
element-wise minimum and maximum.
Econ. explanation: you get less and less utility when paying more resources.

Liding Xu

Branch and price for submodular bin packing

13 / 29

The submodular binpacking formulation
Submodular binpacking:

minX

(1)

yj ,j∈M

Xi∈Nai vij + σsXbi vij ≤ cyj ,∀j ∈ M,

(2)

X

∀i ∈ N ,(3)∀i ∈ N , j ∈ M,∀j ∈ M(4)i∈N

vij = 1,j∈Mvij ∈ {0, 1},yj ∈ {0, 1},(5)

Our first contribution: DW reformulation.
Liding Xu

Branch and price for submodular bin packing

14 / 29

DW decomposition: main problem
Let P be the set of all possible configurations of a bin. DW refomrulation = setcover formulation:
Xmin
λp ,(6a)p∈PX

dip λp ≥ 1,

∀i ∈ N ,(6b)λp ∈ {0, 1},∀p ∈ P.

(6c)p∈P

Liding Xu

Branch and price for submodular bin packing

15 / 29

DW decomposition: main problem
Let P be the set of all possible configurations of a bin. DW refomrulation = setcover formulation:
Xmin
λp ,
(6a)
p∈PX

dip λp ≥ 1,

∀i ∈ N ,(6b)

λp ∈ {0, 1},∀p ∈ P.

(6c)p∈P|P| is huge, so solving the LP relaxation via pricing.

Liding Xu

Branch and price for submodular bin packing

15 / 29

DW decomposition: pricing problem
Find a configuration which yields the steepest descent of the main problem:
Xvprcing = max
πi′ xi ,(7a)i∈NXi∈Nai′ xi + σsXbi′ xi ≤ c,(7b)i∈Nxi ∈ {0, 1},

Liding Xu∀i ∈ N .

Branch and price for submodular bin packing(7c)16 / 29

DW decomposition: pricing problem
Find a configuration which yields the steepest descent of the main problem:
Xvprcing = max
πi′ xi ,(7a)i∈NXi∈Nai′ xi + σ

sXbi′ xi ≤ c,(7b)i∈Nxi ∈ {0, 1},∀i ∈ N .

(7c)

A convex MINLP: solvable by CPLEX.
Our second contribution: Tailored MILP-based branch-and-cut.

Liding Xu

Branch and price for submodular bin packing

16 / 29

An exact pricing algorithm: initial MILP relaxation
Xi∈Nai′ xi + σsXbi′ xi ≤ c ≡i∈NXbi′ xi ≤ (c −i∈NXai′ xi )2 /σ 2 .

i∈N

1d piece-wise-linear concave overestimator for q(w ) := (c − w )2 .
4qq̄

3

2

1001w

2Figure: Graphs of the quadratic and its PWL over-estimator
Liding Xu

Branch and price for submodular bin packing

17 / 29

An exact algorithm for pricing problem: Relaxation refining

Relaxation refining: posterior approximation, lazy cuts separated at infeasible
binary points, via
linearization of the convex function
qPP′′ 2i∈N ai xi + σi∈N bi xi .
Combined together, an exact algorithm faster than CPLEX’s branch-and-cut
algorithm.

Liding Xu

Branch and price for submodular bin packing

18 / 29Hybrid pricing strategy

Our third contribution: a meta pricing scheduler that replace exact pricing
algorithm via heuristic algorithms.
When can we avoid to use the expensive exact pricing algorithm? Some hints
from the dual bound.

Liding Xu

Branch and price for submodular bin packing

19 / 29

Dual bounds
Maser LP (MLP) (long time to converge):
X
X
Dual bound vMLP = minλp :dip λp ≥ 1, ∀i ∈ N , λp ∈ [0, 1], ∀p ∈ P.
p∈Pp∈P(8)Liding Xu

Branch and price for submodular bin packing

20 / 29

Dual bounds
Maser LP (MLP) (long time to converge):
X
X
Dual bound vMLP = minλp :dip λp ≥ 1, ∀i ∈ N , λp ∈ [0, 1], ∀p ∈ P.
p∈Pp∈P(8)Restricted Maser LP (RMLP) (solved during column generation):
XXvRMLP = minλp :dip λp ≥ 1, ∀i ∈ N , λp ∈ [0, 1], ∀p ∈ P ′ ⊆ P. (9)p∈Pp∈PvMLP ≤ vRMLP .

Liding Xu

Branch and price for submodular bin packing

20 / 29

Farley boundRecall that vprcing is the pricing objective value (a maximum problem). Then,vRMLP /vprcing ≤ vMLP ≤ vRMLP . Thus, vRMLP /vprcing is also a lower bound(Farley bound) .

Liding Xu

Branch and price for submodular bin packing

21 / 29

When exact pricing cannot yield better Farley boundAssume that we have a good and fast pricing heuristic (which also generates acolumn), we run it firstTheorem
Let vheur be the solution value of the pricing heuristic, let vRMLP be the optimumof RMLP, and let vld be the current local dual bound for the master problem. IfvRMLPvheur ≤ vld , the exact algorithm cannot yield a better local dual bound than vld .
vRMLP
Because vheur ≥ vprice , vRMLPvheur ≤ vld implies that vprice ≤ vld (no need for exactpricing).

Liding Xu

Branch and price for submodular bin packing

22 / 29

Experiment: settings

Settings:
Compact: compact formulation solved by CPLEX.
DW: DW reformulation with pricing problem solved by CPLEX.
DW+: DW reformulation with tailored pricing algorithm.
DW-hybrid: DW+ with a hybrid strategy using heuristics or exact pricingalgorithms.

Liding Xu

Branch and price for submodular bin packing

23 / 29

Experiment: environment

Randomly generated instances: number of items in {100, 400, 1000}.
Intel Xeon @ 3.90GHz and 126GB memory, 3600 CPU second time limit.
Every setting is given by a solution found by a greedy heuristic..

Liding Xu

Branch and price for submodular bin packing

24 / 29

Experiment: results
Benchmarks

CloudSmall(|N | = 100)

CloudMedium(|N | = 400)

CloudLarge(|N | = 1000)

Solvers
BSOCP-BC
DW-BC
DW-PWL
DW-Hybrid
BSOCP-BC
DW-BC
DW-PWL
DW-Hybrid
BSOCP-BC
DW-BC
DW-PWL
DW-Hybrid

Problem statistics
time (s) dual gap (%)
1452
15.8
2129
11.4
633
2.4
330
2.0
3600
100.0
3600
39.0
3600
17.2
3600
11.8
3600
100.0
3600
59.6
3600
43.1
3600
34.2

primal improve(%) #columns
0.0
0.9
1373
2.7
1869
3.4
3485
0.0
0.1
861
0.4
3372
0.6
6879
0.00.0741
0.2
2105
0.4
4257

Table: Aggregated statistics of the main computational results

Liding Xu

Branch and price for submodular bin packing

25 / 29

Results

Experiment: provides better dual bounds than CPLEX’s bounds for compact
formulation (13%+ improvement).
Conclusion: greedy algorithms perform quite well (usually better than theoretical performance guarantee) (5% to optimality).
Related paper: Xu, D’Ambrosio, Haddad Vanier, and Traversi. "Branch andPrice for Submodular Bin Packing", European journal on computationaloptimization, 2023.

Liding Xu

Branch and price for submodular bin packing

26 / 29

Table of Contents

1

Branch-and-price for submodular binpacking

2Dantzig-Wolfe reformulation

3Conclusion

Liding Xu

Branch and price for submodular bin packing

27 / 29

Conclusion

In this paper, we explore DW reformulation for the submodular binpacking(MINLP);
We propose several methods to generate columns efficiently;
The results show that the DW reformulation is a promising method for thesubmodular binpacking (closing duality gap).

Liding Xu

Branch and price for submodular bin packing

28 / 29

The endThank you for your attention!

Liding Xu

Branch and price for submodular bin packing

29 / 29