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_trivial.c
26   	 * @ingroup DEFPLUGINS_PRESOL
27   	 * @brief  trivial presolver: round fractional bounds on integer variables, fix variables with equal bounds
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/presol_trivial.h"
34   	#include "scip/pub_message.h"
35   	#include "scip/pub_presol.h"
36   	#include "scip/pub_var.h"
37   	#include "scip/scip_message.h"
38   	#include "scip/scip_numerics.h"
39   	#include "scip/scip_presol.h"
40   	#include "scip/scip_prob.h"
41   	#include "scip/scip_var.h"
42   	#include <string.h>
43   	
44   	#define PRESOL_NAME            "trivial"
45   	#define PRESOL_DESC            "round fractional bounds on integers, fix variables with equal bounds"
46   	#define PRESOL_PRIORITY        +9000000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
47   	#define PRESOL_MAXROUNDS             -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
48   	#define PRESOL_TIMING           SCIP_PRESOLTIMING_FAST /* timing of the presolver (fast, medium, or exhaustive) */
49   	
50   	#ifdef FIXSIMPLEVALUE
51   	#define MAXDNOM                 10000LL /**< maximal denominator for simple rational fixed values */
52   	#endif
53   	
54   	
55   	/*
56   	 * Callback methods of presolver
57   	 */
58   	
59   	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
60   	static
61   	SCIP_DECL_PRESOLCOPY(presolCopyTrivial)
62   	{  /*lint --e{715}*/
63   	   assert(scip != NULL);
64   	   assert(presol != NULL);
65   	   assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
66   	
67   	   /* call inclusion method of presolver */
68   	   SCIP_CALL( SCIPincludePresolTrivial(scip) );
69   	
70   	   return SCIP_OKAY;
71   	}
72   	
73   	
74   	/** presolving execution method */
75   	static
76   	SCIP_DECL_PRESOLEXEC(presolExecTrivial)
77   	{  /*lint --e{715}*/
78   	   SCIP_VAR** vars;
79   	   int nvars;
80   	   int v;
81   	
82   	   assert(result != NULL);
83   	
84   	   *result = SCIP_DIDNOTFIND;
85   	
86   	   /* get the problem variables */
87   	   vars = SCIPgetVars(scip);
88   	   nvars = SCIPgetNVars(scip);
89   	
90   	   /* scan the variables for trivial bound reductions
91   	    * (loop backwards, since a variable fixing can change the current and the subsequent slots in the vars array)
92   	    */
93   	   for( v = nvars-1; v >= 0; --v )
94   	   {
95   	      SCIP_Real lb;
96   	      SCIP_Real ub;
97   	      SCIP_Bool infeasible;
98   	      SCIP_Bool fixed;
99   	
100  	      /* get variable's bounds */
101  	      lb = SCIPvarGetLbGlobal(vars[v]);
102  	      ub = SCIPvarGetUbGlobal(vars[v]);
103  	
104  	      /* is variable integral? */
105  	      if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS )
106  	      {
107  	         SCIP_Real newlb;
108  	         SCIP_Real newub;
109  	
110  	         /* round fractional bounds on integer variables */
111  	         newlb = SCIPfeasCeil(scip, lb);
112  	         newub = SCIPfeasFloor(scip, ub);
113  	
114  	         /* check bounds on variable for infeasibility */
115  	         if( newlb > newub + 0.5 )
116  	         {
117  	            SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
118  	               "problem infeasible: integral variable <%s> has bounds [%.17f,%.17f] rounded to [%.17f,%.17f]\n",
119  	               SCIPvarGetName(vars[v]), lb, ub, newlb, newub);
120  	            *result = SCIP_CUTOFF;
121  	            return SCIP_OKAY;
122  	         }
123  	
124  	         /* fix variables with equal bounds */
125  	         if( newlb > newub - 0.5 )
126  	         {
127  	            SCIPdebugMsg(scip, "fixing integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n", SCIPvarGetName(vars[v]), lb, ub, newlb, newub);
128  	            SCIP_CALL( SCIPfixVar(scip, vars[v], newlb, &infeasible, &fixed) );
129  	            if( infeasible )
130  	            {
131  	               SCIPdebugMsg(scip, " -> infeasible fixing\n");
132  	               *result = SCIP_CUTOFF;
133  	               return SCIP_OKAY;
134  	            }
135  	            assert(fixed);
136  	            (*nfixedvars)++;
137  	         }
138  	         else
139  	         {
140  	            /* round fractional bounds */
141  	            if( !SCIPisFeasEQ(scip, lb, newlb) )
142  	            {
143  	               SCIPdebugMsg(scip, "rounding lower bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n",
144  	                  SCIPvarGetName(vars[v]), lb, ub, newlb, ub);
145  	               SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlb) );
146  	               (*nchgbds)++;
147  	            }
148  	            if( !SCIPisFeasEQ(scip, ub, newub) )
149  	            {
150  	               SCIPdebugMsg(scip, "rounding upper bound of integral variable <%s>: [%.17f,%.17f] -> [%.17f,%.17f]\n",
151  	                  SCIPvarGetName(vars[v]), newlb, ub, newlb, newub);
152  	               SCIP_CALL( SCIPchgVarUb(scip, vars[v], newub) );
153  	               (*nchgbds)++;
154  	            }
155  	         }
156  	      }
157  	      else
158  	      {
159  	         /* check bounds on continuous variable for infeasibility */
160  	         if( SCIPisFeasGT(scip, lb, ub) )
161  	         {
162  	            SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
163  	               "problem infeasible: continuous variable <%s> has bounds [%.17f,%.17f]\n",
164  	               SCIPvarGetName(vars[v]), lb, ub);
165  	            *result = SCIP_CUTOFF;
166  	            return SCIP_OKAY;
167  	         }
168  	
169  	         /* fix variables with equal bounds */
170  	         if( SCIPisEQ(scip, lb, ub) )
171  	         {
172  	            SCIP_Real fixval;
173  	
174  	#ifdef FIXSIMPLEVALUE
175  	            fixval = SCIPselectSimpleValue(lb - 0.9 * SCIPepsilon(scip), ub + 0.9 * SCIPepsilon(scip), MAXDNOM);
176  	#else
177  	            /* prefer integral values (especially 0) over midpoint */
178  	            fixval = SCIPround(scip, lb);
179  	            if( fixval < lb || fixval > ub )
180  	               fixval = (lb + ub)/2;
181  	#endif
182  	            SCIPdebugMsg(scip, "fixing continuous variable <%s>[%.17f,%.17f] to %.17f\n", SCIPvarGetName(vars[v]), lb, ub, fixval);
183  	            SCIP_CALL( SCIPfixVar(scip, vars[v], fixval, &infeasible, &fixed) );
184  	            if( infeasible )
185  	            {
186  	               SCIPdebugMsg(scip, " -> infeasible fixing\n");
187  	               *result = SCIP_CUTOFF;
188  	               return SCIP_OKAY;
189  	            }
190  	            assert(fixed);
191  	            (*nfixedvars)++;
192  	         }
193  	      }
194  	   }
195  	
196  	   return SCIP_OKAY;
197  	}
198  	
199  	
200  	/*
201  	 * presolver specific interface methods
202  	 */
203  	
204  	/** creates the trivial presolver and includes it in SCIP */
205  	SCIP_RETCODE SCIPincludePresolTrivial(
206  	   SCIP*                 scip                /**< SCIP data structure */
207  	   )
208  	{
209  	   SCIP_PRESOL* presolptr;
210  	
211  	   /* include presolver */
212  	   SCIP_CALL( SCIPincludePresolBasic(scip, &presolptr, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING, presolExecTrivial, NULL) );
213  	
214  	   assert(presolptr != NULL);
215  	
216  	   SCIP_CALL( SCIPsetPresolCopy(scip, presolptr, presolCopyTrivial) );
217  	
218  	   return SCIP_OKAY;
219  	}
220