Scippy

SCIP

Solving Constraint Integer Programs

benderscut_feasalt.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_feasalt.h
17  * @ingroup BENDERSCUTS
18  * @brief Alternative feasibility cuts for Benders' decomposition
19  * @author Stephen J. Maher
20  *
21  * The alternative feasibility cut for Benders' decomposition uses the optimality cut generation code to generate a cut
22  * that minimises the violation of the constraints.
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 some of the constraints are violated.
28  * In this case, we define an alternative/auxiliary subproblem to find a solution that minimises the constraint
29  * violations. Such a problem is given by
30  * \f[
31  * \min\{\mathbb{1}{T}v : Ty + v \geq h - H\bar{x}, y \geq 0, v \geq 0\}
32  * \f]
33  *
34  * This auxiliary problem is guaranteed to always be feasible. Given a solution to this problem, it is possible to
35  * generate a classical Benders' optimality cut. For such a cut, the reader is referred to \ref benderscut_opt.h.
36  *
37  * If the Benders' decomposition subproblem contains non-linear constraints, an equivalent auxiliary subproblem can be
38  * formed to generate an alternative feasibility cut.
39  */
40 
41 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42 
43 #ifndef __SCIP_BENDERSCUT_FEASALT_H__
44 #define __SCIP_BENDERSCUT_FEASALT_H__
45 
46 
47 #include "scip/def.h"
48 #include "scip/type_benders.h"
49 #include "scip/type_retcode.h"
50 #include "scip/type_scip.h"
51 
52 #ifdef __cplusplus
53 extern "C" {
54 #endif
55 
56 /** creates the Alternative Feasibility Benders' decomposition cuts and includes it in SCIP
57  *
58  * @ingroup BenderscutIncludes
59  */
60 SCIP_EXPORT
62  SCIP* scip, /**< SCIP data structure */
63  SCIP_BENDERS* benders /**< Benders' decomposition */
64  );
65 
66 #ifdef __cplusplus
67 }
68 #endif
69 
70 #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 SCIPincludeBenderscutFeasalt(SCIP *scip, SCIP_BENDERS *benders)
type definitions for Benders&#39; decomposition methods
common defines and data types used in all packages of SCIP