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-2024 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
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) */
59static
60SCIP_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 */
74static
75SCIP_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 */
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}
methods for debugging
#define SCIPdebugGetSolVal(scip, var, val)
Definition: debug.h:299
#define SCIPdebugAddSolVal(scip, var, val)
Definition: debug.h:298
#define SCIPdebugSolIsEnabled(scip)
Definition: debug.h:303
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludePresolInttobinary(SCIP *scip)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
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
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition: var.c:17620
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip_var.c:8565
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
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition: var.c:17630
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
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
memory allocation routines
static SCIP_DECL_PRESOLCOPY(presolCopyInttobinary)
#define PRESOL_NAME
static SCIP_DECL_PRESOLEXEC(presolExecInttobinary)
#define PRESOL_PRIORITY
#define PRESOL_MAXROUNDS
#define PRESOL_TIMING
#define PRESOL_DESC
presolver that converts integer variables with domain [a,a+1] to binaries
public methods for message output
public data structures and miscellaneous methods
public methods for presolvers
public methods for problem variables
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for presolving plugins
public methods for global and local (sub)problems
public methods for SCIP variables
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:51
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62