Scippy

SCIP

Solving Constraint Integer Programs

cons_benders.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 cons_benders.h
17  * @ingroup CONSHDLRS
18  * @brief constraint handler for Benders' decomposition
19  * @author Stephen J. Maher
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_CONS_BENDERS_H__
25 #define __SCIP_CONS_BENDERS_H__
26 
27 
28 #include "scip/def.h"
29 #include "scip/type_benders.h"
30 #include "scip/type_cons.h"
31 #include "scip/type_result.h"
32 #include "scip/type_retcode.h"
33 #include "scip/type_scip.h"
34 #include "scip/type_sol.h"
35 
36 #ifdef __cplusplus
37 extern "C" {
38 #endif
39 
40 /** creates the handler for Benders' decomposition and includes it in SCIP
41  *
42  * @ingroup ConshdlrIncludes
43  * */
44 extern
46  SCIP* scip /**< SCIP data structure */
47  );
48 
49 /**@addtogroup CONSHDLRS
50  *
51  * @{
52  *
53  * @name Benders Constraints
54  *
55  * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a
56  * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation
57  * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with
58  * respect to the subproblem constraints.
59  *
60  * This constraint handler has an enforcement priority that is less than the integer constraint handler. This means that
61  * only integer feasible solutions from the LP solver are enforced by this constraint handler. This is the traditional
62  * behaviour of the branch-and-check approach to Benders' decomposition. Additionally, the check priority is set low,
63  * such that this expensive constraint handler is only called as a final check on primal feasible solutions.
64  *
65  * This constraint handler in the standard constraint handler that should be added when using Benders' decomposition.
66  * Additionally, there is a flag in SCIPincludeConshdlrBenders that permits the addition of the LP constraint handler,
67  * cons_benderslp. The use of both cons_benders and cons_benderslp allows the user to perform a multiphase Benders'
68  * decomposition algorithm.
69  *
70  * @{
71  */
72 
73 /** enforces Benders' constraints for given solution
74  *
75  * This method is called from cons_benderslp and cons_benders. If the method is called from cons_benderslp, then the
76  * solutions are not guaranteed to be integer feasible. This is because the default priority is set greater than the
77  * integer constraint handler. If this method is called from cons_benders, then, because the default enforcement
78  * priority is set less than that of the integer constraint handler, then it can be assumed that the solutions are
79  * integer feasible.
80  *
81  * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
82  * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
83  * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
84  * solution feasibility.
85  */
86 extern
88  SCIP* scip, /**< the SCIP instance */
89  SCIP_SOL* sol, /**< the primal solution to enforce, or NULL for the current LP/pseudo sol */
90  SCIP_CONSHDLR* conshdlr, /**< the constraint handler */
91  SCIP_RESULT* result, /**< the result of the enforcement */
92  SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
93  SCIP_Bool checkint /**< should integrality be considered when checking the subproblems */
94  );
95 
96 /* @} */
97 
98 /* @} */
99 
100 #ifdef __cplusplus
101 }
102 #endif
103 
104 #endif
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPconsBendersEnforceSolution(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: cons_benders.c:222
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:42
type definitions for return codes for SCIP methods
SCIP_RETCODE SCIPincludeConshdlrBenders(SCIP *scip)
Definition: cons_benders.c:647
type definitions for SCIP&#39;s main datastructure
#define SCIP_Bool
Definition: def.h:69
type definitions for Benders&#39; decomposition methods
type definitions for storing primal CIP solutions
result codes for SCIP callback methods
common defines and data types used in all packages of SCIP
type definitions for constraints and constraint handlers