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