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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file cons_benders.h
26  * @ingroup CONSHDLRS
27  * @brief constraint handler for Benders' decomposition
28  * @author Stephen J. Maher
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __SCIP_CONS_BENDERS_H__
34 #define __SCIP_CONS_BENDERS_H__
35 
36 
37 #include "scip/def.h"
38 #include "scip/type_benders.h"
39 #include "scip/type_cons.h"
40 #include "scip/type_result.h"
41 #include "scip/type_retcode.h"
42 #include "scip/type_scip.h"
43 #include "scip/type_sol.h"
44 
45 #ifdef __cplusplus
46 extern "C" {
47 #endif
48 
49 /** creates the handler for Benders' decomposition and includes it in SCIP
50  *
51  * @ingroup ConshdlrIncludes
52  * */
53 SCIP_EXPORT
55  SCIP* scip /**< SCIP data structure */
56  );
57 
58 /**@addtogroup CONSHDLRS
59  *
60  * @{
61  *
62  * @name Benders Constraints
63  *
64  * Two constraint handlers are implemented for the generation of Benders' decomposition cuts. When included in a
65  * problem, the Benders' decomposition constraint handlers generate cuts during the enforcement of LP and relaxation
66  * solutions. Additionally, Benders' decomposition cuts can be generated when checking the feasibility of solutions with
67  * respect to the subproblem constraints.
68  *
69  * This constraint handler has an enforcement priority that is less than the integer constraint handler. This means that
70  * only integer feasible solutions from the LP solver are enforced by this constraint handler. This is the traditional
71  * behaviour of the branch-and-check approach to Benders' decomposition. Additionally, the check priority is set low,
72  * such that this expensive constraint handler is only called as a final check on primal feasible solutions.
73  *
74  * This constraint handler in the standard constraint handler that should be added when using Benders' decomposition.
75  * Additionally, there is a flag in SCIPincludeConshdlrBenders that permits the addition of the LP constraint handler,
76  * cons_benderslp. The use of both cons_benders and cons_benderslp allows the user to perform a multiphase Benders'
77  * decomposition algorithm.
78  *
79  * @{
80  */
81 
82 /** enforces Benders' constraints for given solution
83  *
84  * This method is called from cons_benderslp and cons_benders. If the method is called from cons_benderslp, then the
85  * solutions are not guaranteed to be integer feasible. This is because the default priority is set greater than the
86  * integer constraint handler. If this method is called from cons_benders, then, because the default enforcement
87  * priority is set less than that of the integer constraint handler, then it can be assumed that the solutions are
88  * integer feasible.
89  *
90  * The checkint flag indicates whether integer feasibility can be assumed. If it is not assumed, i.e. checkint ==
91  * FALSE, then only the convex relaxations of the subproblems are solved. If integer feasibility is assumed, i.e.
92  * checkint == TRUE, then the convex relaxations and the full CIP are solved to generate Benders' cuts and check
93  * solution feasibility.
94  */
95 SCIP_EXPORT
97  SCIP* scip, /**< the SCIP instance */
98  SCIP_SOL* sol, /**< the primal solution to enforce, or NULL for the current LP/pseudo sol */
99  SCIP_CONSHDLR* conshdlr, /**< the constraint handler */
100  SCIP_RESULT* result, /**< the result of the enforcement */
101  SCIP_BENDERSENFOTYPE type, /**< the type of solution being enforced */
102  SCIP_Bool checkint /**< should integrality be considered when checking the subproblems */
103  );
104 
105 /** @} */
106 
107 /** @} */
108 
109 #ifdef __cplusplus
110 }
111 #endif
112 
113 #endif
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
SCIP_RETCODE SCIPconsBendersEnforceSolution(SCIP *scip, SCIP_SOL *sol, SCIP_CONSHDLR *conshdlr, SCIP_RESULT *result, SCIP_BENDERSENFOTYPE type, SCIP_Bool checkint)
Definition: cons_benders.c:261
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
Definition: type_benders.h:51
type definitions for return codes for SCIP methods
SCIP_RETCODE SCIPincludeConshdlrBenders(SCIP *scip)
Definition: cons_benders.c:769
type definitions for SCIP&#39;s main datastructure
#define SCIP_Bool
Definition: def.h:93
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