Detailed Description
mpec primal heuristic
This heuristic is based on the paper:
- Lars Schewe and Martin Schmidt
Computing Feasible Points for MINLPs with MPECs
An MPEC is a mathematical program with complementarity constraint. For example, the constraint x \in \{0, 1\} as x (1-x) = 0 can be modeled as complementarity constraint x = 0 or x = 1.
This heuristic applies only to mixed binary nonlinear problems. The idea is to rewrite the MBNLP as MPEC and solve the MPEC instead (to a a local optimum) by replacing each integrality constraint by the complementarity constraint x = 0 or x = 1. In principle, this MPEC can be reformulated to a NLP by rewriting this constraint as equation x (1-x) = 0. However, solving this NLP reformulation with a generic NLP solver will often fail. One issue is that the reformulated complementarity constraints will not, in general, satisfy constraint qualifications (for instance, Slater's conditions, which requires the existence of a relative interior point, will not be satisfied). In order to increase the chances of solving the NLP reformulation of the MPEC by a NLP solver, the heuristic applies a regularization (proposed by Scholtes): it relaxes x(1-x) = 0 to x(1-x) \leq \theta.
So the heuristic proceeds as follows.
- Build the regularized NLP (rNLP) with a starting \theta \in (0, \tfrac{1}{4}.
- Give the current LP solution as starting point to the NLP solver.
- Solves rNLP and let x^* be the best point found (if there is no point, abort).
- If feasible, then reduce \theta by a factor \sigma and use its solution as the starting point for the next iteration.
- If the rNLP is found infeasible, but the regularization constraints are feasible, abort.
- If some variable violates the regularization constraint, i.e., x^*_i(1-x^*_i) > \tau then solve the rNLP again using its starting solution modified by x_i = 0 if x^*_i > 0.5 and x_i = 1 if x^*_i < 0.5. One possible explanation for this choice is that, assuming x^*_i > 0.5, if really x_i = 1 were a solution, then the NLP solver should not have had troubles pushing x_i towards 1, making at least the regularization constraint feasible. Instead, it might be that there is a solution with x_i = 0, but since x^*_i > 0.5 the NLP solver is having more problems pushing it to 0.
- If the modification of the starting point did not help finding a feasible solution, solve the problem again, but now fixing the problematic variables using the same criteria.
- If still we do not get a feasible solution, abort (note that the paper suggests to backtrack, but this might be just too expensive).
- If the maximum binary infeasibility is small enough, call sub-NLP heuristic with binary variables fixed to the value suggested by x^*.
Definition in file heur_mpec.h.
Go to the source code of this file.
Functions | |
SCIP_RETCODE | SCIPincludeHeurMpec (SCIP *scip) |