Scippy

SCIP

Solving Constraint Integer Programs

presol_dualsparsify.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_dualsparsify.h
17  * @brief cancel nonzeros of the constraint matrix based on the columns
18  * @author Dieter Weninger
19  * @author Leona Gottwald
20  * @author Ambros Gleixner
21  * @author Weikun Chen
22  *
23  * This presolver attempts to cancel non-zero entries of the constraint
24  * matrix by adding scaled columns to other columns.
25  *
26  * In more detail, for two columns A_{j.} and A_{k.}, suppose for a given value s, we have
27  *
28  * | A_{j.} | - | A_{j.} - s*A_{k.} | > eta,
29  *
30  * where eta is an nonnegative integer. Then we introduce a new variable y := s*x_j + x_k
31  * and aggregate the variable x_k = y - s*x_j. After aggregation, the column of the variable
32  * x_j is A_{j.} + s*A_{j.} which is sparser than A_{j.}. In the case that x_k is no implied
33  * free variable, we need to add a new constraint l_k <= y - weight*x_j <= u_k into the problem
34  * to keep the bounds constraints of variable x_k.
35  *
36  * Further information can be found in
37  * Chen et al. "Two-row and two-column mixed-integer presolve using hasing-based pairing methods".
38  *
39  * @todo add infrastructure to SCIP for handling aggregated binary variables
40  */
41 
42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43 
44 #ifndef __SCIP_PRESOL_DUALSPARSIFY_H__
45 #define __SCIP_PRESOL_DUALSPARSIFY_H__
46 
47 #include "scip/def.h"
48 #include "scip/type_retcode.h"
49 #include "scip/type_scip.h"
50 
51 #ifdef __cplusplus
52 extern "C" {
53 #endif
54 
55 /** creates the dual sparsify presolver and includes it in SCIP */
56 SCIP_EXPORT
58  SCIP* scip /**< SCIP data structure */
59  );
60 
61 #ifdef __cplusplus
62 }
63 #endif
64 
65 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for return codes for SCIP methods
SCIP_RETCODE SCIPincludePresolDualsparsify(SCIP *scip)
type definitions for SCIP&#39;s main datastructure
common defines and data types used in all packages of SCIP