Scippy

SCIP

Solving Constraint Integer Programs

presol_inttobinary.c
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_inttobinary.c
17  * @ingroup DEFPLUGINS_PRESOL
18  * @brief presolver that converts integer variables with domain [a,a+1] to binaries
19  * @author Tobias Achterberg
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "blockmemshell/memory.h"
25 #include "scip/debug.h"
27 #include "scip/pub_message.h"
28 #include "scip/pub_misc.h"
29 #include "scip/pub_presol.h"
30 #include "scip/pub_var.h"
31 #include "scip/scip_mem.h"
32 #include "scip/scip_message.h"
33 #include "scip/scip_numerics.h"
34 #include "scip/scip_presol.h"
35 #include "scip/scip_prob.h"
36 #include "scip/scip_var.h"
37 #include <string.h>
38 
39 #define PRESOL_NAME "inttobinary"
40 #define PRESOL_DESC "converts integer variables with domain [a,a+1] to binaries"
41 #define PRESOL_PRIORITY +7000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
42 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
43 #define PRESOL_TIMING SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
44 
45 /*
46  * Callback methods of presolver
47  */
48 
49 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
50 static
51 SCIP_DECL_PRESOLCOPY(presolCopyInttobinary)
52 { /*lint --e{715}*/
53  assert(scip != NULL);
54  assert(presol != NULL);
55  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
56 
57  /* call inclusion method of presolver */
59 
60  return SCIP_OKAY;
61 }
62 
63 
64 /** presolving execution method */
65 static
66 SCIP_DECL_PRESOLEXEC(presolExecInttobinary)
67 { /*lint --e{715}*/
68  SCIP_VAR** scipvars;
69  SCIP_VAR** vars;
70  int nbinvars;
71  int nintvars;
72  int v;
73 
74  assert(result != NULL);
75 
76  *result = SCIP_DIDNOTRUN;
77 
78  if( SCIPdoNotAggr(scip) )
79  return SCIP_OKAY;
80 
81  /* get the problem variables */
82  scipvars = SCIPgetVars(scip);
83  nbinvars = SCIPgetNBinVars(scip);
84  nintvars = SCIPgetNIntVars(scip);
85  if( nintvars == 0 )
86  return SCIP_OKAY;
87 
88  *result = SCIP_DIDNOTFIND;
89 
90  /* copy the integer variables into an own array, since adding binary variables affects the left-most slots in the
91  * array and thereby interferes with our search loop
92  */
93  SCIP_CALL( SCIPduplicateBufferArray(scip, &vars, &scipvars[nbinvars], nintvars) );
94 
95  /* scan the integer variables for possible conversion into binaries */
96  for( v = 0; v < nintvars; ++v )
97  {
98  SCIP_Real lb;
99  SCIP_Real ub;
100 
101  assert(SCIPvarGetType(vars[v]) == SCIP_VARTYPE_INTEGER);
102 
103  /* get variable's bounds */
104  lb = SCIPvarGetLbGlobal(vars[v]);
105  ub = SCIPvarGetUbGlobal(vars[v]);
106 
107  /* check if bounds are exactly one apart; if the lower bound is too large, aggregations will be rejected */
108  if( SCIPisEQ(scip, lb, ub - 1.0) && !SCIPisHugeValue(scip, REALABS(lb) / SCIPfeastol(scip)) )
109  {
110  SCIP_VAR* binvar;
111  char binvarname[SCIP_MAXSTRLEN];
112  SCIP_Bool infeasible;
113  SCIP_Bool redundant;
114  SCIP_Bool aggregated;
115 
116  SCIPdebugMsg(scip, "converting <%s>[%g,%g] into binary variable\n", SCIPvarGetName(vars[v]), lb, ub);
117 
118  /* create binary variable */
119  (void) SCIPsnprintf(binvarname, SCIP_MAXSTRLEN, "%s_bin", SCIPvarGetName(vars[v]));
120  SCIP_CALL( SCIPcreateVar(scip, &binvar, binvarname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
121  SCIPvarIsInitial(vars[v]), SCIPvarIsRemovable(vars[v]), NULL, NULL, NULL, NULL, NULL) );
122  SCIP_CALL( SCIPaddVar(scip, binvar) );
123 
124  /* set up debug solution */
125 #ifdef WITH_DEBUG_SOLUTION
127  {
128  SCIP_SOL* debugsol;
129 
130  SCIP_CALL( SCIPdebugGetSol(scip, &debugsol) );
131 
132  /* set solution value in the debug solution if it is available */
133  if( debugsol != NULL )
134  {
135  SCIP_Real val;
136  SCIP_CALL( SCIPdebugGetSolVal(scip, vars[v], &val) );
137  SCIP_CALL( SCIPdebugAddSolVal(scip, binvar, val - lb) );
138  }
139  }
140 #endif
141 
142  /* aggregate integer and binary variable */
143  SCIP_CALL( SCIPaggregateVars(scip, vars[v], binvar, 1.0, -1.0, lb, &infeasible, &redundant, &aggregated) );
144 
145  /* release binary variable */
146  SCIP_CALL( SCIPreleaseVar(scip, &binvar) );
147 
148  /* it can be the case that this aggregation detects an infeasibility; for example, during the copy of the
149  * variable bounds from the integer variable to the binary variable, infeasibility can be detected; this can
150  * happen because an upper bound or a lower bound of such a variable bound variable was "just" changed and the
151  * varbound constraint handler, who would detect that infeasibility (since it was creating it from a varbound
152  * constraint), was called before that bound change was detected due to the presolving priorities;
153  */
154  if( infeasible )
155  {
156  *result = SCIP_CUTOFF;
157  break;
158  }
159  else if( aggregated )
160  {
161  assert(redundant);
162 
163  (*nchgvartypes)++;
164  ++(*naggrvars);
165  *result = SCIP_SUCCESS;
166  }
167  }
168  }
169 
170  /* free temporary memory */
171  SCIPfreeBufferArray(scip, &vars);
172 
173  return SCIP_OKAY;
174 }
175 
176 
177 /*
178  * presolver specific interface methods
179  */
180 
181 /** creates the inttobinary presolver and includes it in SCIP */
183  SCIP* scip /**< SCIP data structure */
184  )
185 {
186  SCIP_PRESOLDATA* presoldata;
187  SCIP_PRESOL* presolptr;
188 
189  /* create inttobinary presolver data */
190  presoldata = NULL;
191 
192  /* include presolver */
194  presolExecInttobinary,
195  presoldata) );
196 
197  assert(presolptr != NULL);
198 
199  SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyInttobinary) );
200 
201  return SCIP_OKAY;
202 }
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip_presol.c:96
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2080
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:42
SCIP_Real SCIPfeastol(SCIP *scip)
public methods for memory management
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
#define SCIP_MAXSTRLEN
Definition: def.h:293
#define PRESOL_DESC
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition: var.c:17452
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
public methods for presolving plugins
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
public methods for problem variables
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:123
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition: var.c:17462
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:69
static SCIP_DECL_PRESOLEXEC(presolExecInttobinary)
public methods for numerical tolerances
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:201
#define SCIP_CALL(x)
Definition: def.h:384
#define PRESOL_TIMING
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:281
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:84
#define PRESOL_NAME
#define PRESOL_PRIORITY
methods for debugging
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:590
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:105
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2035
public methods for presolvers
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1666
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:131
public methods for message output
#define PRESOL_MAXROUNDS
static SCIP_DECL_PRESOLCOPY(presolCopyInttobinary)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1945
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8398
#define SCIP_Real
Definition: def.h:177
SCIP_RETCODE SCIPincludePresolInttobinary(SCIP *scip)
public methods for message handling
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip_var.c:8562
presolver that converts integer variables with domain [a,a+1] to binaries
#define SCIPdebugAddSolVal(scip, var, val)
Definition: debug.h:280
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
#define SCIPdebugSolIsEnabled(scip)
Definition: debug.h:285
public methods for global and local (sub)problems
memory allocation routines