Scippy

SCIP

Solving Constraint Integer Programs

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 MinIISC/src/benders.h
26  * @brief run Benders algorithm
27  * @author Marc Pfetsch
28  *
29  * Run Benders algorithm using an oracle for solving the subproblems and solving the master problem to optimality.
30  */
31 
32 #ifndef __BENDERS_H__
33 #define __BENDERS_H__
34 
35 #include <scip/scip.h>
36 
37 #ifdef __cplusplus
38 extern "C" {
39 #endif
40 
41 /** Benders subproblem oracle solving status */
43 {
44  BENDERS_STATUS_UNKNOWN = 0, /**< the solving status is not yet known */
45  BENDERS_STATUS_ADDEDCUT = 1, /**< a Benders cut has been added */
46  BENDERS_STATUS_SUCESS = 2, /**< the solution is optimal, no further Benders cut has to be generated */
47  BENDERS_STATUS_TIMELIMIT = 3, /**< the time limit has been reached */
48  BENDERS_STATUS_USERINTERRUPT = 4, /**< the user has interrupted the solution of the subproblem */
49  BENDERS_STATUS_ERROR = 5 /**< an error occured during the solution of the subproblem */
50 };
52 
53 typedef struct BENDERS_Data BENDERS_DATA; /**< user defined data to pass to the oracle */
54 
55 /** user callback method for a Benders subproblem oracle
56  * input:
57  * - masterscip: SCIP pointer of Benders master problem
58  * - nmastervars: number of variables in master problem
59  * - mastervars: variables in master problem
60  * - mastersolution: solution of Benders master problem
61  * - data: user data for oracle
62  * - timelimit: time limit for subproblem
63  * - ntotalcuts: total number of cuts
64  * output:
65  * - ncuts: number of cuts added
66  * - status: status
67  *
68  * The oracle should take the given solution and possibly add a Benders Cut to the master problem.
69  */
70 #define BENDERS_CUTORACLE(x) SCIP_RETCODE x (SCIP* masterscip, int nmastervars, SCIP_VAR** mastervars, SCIP_Real* mastersolution, BENDERS_DATA* data, SCIP_Real timelimit, SCIP_Longint ntotalcuts, int* ncuts, BENDERS_STATUS* status)
71 
72 
73 
74 /** run Benders algorithm using an oracle for the subproblems */
76  SCIP* masterscip, /**< master SCIP instance */
77  BENDERS_CUTORACLE((*Oracle)), /**< oracle for the Benders subproblem */
78  BENDERS_DATA* data, /**< user data for oracle */
79  SCIP_Real timelimit, /**< time limit read from arguments */
80  SCIP_Real memlimit, /**< memory limit read from arguments */
81  int dispfreq, /**< display frequency */
82  SCIP_Bool usereopt, /**< use reoptimization */
83  SCIP_Bool solvemasterapprox, /**< Solve master problem approximately? */
84  SCIP_Longint masterstallnodes, /**< stall nodes for master problem if solvemasterapprox is true */
85  SCIP_Real mastergaplimit, /**< gap limit for master problem if solvemasterapprox is true */
86  SCIP_VERBLEVEL verblevel, /**< verbosity level for output */
87  SCIP_STATUS* status /**< status of optimization */
88  );
89 
90 #ifdef __cplusplus
91 }
92 #endif
93 
94 #endif
#define BENDERS_CUTORACLE(x)
Definition: benders.h:70
SCIP_RETCODE runBenders(SCIP *masterscip, BENDERS_CUTORACLE((*Oracle)), BENDERS_DATA *data, SCIP_Real timelimit, SCIP_Real memlimit, int dispfreq, SCIP_Bool usereopt, SCIP_Bool solvemasterapprox, SCIP_Longint masterstallnodes, SCIP_Real mastergaplimit, SCIP_VERBLEVEL verblevel, SCIP_STATUS *status)
Definition: benders.c:207
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
enum SCIP_VerbLevel SCIP_VERBLEVEL
Definition: type_message.h:57
BENDERS_Status
Definition: benders.h:42
#define SCIP_Bool
Definition: def.h:93
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:67
enum BENDERS_Status BENDERS_STATUS
Definition: benders.h:51
#define SCIP_Real
Definition: def.h:186
#define SCIP_Longint
Definition: def.h:171
SCIP callable library.