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
