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
102  	SCIP_RETCODE SCIPincludeHeurMpec(
103  	   SCIP*                 scip                /**< SCIP data structure */
104  	   );
105  	
106  	#ifdef __cplusplus
107  	}
108  	#endif
109  	
110  	#endif
111