Task 3 (Not Yet Finished)¶

We consider the following problem (Fisher M., An Applications Oriented Guide to Lagrangian Relaxation Interfaces, 15:2, 1985):

$$ \begin{array}{lllll} z_P=&\text{max} &16x_1+10x_2+4x_4\\ &\text{s.t.}&8x_1+2x_2+x_3+4x_4\leq 10\\ &&x_1+x_2\leq 1\\ &&x_3+x_4\leq 1\\ &&0\leq x\leq 1 \qquad \text{and integer} \end{array} $$

There are three major questions to design a Lagrangian-relaxation-based system: a. which constraints should be relaxaed b. how to compute good multipliers $\lambda$ c. how to deduce a good feasible solution to the original problem, given a solution to the Lagrangian relaxation problem.

The answers are: a. those whose relaxation makes the problem significantly easy but not too easy b. subgradient optimization procedure c. problem specific heuristics

Subtask 2.1¶

If we relax the first constraint with multiplier $\lambda\geq 0$ the corresponding Lagrangian relaxation problem becomes:

$$ \begin{array}{lllll} z_P=&\text{max} &(16-8\lambda)x_1+(10-2\lambda)x_2+(0-\lambda)x_3+(4-4\lambda)x_4+10\lambda\\ &\text{s.t.}&x_1+x_2\leq 1\\ &&x_3+x_4\leq 1\\ &&0\leq x\leq 1 \qquad \text{and integer} \end{array} $$

For a given $\lambda$ we could solve the problem by inspection:

between $x_1$ and $x_2$ set to 1 the variable with the largest cost coefficient in the objective function;
between $x_1$ and $x_2$ set to 1 the variable with the largest cost coefficient in the objective function.

However let's use the SCIP procedure developed above.