Consider the following optimization problem (P1). maximize 4x1 + 6x2 + 5x3+4x4 + 6x5 + 4x6...

 

Transcribed Image Text:

Consider the following optimization problem (P1). maximize 4x1 + 6x2 + 5x3+4x4 + 6x5 + 4x6 + 15x7 + 15x8 subject to 3x1 + 10x2 + 7x7 + 8x8 ≤ 17, 5x1 + 2x2 + 4x7 + 3x8 ≤ 7, 6x3 +9x4+x7 +10x8 ≤ 13, 3x3 + 2x4 + 8x7 + 4x8 ≤ 8, x5 + 4x6 + 2x7+7x8 ≤ 8, 5x5 + 6x6 + 3x7 + 4x8 ≤ 13, X1, X2, X3, X4, X5, X6, X7, X8 € {0, 1}. (P₁) )Apply Lagrangian decomposition to (P1). Write down the re- formulated problem, show the relaxed constraints in the reformulated problem. Apply 2 iterations by hand-writing. Explicitly write down the master problem, subproblems, and each updating calculations, clearly. You may use subgradient algorithm or cutting planes algorithm, no need to use both. No need to apply Branch-and-Price, just solve the root node. Consider the following optimization problem (P1). maximize 4x1 + 6x2 + 5x3+4x4 + 6x5 + 4x6 + 15x7 + 15x8 subject to 3x1 + 10x2 + 7x7 + 8x8 ≤ 17, 5x1 + 2x2 + 4x7 + 3x8 ≤ 7, 6x3 +9x4+x7 +10x8 ≤ 13, 3x3 + 2x4 + 8x7 + 4x8 ≤ 8, x5 + 4x6 + 2x7+7x8 ≤ 8, 5x5 + 6x6 + 3x7 + 4x8 ≤ 13, X1, X2, X3, X4, X5, X6, X7, X8 € {0, 1}. (P₁) )Apply Lagrangian decomposition to (P1). Write down the re- formulated problem, show the relaxed constraints in the reformulated problem. Apply 2 iterations by hand-writing. Explicitly write down the master problem, subproblems, and each updating calculations, clearly. You may use subgradient algorithm or cutting planes algorithm, no need to use both. No need to apply Branch-and-Price, just solve the root node.

Answer rating: 100% (QA)

To apply Lagrangian decomposition to problem P1 we need to introduce Lagrange multipliers for each constraint Lets denote the Lagrange multipliers as 1 2 3 4 and 5 for the respective constraints The L... View the full answer