SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
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
61{ /*lint --e{715}*/
62 assert(scip != NULL);
63 assert(presol != NULL);
65
66 /* call inclusion method of presolver */
68
69 return SCIP_OKAY;
70}
71
72
73/** presolving execution method */
74static
76{ /*lint --e{715}*/
78 SCIP_VAR** vars;
79 int nbinvars;
80 int nintvars;
81 int v;
82
83 assert(result != NULL);
84
86
87 if( SCIPdoNotAggr(scip) )
88 return SCIP_OKAY;
89
90 /* get the problem variables */
94 if( nintvars == 0 )
95 return SCIP_OKAY;
96
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 */
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
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;
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 */
129 SCIP_CALL( SCIPcreateVar(scip, &binvar, binvarname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
131 SCIP_CALL( SCIPaddVar(scip, binvar) );
132
133 /* set up debug solution */
134#ifdef WITH_DEBUG_SOLUTION
136 {
138
140
141 /* set solution value in the debug solution if it is available */
142 if( debugsol != NULL )
143 {
144 SCIP_Real 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 {
166 break;
167 }
168 else if( aggregated )
169 {
170 assert(redundant);
171
172 (*nchgvartypes)++;
173 ++(*naggrvars);
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;
197
198 /* create inttobinary presolver data */
199 presoldata = NULL;
200
201 /* include presolver */
204 presoldata) );
205
207
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 SCIP_MAXSTRLEN
Definition def.h:302
#define REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
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
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_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)
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:17442
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:17406
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:17910
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1248
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition var.c:17452
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:17900
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_VAR ** vars
int nbinvars
int nintvars
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
#define PRESOL_NAME
#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
#define SCIP_DECL_PRESOLCOPY(x)
Definition type_presol.h:60
struct SCIP_PresolData SCIP_PRESOLDATA
Definition type_presol.h:51
#define SCIP_DECL_PRESOLEXEC(x)
@ 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
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_INTEGER
Definition type_var.h:63
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62