Scippy

SCIP

Solving Constraint Integer Programs

presol_tworowbnd.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-2022 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 presol_tworowbnd.h
17  * @ingroup DEFPLUGINS_PRESOL
18  * @brief do bound tightening by using two rows
19  * @author Dieter Weninger
20  * @author Patrick Gemander
21  *
22  * Perform bound tightening on two inequalities with some common variables.
23  * Two possible methods are being used.
24  *
25  * 1. LP-bound
26  * Let two constraints be given:
27  * \f{eqnarray*}{
28  * A_{iR} x_R + A_{iS} x_S \geq b_i\\
29  * A_{kR} x_R + A_{kT} x_T \geq b_k
30  * \f}
31  * with \f$N\f$ the set of variable indexes, \f$R \subseteq N\f$, \f$S \subseteq N\f$, \f$T \subseteq N\f$,
32  * \f$R \cap S = \emptyset\f$, \f$R \cap T = \emptyset\f$, \f$S \cap T = \emptyset\f$ and row indices \f$i \not= k\f$.
33  *
34  * Let \f$\ell\f$ and \f$u\f$ be bound vectors for x and solve the following two LPs
35  * \f{eqnarray*}{
36  * L = \min \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \}\\
37  * U = \max \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i, \ell \leq x \leq u \}
38  * \f}
39  * and use \f$L\f$ and \f$U\f$ for getting bounds on \f$x_T\f$.
40  *
41  * If \f$L + \mbox{infimum}(A_{kT}x_T) \geq b_k\f$, then the second constraint above is redundant.
42  *
43  * 2. ConvComb with clique-extension
44  * Given two constraints
45  * \f{eqnarray*}{
46  * A_{i\cdot} x \geq b_i \\
47  * A_{k\cdot} x \geq b_k \\
48  * \ell \leq x \leq u \\
49  * \f}
50  * this method determines promising values for \f$\lambda \in (0,1)\f$ and
51  * applies feasibility-based bound tightening to the convex combinations
52  *
53  * \f$(\lambda A_{i\cdot} + (1 - \lambda) A_{k\cdot}) x \geq \lambda b_i + (1 - \lambda) b_k\f$.
54  *
55  * Additionally, cliques drawn from the SCIPcliqueTable are used
56  * to further strengthen the above bound tightening. Full details can be found in
57  * - Belotti P. "Bound reduction using pairs of linear inequalities"
58  * - Chen W. et. al "Two-row and two-column mixed-integer presolve using hashing-based pairing methods"
59  */
60 
61 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62 
63 #ifndef __SCIP_PRESOL_TWOROWBND_H__
64 #define __SCIP_PRESOL_TWOROWBND_H__
65 
66 #include "scip/def.h"
67 #include "scip/type_retcode.h"
68 #include "scip/type_scip.h"
69 
70 #ifdef __cplusplus
71 extern "C" {
72 #endif
73 
74 /** creates the tworowbnd presolver and includes it in SCIP
75  *
76  * @ingroup PresolverIncludes
77  */
78 SCIP_EXPORT
80  SCIP* scip /**< SCIP data structure */
81  );
82 
83 #ifdef __cplusplus
84 }
85 #endif
86 
87 #endif
SCIP_RETCODE SCIPincludePresolTworowbnd(SCIP *scip)
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
common defines and data types used in all packages of SCIP