Scippy

SCIP

Solving Constraint Integer Programs

benderscut_nogood.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-2021 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file benderscut_nogood.h
17  * @ingroup BENDERSCUTS
18  * @brief Generates a no-good cut for solutions that are integer infeasible
19  * @author Stephen J. Maher
20  *
21  * The no-good cut is generated for the Benders' decomposition master problem if an integer solution is identified as
22  * infeasible in at least one CIP subproblems. The no-good cut is required, because the classical Benders' decomposition
23  * feasibility cuts (see benderscut_feas.c) will only cut off the solution \f$\bar{x}\f$ if the LP relaxation of the CIP
24  * is infeasible.
25  *
26  * Consider a Benders' decomposition subproblem that is a CIP and it infeasible. Let \f$S_{r}\f$ be the set of indices
27  * for master problem variables that are 1 in \f$\bar{x}\f$. The no-good cut is given by
28  *
29  * \f[
30  * 1 \leq \sum_{i \in S_{r}}(1 - x_{i}) + \sum_{i \notin S_{r}}x_{i}
31  * \f]
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #ifndef __SCIP_BENDERSCUT_NOGOOD_H__
37 #define __SCIP_BENDERSCUT_NOGOOD_H__
38 
39 
40 #include "scip/def.h"
41 #include "scip/type_benders.h"
42 #include "scip/type_retcode.h"
43 #include "scip/type_scip.h"
44 
45 #ifdef __cplusplus
46 extern "C" {
47 #endif
48 
49 /** creates the no good Benders' decomposition cut and includes it in SCIP
50  *
51  * @ingroup BenderscutIncludes
52  */
55  SCIP* scip, /**< SCIP data structure */
56  SCIP_BENDERS* benders /**< Benders' decomposition */
57  );
58 
59 #ifdef __cplusplus
60 }
61 #endif
62 
63 #endif
SCIP_EXPORT SCIP_RETCODE SCIPincludeBenderscutNogood(SCIP *scip, SCIP_BENDERS *benders)
#define SCIP_EXPORT
Definition: def.h:100
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
type definitions for Benders&#39; decomposition methods
common defines and data types used in all packages of SCIP