heur_mpec.h File Reference

Detailed Description

mpec primal heuristic

Author

Felipe Serrano

Benjamin Mueller

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/scip.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeHeurMpec (SCIP *scip)