Scippy

SCIP

Solving Constraint Integer Programs

benderscut_feas.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-2022 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file benderscut_feas.h
17  * @ingroup BENDERSCUTS
18  * @brief Standard feasibility cuts for Benders' decomposition
19  * @author Stephen J. Maher
20  *
21  * The classical Benders' decomposition feasibility cuts arise from an infeasible instance of the Benders' decomposition
22  * subproblem.
23  * Consider the linear Benders' decomposition subproblem that takes the master problem solution \f$\bar{x}\f$ as input:
24  * \f[
25  * z(\bar{x}) = \min\{d^{T}y : Ty \geq h - H\bar{x}, y \geq 0\}
26  * \f]
27  * If the subproblem is infeasible as a result of the solution \f$\bar{x}\f$, then the Benders' decomposition
28  * feasibility cut can be generated from the dual ray. Let \f$w\f$ be the vector corresponding to the dual ray of the
29  * Benders' decomposition subproblem. The resulting cut is:
30  * \f[
31  * 0 \geq w^{T}(h - Hx)
32  * \f]
33  *
34  * Next, consider the nonlinear Benders' decomposition subproblem that takes the master problem solution \f$\bar{x}\f$ as input:
35  * \f[
36  * z(\bar{x}) = \min\{d^{T}y : g(\bar{x}, y) \leq 0, y \geq 0\}
37  * \f]
38  * If the subproblem is infeasible as a result of the solution \f$\bar{x}\f$, then the Benders' decomposition
39  * feasibility cut can be generated from a minimal infeasible solution, i.e., a solution of the NLP
40  * \f[
41  * \min\left\{\sum_i u_i : g(\bar{x}, y) \leq u, y \geq 0, u \geq 0\right\}
42  * \f]
43  * Let \f$\bar{y}\f$, \f$w\f$ be the vectors corresponding to the primal and dual solution of this auxiliary NLP.
44  * The resulting cut is:
45  * \f[
46  * 0 \geq w^{T}\left(g(\bar{x},\bar{y}) + \nabla_x g(\bar{x},\bar{y}) (x - \bar{x})\right)
47  * \f]
48  * Note, that usually NLP solvers already provide a minimal infeasible solution when declaring the Benders'
49  * decomposition subproblem as infeasible.
50  */
51 
52 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
53 
54 #ifndef __SCIP_BENDERSCUT_FEAS_H__
55 #define __SCIP_BENDERSCUT_FEAS_H__
56 
57 
58 #include "scip/def.h"
59 #include "scip/type_benders.h"
60 #include "scip/type_retcode.h"
61 #include "scip/type_scip.h"
62 
63 #ifdef __cplusplus
64 extern "C" {
65 #endif
66 
67 /** creates the Standard Feasibility Benders' decomposition cuts and includes it in SCIP
68  *
69  * @ingroup BenderscutIncludes
70  */
71 SCIP_EXPORT
73  SCIP* scip, /**< SCIP data structure */
74  SCIP_BENDERS* benders /**< Benders' decomposition */
75  );
76 
77 #ifdef __cplusplus
78 }
79 #endif
80 
81 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPincludeBenderscutFeas(SCIP *scip, SCIP_BENDERS *benders)
type definitions for Benders&#39; decomposition methods
common defines and data types used in all packages of SCIP