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