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