Scippy

SCIP

Solving Constraint Integer Programs

heur_mpec.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_mpec.h
17  * @ingroup PRIMALHEURISTICS
18  * @brief mpec primal heuristic
19  * @author Felipe Serrano
20  * @author Benjamin Mueller
21  *
22  * This heuristic is based on the paper:
23  * @par
24  * Lars Schewe and Martin Schmidt@n
25  * [Computing Feasible Points for MINLPs with MPECs](http://www.optimization-online.org/DB_HTML/2016/12/5778.html)
26  *
27  * An MPEC is a mathematical program with complementarity constraint.
28  * For example, the constraint \f$x \in \{0, 1\}\f$ as \f$x (1-x) = 0\f$
29  * can be modeled as complementarity constraint \f$x = 0\f$ or \f$x = 1\f$.
30  *
31  * This heuristic applies only to mixed binary nonlinear problems.
32  * The idea is to rewrite the MBNLP as MPEC and solve the MPEC instead (to a
33  * a local optimum) by replacing each integrality constraint by the
34  * complementarity constraint \f$x = 0\f$ or \f$x = 1\f$.
35  * In principle, this MPEC can be reformulated to a NLP by rewriting this
36  * constraint as equation \f$x (1-x) = 0\f$.
37  * However, solving this NLP reformulation with a generic NLP solver will
38  * often fail. One issue is that the reformulated complementarity constraints
39  * will not, in general, satisfy constraint qualifications (for instance,
40  * Slater's conditions, which requires the existence of a relative interior
41  * point, will not be satisfied).
42  * In order to increase the chances of solving the NLP reformulation of
43  * the MPEC by a NLP solver, the heuristic applies a regularization
44  * (proposed by Scholtes): it relaxes \f$x(1-x) = 0\f$ to
45  * \f$x(1-x) \leq \theta\f$.
46  *
47  * So the heuristic proceeds as follows.
48  * - Build the regularized NLP (rNLP) with a starting \f$\theta \in (0, \tfrac{1}{4}\f$.
49  * - Give the current LP solution as starting point to the NLP solver.
50  * - Solves rNLP and let \f$x^*\f$ be the best point found (if there is no point, abort).
51  * - If feasible, then reduce \f$\theta\f$ by a factor \f$\sigma\f$ and use
52  * its solution as the starting point for the next iteration.
53  *
54  * - If the rNLP is found infeasible, but the regularization constraints are feasible, abort.
55  *
56  * - If some variable violates the regularization constraint, i.e.,
57  * \f$x^*_i(1-x^*_i) > \tau\f$ then solve the rNLP again using its starting solution
58  * modified by \f$x_i = 0\f$ if \f$x^*_i > 0.5\f$ and \f$x_i = 1\f$ if \f$x^*_i < 0.5\f$.
59  * One possible explanation for this choice is that, assuming \f$x^*_i > 0.5\f$,
60  * if really \f$x_i = 1\f$ were a solution, then the NLP solver should not have had troubles
61  * pushing \f$x_i\f$ towards 1, making at least the regularization constraint feasible.
62  * Instead, it might be that there is a solution with \f$x_i = 0\f$, but since \f$x^*_i > 0.5\f$
63  * the NLP solver is having more problems pushing it to 0.
64  *
65  * - If the modification of the starting point did not help finding a feasible solution,
66  * solve the problem again, but now fixing the problematic variables using the same criteria.
67  *
68  * - If still we do not get a feasible solution, abort (note that the paper suggests to backtrack,
69  * but this might be just too expensive).
70  *
71  * - If the maximum binary infeasibility is small enough, call sub-NLP heuristic
72  * with binary variables fixed to the value suggested by \f$x^*\f$.
73  */
74 
75 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
76 
77 #ifndef __SCIP_HEUR_MPEC_H__
78 #define __SCIP_HEUR_MPEC_H__
79 
80 #include "scip/def.h"
81 #include "scip/type_retcode.h"
82 #include "scip/type_scip.h"
83 
84 #ifdef __cplusplus
85 extern "C" {
86 #endif
87 
88 /** creates the mpec primal heuristic and includes it in SCIP
89  *
90  * @ingroup PrimalHeuristicIncludes
91  */
94  SCIP* scip /**< SCIP data structure */
95  );
96 
97 #ifdef __cplusplus
98 }
99 #endif
100 
101 #endif
#define SCIP_EXPORT
Definition: def.h:98
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
SCIP_EXPORT SCIP_RETCODE SCIPincludeHeurMpec(SCIP *scip)
Definition: heur_mpec.c:726
common defines and data types used in all packages of SCIP