Binpacking problem
Binpacking Problem introduction
Heuristics for Bin Packing
• Next fit:
• First fit:
• Best fit:
Worst case Analysis: Elk van deze heuristieken heeft factor 2 prestatiegarantie
Model for Bin Packing Problem:
LP relaxation of Bin Packing Problem
, A stronger model for the Binpacking Problem
Column Generation: Add patterns iteratively
• We start with a limited number of patterns, thus an LP with a restricted set of variables.
• Solve this LP and obtain an optimal solution for the restricted problem.
• Is this solution optimal for the original problem? →Not necessarily, as we did not consider all possible patterns.
• Add those patterns that improve the objective function value. How?→ By using the dual prices (shadow prices).
• The dual price of a constraint indicates by how much the optimal value changes if the right hand side value of the constraint is
increased by 1.
0) Choose a set of start patterns that leads to a feasible solution. → We need a feasible solution because we need the dual prices.
1) The first LP model: Dual Prices
, 2) LP model 2
Dual Prices LP model 2
3) LP model 3
…) Continue adding New colums
Binpacking Problem introduction
Heuristics for Bin Packing
• Next fit:
• First fit:
• Best fit:
Worst case Analysis: Elk van deze heuristieken heeft factor 2 prestatiegarantie
Model for Bin Packing Problem:
LP relaxation of Bin Packing Problem
, A stronger model for the Binpacking Problem
Column Generation: Add patterns iteratively
• We start with a limited number of patterns, thus an LP with a restricted set of variables.
• Solve this LP and obtain an optimal solution for the restricted problem.
• Is this solution optimal for the original problem? →Not necessarily, as we did not consider all possible patterns.
• Add those patterns that improve the objective function value. How?→ By using the dual prices (shadow prices).
• The dual price of a constraint indicates by how much the optimal value changes if the right hand side value of the constraint is
increased by 1.
0) Choose a set of start patterns that leads to a feasible solution. → We need a feasible solution because we need the dual prices.
1) The first LP model: Dual Prices
, 2) LP model 2
Dual Prices LP model 2
3) LP model 3
…) Continue adding New colums
