Scippy

SCIP

Solving Constraint Integer Programs

benderscut_opt.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-2018 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_opt.h
17  * @ingroup BENDERSCUTS
18  * @brief Generates a standard Benders' decomposition optimality cut
19  * @author Stephen J. Maher
20  *
21  * The classical Benders' decomposition optimality cuts arise from a feasible instance of the Benders' decomposition
22  * subproblem. The optimality cuts are an underestimator of the subproblem objective function value. Auxiliary
23  * variables, \f$\varphi\f$ are added to the master problem as alower bound on the subproblem objective function value.
24  *
25  * Consider the Benders' decomposition subproblem that takes the master problem solution \f$\bar{x}\f$ as input:
26  * \f[
27  * z(\bar{x}) = \min\{d^{T}y : Ty \geq h - H\bar{x}, y \geq 0\}
28  * \f]
29  * If the subproblem is feasible, and \f$z(\bar{x}) > \varphi\f$ (indicating that the current underestimators are not
30  * optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the
31  * subproblem. Let \f$w\f$ be the vector corresponding to the optimal dual solution of the Benders' decomposition
32  * subproblem. The resulting cut is:
33  * \f[
34  * \varphi \geq w^{T}(h - Hx)
35  * \f]
36  *
37  */
38 
39 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40 
41 #ifndef __SCIP_BENDERSCUT_OPT_H__
42 #define __SCIP_BENDERSCUT_OPT_H__
43 
44 
45 #include "scip/def.h"
46 #include "scip/type_benders.h"
47 #include "scip/type_retcode.h"
48 #include "scip/type_scip.h"
49 
50 #ifdef __cplusplus
51 extern "C" {
52 #endif
53 
54 /** creates the optimality Benders' decomposition cut and includes it in SCIP
55  *
56  * @ingroup BenderscutIncludes
57  */
58 extern
60  SCIP* scip, /**< SCIP data structure */
61  SCIP_BENDERS* benders /**< Benders' decomposition */
62  );
63 
64 /* @} */
65 
66 /* @} */
67 
68 #ifdef __cplusplus
69 }
70 #endif
71 
72 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
type definitions for Benders&#39; decomposition methods
SCIP_RETCODE SCIPincludeBenderscutOpt(SCIP *scip, SCIP_BENDERS *benders)
common defines and data types used in all packages of SCIP