Question 1

Consider the following problem, used by Land and Doig in their seminal paper:

max 77.9x1 + 76.8x2 + 89.6x3 + 97.1y1 + 31.3y2 (1)

s.t.

10.9x1 + 3.6x2 − 40.8x3 + 43.9y1 + 7.1y2 + y3  = 82.3

−86.8x1 + 32.7x2 + 24.3x3 + 13.8y1 − 12.6y2 + y4 = 77.3

60.9x1 + 68.9x2 + 69.0x3 − 56.9y1 + 22.5y2 = 86.5

x1, x2, x3  ∈ Z+

 y1, y2, y3, y4 ∈ R+

(a) obtain the complete branch-and-bound tree using the following rules. For each node, indicate its number (in order of exploration). Also indicate the branching constraints and the reason for pruning leaf nodes.

• variable selection: always branch on the fractional variable with smallest index.

• node selection: depth-first (always explore first the child with the ≤ branching constraint. 

(b) obtain the complete branch-and-bound tree using the following rules. For each node, indicate its number (in order of exploration). Also indicate the reason for pruning in leaf nodes.

• variable selection: always branch on the fractional variable with largest index.

• node selection: node selection: best-bound (always explore the child with the best promising bound) 

Question 2

Consider the cutting stock problem with the following data: 

• Rolls length: 15m

• Items:

size: 2m / demand: 35

size: 4m / demand: 22 

size: 5m / demand: 17 

size: 6m / demand: 9 

size: 11m / demand: 7

Due to a technical constraint, no more than two different items type can be cut from the same roll. For example, you can cut 5 items of 3m from a roll, but you can not cut one roll with one item of 2m, one item of 4m and one item of 5m as it violates the technical constraint.

(a) Propose a compact model for the problem. How many rolls you need in the optimal solution? 

(b) Propose a pattern-based (column-based) model for the problem. Clearly define what is a pattern in your model. 

(c) Propose an initial set of columns and solve the relaxed version (with no integrality constraints) of the model you obtained in (b). What values for the dual variables do you obtain ? Give an economical interpretation for their values. 

(d) Propose a pricing problem for generating new columns. Use the duals you obtained in (c) to create a new column. 

(e) Carry out three iterations of a column generation, using your answers above. Which columns did you obtain? What is the optimal solution of this incomplete problem? Is this value an upper bound, a lower bound or none?