Processing math: 100%
Scippy

SCIP

Solving Constraint Integer Programs

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/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)