SCIP

Solving Constraint Integer Programs

heur_mpec.h File Reference

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.

#include "scip/def.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPincludeHeurMpec (SCIP *scip)