SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-2024 Zuse Institute Berlin (ZIB) */
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 benderscut_opt.h
26 * @ingroup BENDERSCUTS
27 * @brief Generates a standard Benders' decomposition optimality cut
28 * @author Stephen J. Maher
29 *
30 * The classical Benders' decomposition optimality cuts arise from a feasible instance of the Benders' decomposition
31 * subproblem. The optimality cuts are an underestimator of the subproblem objective function value. Auxiliary
32 * variables, \f$\varphi\f$ are added to the master problem as a lower bound on the subproblem objective function value.
33 *
34 * Consider a linear Benders' decomposition subproblem that takes the master problem solution \f$\bar{x}\f$ as input:
35 * \f[
36 * z(\bar{x}) = \min\{d^{T}y : Ty \geq h - H\bar{x}, y \geq 0\}
37 * \f]
38 * If the subproblem is feasible, and \f$z(\bar{x}) > \varphi\f$ (indicating that the current underestimators are not
39 * optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the
40 * subproblem. Let \f$w\f$ be the vector corresponding to the optimal dual solution of the Benders' decomposition
41 * subproblem. The resulting cut is:
42 * \f[
43 * \varphi \geq w^{T}(h - Hx)
44 * \f]
45 *
46 * Next, consider a nonlinear Benders' decomposition subproblem that takes the master problem solution \f$\bar{x}\f$ as input:
47 * \f[
48 * z(\bar{x}) = \min\{d^{T}y : g(\bar{x},y) \leq 0, y \geq 0\}
49 * \f]
50 * If the subproblem is feasible, and \f$z(\bar{x}) > \varphi\f$ (indicating that the current underestimators are not
51 * optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the
52 * subproblem. Let \f$w\f$ be the vector corresponding to the optimal dual solution of the Benders' decomposition subproblem.
53 * The resulting cut is:
54 * \f[
55 * \varphi \geq z(\bar{x}) + w^{T} \nabla_x g(\bar{x}, y) (x-\bar{x})
56 * \f]
57 *
58 */
59
60/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
61
62#ifndef __SCIP_BENDERSCUT_OPT_H__
63#define __SCIP_BENDERSCUT_OPT_H__
64
65
66#include "scip/def.h"
67#include "scip/type_benders.h"
69#include "scip/type_cons.h"
70#include "scip/type_lp.h"
71#include "scip/type_misc.h"
72#include "scip/type_nlp.h"
73#include "scip/type_retcode.h"
74#include "scip/type_scip.h"
76
77#ifdef __cplusplus
78extern "C" {
79#endif
80
81/** creates the optimality Benders' decomposition cut and includes it in SCIP
82 *
83 * @ingroup BenderscutIncludes
84 */
85SCIP_EXPORT
87 SCIP* scip, /**< SCIP data structure */
88 SCIP_BENDERS* benders /**< Benders' decomposition */
89 );
90
91/** @addtogroup BENDERSCUTS
92 * @{
93 */
94
95/** Generates a classical Benders' optimality cut using the dual solutions from the subproblem or the input arrays. If
96 * the dual solutions are input as arrays, then a mapping between the array indices and the rows/variables is required.
97 * This method can also be used to generate a feasiblity, is a problem to minimise the infeasibilities has been solved
98 * to generate the dual solutions
99 */
100SCIP_EXPORT
102 SCIP* masterprob, /**< the SCIP instance of the master problem */
103 SCIP* subproblem, /**< the SCIP instance of the pricing problem */
104 SCIP_BENDERS* benders, /**< the benders' decomposition */
105 SCIP_BENDERSCUT* benderscut, /**< the benders' decomposition cut method */
106 SCIP_SOL* sol, /**< primal CIP solution */
107 int probnumber, /**< the number of the pricing problem */
108 char* cutname, /**< the name for the cut to be generated */
109 SCIP_Real objective, /**< the objective function of the subproblem */
110 SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
111 SCIP_Real* consdualvals, /**< dual variables for the constraints, can be NULL */
112 SCIP_Real* varlbdualvals, /**< the dual variables for the variable lower bounds, can be NULL */
113 SCIP_Real* varubdualvals, /**< the dual variables for the variable upper bounds, can be NULL */
114 SCIP_HASHMAP* row2idx, /**< mapping between the row in the subproblem to the index in the dual array, can be NULL */
115 SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
116 SCIP_BENDERSENFOTYPE type, /**< the enforcement type calling this function */
117 SCIP_Bool addcut, /**< should the Benders' cut be added as a cut or constraint */
118 SCIP_Bool feasibilitycut, /**< is this called for the generation of a feasibility cut */
119 SCIP_RESULT* result /**< the result from solving the subproblems */
120 );
121
122/** adds the gradient of a nonlinear row in the current NLP solution of a subproblem to a linear row or constraint in the master problem
123 *
124 * Only computes gradient w.r.t. master problem variables.
125 * Computes also the directional derivative, that is, mult times gradient times solution.
126 */
127SCIP_EXPORT
129 SCIP* masterprob, /**< the SCIP instance of the master problem */
130 SCIP* subproblem, /**< the SCIP instance of the subproblem */
131 SCIP_BENDERS* benders, /**< the benders' decomposition structure */
132 SCIP_NLROW* nlrow, /**< nonlinear row */
133 SCIP_Real mult, /**< multiplier */
134 SCIP_Real* primalvals, /**< the primal solutions for the NLP, can be NULL */
135 SCIP_HASHMAP* var2idx, /**< mapping from variable of the subproblem to the index in the dual arrays, can be NULL */
136 SCIP_Real* dirderiv, /**< storage to add directional derivative */
137 SCIP_VAR*** vars, /**< pointer to array of variables in the generated cut with non-zero coefficient */
138 SCIP_Real** vals, /**< pointer to array of coefficients of the variables in the generated cut */
139 int* nvars, /**< the number of variables in the cut */
140 int* varssize /**< the number of variables in the array */
141 );
142
143/** @} */
144
145#ifdef __cplusplus
146}
147#endif
148
149#endif
common defines and data types used in all packages of SCIP
#define SCIP_Bool
Definition def.h:91
#define SCIP_Real
Definition def.h:172
SCIP_RETCODE SCIPgenerateAndApplyBendersOptCut(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, char *cutname, SCIP_Real objective, SCIP_Real *primalvals, SCIP_Real *consdualvals, SCIP_Real *varlbdualvals, SCIP_Real *varubdualvals, SCIP_HASHMAP *row2idx, SCIP_HASHMAP *var2idx, SCIP_BENDERSENFOTYPE type, SCIP_Bool addcut, SCIP_Bool feasibilitycut, SCIP_RESULT *result)
SCIP_RETCODE SCIPaddNlRowGradientBenderscutOpt(SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_NLROW *nlrow, SCIP_Real mult, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx, SCIP_Real *dirderiv, SCIP_VAR ***vars, SCIP_Real **vals, int *nvars, int *varssize)
SCIP_RETCODE SCIPincludeBenderscutOpt(SCIP *scip, SCIP_BENDERS *benders)
static SCIP_SOL * sol
int nvars
static SCIP_VAR ** vars
type definitions for Benders' decomposition methods
struct SCIP_Benders SCIP_BENDERS
enum SCIP_BendersEnfoType SCIP_BENDERSENFOTYPE
type definitions for Benders' decomposition cut
struct SCIP_Benderscut SCIP_BENDERSCUT
type definitions for constraints and constraint handlers
type definitions for expression interpreter
type definitions for LP management
type definitions for miscellaneous datastructures
struct SCIP_HashMap SCIP_HASHMAP
Definition type_misc.h:105
type definitions for NLP management
struct SCIP_NlRow SCIP_NLROW
Definition type_nlp.h:41
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
type definitions for return codes for SCIP methods
enum SCIP_Retcode SCIP_RETCODE
type definitions for SCIP's main datastructure
struct Scip SCIP
Definition type_scip.h:39
struct SCIP_Sol SCIP_SOL
Definition type_sol.h:57
struct SCIP_Var SCIP_VAR
Definition type_var.h:119