Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 34

In mathematical programming, good performance essentially depends on the program’s ability to construct useful bounds (lower bounds for maximization and upper bounds for minimization). These bounds can be obtained by relaxing the linear program, i.e.

 – either increasing the set of solutions to optimize over a larger space (that is easier to optimize); this includes constraint relaxation (and in particular continuous relaxation);

 – or replacing the objective function with an upper bound (in the case of maximization), for example, Lagrangian relaxation.

For a mathematical program, the following continuous relaxations are possible:

 – (simple) continuous maximization, which is very effective for LPs (with the simplex algorithm, the interior-point method, or the volume algorithm); however, we will see that continuous relaxation is rarely the best option;

 – in the specific context of LPs, we can improve the value of linear relaxation by adding constraints – reinforcement;

 – we can also add variables – reformulation;

 – Lagrangian relaxation is another approach.