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-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 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 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  */
35 
36 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37 
38 #ifndef __SCIP_BENDERSCUT_FEAS_H__
39 #define __SCIP_BENDERSCUT_FEAS_H__
40 
41 
42 #include "scip/def.h"
43 #include "scip/type_benders.h"
44 #include "scip/type_retcode.h"
45 #include "scip/type_scip.h"
46 
47 #ifdef __cplusplus
48 extern "C" {
49 #endif
50 
51 /** creates the Standard Feasibility Benders' decomposition cuts and includes it in SCIP
52  *
53  * @ingroup BenderscutIncludes
54  */
57  SCIP* scip, /**< SCIP data structure */
58  SCIP_BENDERS* benders /**< Benders' decomposition */
59  );
60 
61 #ifdef __cplusplus
62 }
63 #endif
64 
65 #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
SCIP_EXPORT SCIP_RETCODE SCIPincludeBenderscutFeas(SCIP *scip, SCIP_BENDERS *benders)
type definitions for SCIP&#39;s main datastructure
type definitions for Benders&#39; decomposition methods
common defines and data types used in all packages of SCIP