Mathematical Programming
Graded assignment 1 - Column generation
Please conform to the following instructions:
1. Hand in a report as pdf file.
(a) Use the tile “GA1 Report .pdf”, (for example “GA1 Report 123456.pdf”).
(b) At the start of your report mention your name and student number.
(c) The report must be clearly written, concise and complete.
(d) Use between 1 and 3 pages.
2. Hand in the used code in a zip file.
(a) Use the title “GA1 Code .zip”, (for example “GA1 Code 123456.zip”).
3. Hand in your report and code through Canvas.
Assignment
In this assignment, we consider the bin packing problem as can be found in the lecture slides. An instance
of the bin packing problem can be found in BinPackingInstance.txt. The aim is to apply a column
generation algorithm to this instance, to solve the LP relaxation of the bin packing problem, using the
formulation presented in the lecture slides. We slightly modify the formulation as follows. Replace the
equality constraints with inequalities, such that each item should be packed in at least one bin.
For your convenience, feel free to use the file BinPackingInstance.java. It contains a class to represent
a bin packing instance, and it can be used to read BinPackingInstance.txt.
a. Why is the modified formulation of the bin packing problem also correct?
b. What is an advantage of using the modified formulation?
c. Initialize the restricted master problem using the packings provided in InitialPackings.txt.
Solve the initial restricted master problem and report the solution.
d. Describe the pricing problem and explain how you solve it.
Make it easy on yourself ! Solving the pricing problem may be done exactly or heuristically.
e. Perform 7 iterations of the column generation algorithm. At each iteration, report
1. the solution value of the restricted master problem,
2. the new packing that is added to the restricted master problem,
3. the reduced cost of the new packing.
1