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   cons_integral.c
26   	 * @ingroup DEFPLUGINS_CONS
27   	 * @brief  constraint handler for the integrality constraint
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/cons_integral.h"
34   	#include "scip/pub_cons.h"
35   	#include "scip/pub_message.h"
36   	#include "scip/pub_var.h"
37   	#include "scip/scip_branch.h"
38   	#include "scip/scip_cons.h"
39   	#include "scip/scip_lp.h"
40   	#include "scip/scip_message.h"
41   	#include "scip/scip_numerics.h"
42   	#include "scip/scip_prob.h"
43   	#include "scip/scip_probing.h"
44   	#include "scip/scip_sol.h"
45   	#include <string.h>
46   	
47   	
48   	#define CONSHDLR_NAME          "integral"
49   	#define CONSHDLR_DESC          "integrality constraint"
50   	#define CONSHDLR_ENFOPRIORITY         0 /**< priority of the constraint handler for constraint enforcing */
51   	#define CONSHDLR_CHECKPRIORITY        0 /**< priority of the constraint handler for checking feasibility */
52   	#define CONSHDLR_EAGERFREQ           -1 /**< frequency for using all instead of only the useful constraints in separation,
53   	                                              *   propagation and enforcement, -1 for no eager evaluations, 0 for first only */
54   	#define CONSHDLR_NEEDSCONS        FALSE /**< should the constraint handler be skipped, if no constraints are available? */
55   	
56   	/*
57   	 * Callback methods
58   	 */
59   	
60   	/** copy method for constraint handler plugins (called when SCIP copies plugins) */
61   	static
62   	SCIP_DECL_CONSHDLRCOPY(conshdlrCopyIntegral)
63   	{  /*lint --e{715}*/
64   	   assert(scip != NULL);
65   	   assert(conshdlr != NULL);
66   	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
67   	
68   	   /* call inclusion method of constraint handler */
69   	   SCIP_CALL( SCIPincludeConshdlrIntegral(scip) );
70   	
71   	   *valid = TRUE;
72   	
73   	   return SCIP_OKAY;
74   	}
75   	
76   	#define consCopyIntegral NULL
77   	
78   	#define consEnfopsIntegral NULL
79   	
80   	/** constraint enforcing method of constraint handler for LP solutions */
81   	static
82   	SCIP_DECL_CONSENFOLP(consEnfolpIntegral)
83   	{  /*lint --e{715}*/
84   	   assert(conshdlr != NULL);
85   	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
86   	   assert(scip != NULL);
87   	   assert(conss == NULL);
88   	   assert(nconss == 0);
89   	   assert(result != NULL);
90   	
91   	   SCIPdebugMsg(scip, "Enfolp method of integrality constraint: %d fractional variables\n", SCIPgetNLPBranchCands(scip));
92   	
93   	   /* if the root LP is unbounded, we want to terminate with UNBOUNDED or INFORUNBOUNDED,
94   	    * depending on whether we are able to construct an integral solution; in any case we do not want to branch
95   	    */
96   	   if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_UNBOUNDEDRAY )
97   	   {
98   	      if( SCIPgetNLPBranchCands(scip) == 0 )
99   	         *result = SCIP_FEASIBLE;
100  	      else
101  	         *result = SCIP_INFEASIBLE;
102  	      return SCIP_OKAY;
103  	   }
104  	
105  	   /* call branching methods */
106  	   SCIP_CALL( SCIPbranchLP(scip, result) );
107  	
108  	   /* if no branching was done, the LP solution was not fractional */
109  	   if( *result == SCIP_DIDNOTRUN )
110  	      *result = SCIP_FEASIBLE;
111  	
112  	   return SCIP_OKAY;
113  	}
114  	
115  	/** constraint enforcing method of constraint handler for relaxation solutions */
116  	static
117  	SCIP_DECL_CONSENFORELAX(consEnforelaxIntegral)
118  	{  /*lint --e{715}*/
119  	   SCIP_VAR** vars;
120  	   int nbinvars;
121  	   int nintvars;
122  	   int i;
123  	
124  	   assert(conshdlr != NULL);
125  	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
126  	   assert(scip != NULL);
127  	   assert(conss == NULL);
128  	   assert(nconss == 0);
129  	   assert(result != NULL);
130  	
131  	   SCIPdebugMsg(scip, "Enforelax method of integrality constraint\n");
132  	
133  	   *result = SCIP_FEASIBLE;
134  	
135  	   SCIP_CALL( SCIPgetVarsData(scip, &vars, NULL, &nbinvars, &nintvars, NULL, NULL) );
136  	
137  	   for( i = 0; i < nbinvars + nintvars; ++i )
138  	   {
139  	      assert(vars[i] != NULL);
140  	      assert(SCIPvarIsIntegral(vars[i]));
141  	
142  	      if( !SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars[i])) )
143  	      {
144  	         if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])) )
145  	         {
146  	            SCIPdebugMsg(scip, "Cutoff for integral variable %s with bounds [%f, %f] and value %f\n", SCIPvarGetName(vars[i]),
147  	                  SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i]), SCIPgetSolVal(scip, sol, vars[i]));
148  	            *result = SCIP_CUTOFF;
149  	            return SCIP_OKAY;
150  	         }
151  	         else
152  	         {
153  	            /* @todo better way to handle this would be a BRANCHEXECRELAX callback that could also implement pseudo costs for
154  	             * relaxation solutions instead of using the enforelaxcallback which is mainly intended for spatial branching
155  	             */
156  	            SCIP_CALL( SCIPaddExternBranchCand(scip, vars[i], 0.2, SCIPgetSolVal(scip, sol, vars[i])) );
157  	            *result = SCIP_INFEASIBLE;
158  	         }
159  	      }
160  	   }
161  	
162  	   /* if we have found a branching candidate, immediately branch to be able to return SCIP_BRANCHED and stop the
163  	    * enforcement loop
164  	    */
165  	   if( *result == SCIP_INFEASIBLE )
166  	   {
167  	      /* call branching methods for external candidates */
168  	      SCIP_CALL( SCIPbranchExtern(scip, result) );
169  	
170  	      /* since we only call it if we added external candidates, the branching rule should always be able to branch */
171  	      assert(*result != SCIP_DIDNOTRUN);
172  	   }
173  	
174  	   return SCIP_OKAY;
175  	}
176  	
177  	/** feasibility check method of constraint handler for integral solutions */
178  	static
179  	SCIP_DECL_CONSCHECK(consCheckIntegral)
180  	{  /*lint --e{715}*/
181  	   SCIP_VAR** vars;
182  	   SCIP_Real solval;
183  	   int ninteger;
184  	   int nbin;
185  	   int nint;
186  	   int nimpl;
187  	   int v;
188  	
189  	   assert(conshdlr != NULL);
190  	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
191  	   assert(scip != NULL);
192  	
193  	   SCIPdebugMsg(scip, "Check method of integrality constraint (checkintegrality=%u)\n", checkintegrality);
194  	
195  	   SCIP_CALL( SCIPgetSolVarsData(scip, sol, &vars, NULL, &nbin, &nint, &nimpl, NULL) );
196  	
197  	   *result = SCIP_FEASIBLE;
198  	
199  	   if( !checkintegrality )
200  	      return SCIP_OKAY;
201  	
202  	   ninteger = nbin + nint;
203  	
204  	   for( v = 0; v < ninteger; ++v )
205  	   {
206  	      solval = SCIPgetSolVal(scip, sol, vars[v]);
207  	
208  	      if( sol != NULL )
209  	         SCIPupdateSolIntegralityViolation(scip, sol, EPSFRAC(solval, SCIPfeastol(scip)));
210  	
211  	      if( !SCIPisFeasIntegral(scip, solval) )
212  	      {
213  	         *result = SCIP_INFEASIBLE;
214  	
215  	         if( printreason )
216  	         {
217  	            SCIPinfoMessage(scip, NULL, "violation: integrality condition of variable <%s> = %.15g\n",
218  	               SCIPvarGetName(vars[v]), solval);
219  	         }
220  	         if( !completely )
221  	            break;
222  	      }
223  	   }
224  	
225  	   return SCIP_OKAY;
226  	}
227  	
228  	/** variable rounding lock method of constraint handler */
229  	static
230  	SCIP_DECL_CONSLOCK(consLockIntegral)
231  	{  /*lint --e{715}*/
232  	   return SCIP_OKAY;
233  	}
234  	
235  	/** constraint handler method to suggest dive bound changes during the generic diving algorithm */
236  	static
237  	SCIP_DECL_CONSGETDIVEBDCHGS(consGetDiveBdChgsIntegral)
238  	{  /*lint --e{715}*/
239  	   SCIP_VAR** vars;
240  	   SCIP_Real solval;
241  	   SCIP_Real score;
242  	   SCIP_Real bestscore;
243  	   SCIP_Bool bestroundup;
244  	   int ninteger;
245  	   int nbin;
246  	   int nint;
247  	   int nimpl;
248  	   int v;
249  	   int bestcandidx;
250  	
251  	   assert(scip != NULL);
252  	   assert(sol != NULL);
253  	   assert(diveset != NULL);
254  	
255  	   assert(conshdlr != NULL);
256  	   assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
257  	   assert(scip != NULL);
258  	
259  	   SCIPdebugMsg(scip, "integral constraint handler: determine diving bound changes\n");
260  	
261  	   SCIP_CALL( SCIPgetSolVarsData(scip, sol, &vars, NULL, &nbin, &nint, &nimpl, NULL) );
262  	
263  	   ninteger = nbin + nint + nimpl;
264  	   bestscore = SCIP_REAL_MIN;
265  	   bestcandidx = -1;
266  	   *success = FALSE;
267  	   bestroundup = FALSE; /* only for lint */
268  	
269  	   /* loop over solution values and get score of fractional variables */
270  	   for( v = 0; v < ninteger; ++v )
271  	   {
272  	      solval = SCIPgetSolVal(scip, sol, vars[v]);
273  	
274  	      /* skip variable if solution value disagrees with the local bounds */
275  	      if( ! SCIPisFeasIntegral(scip, solval) && SCIPisGE(scip, solval, SCIPvarGetLbLocal(vars[v])) && SCIPisLE(scip, solval, SCIPvarGetUbLocal(vars[v])) )
276  	      {
277  	         SCIP_Bool roundup;
278  	
279  	         SCIP_CALL( SCIPgetDivesetScore(scip, diveset, SCIP_DIVETYPE_INTEGRALITY, vars[v], solval,
280  	               solval - SCIPfloor(scip, solval), &score, &roundup) );
281  	
282  	         /* we search for candidates with maximum score */
283  	         if( score > bestscore )
284  	         {
285  	            bestcandidx = v;
286  	            bestscore = score;
287  	            bestroundup = roundup;
288  	            *success = TRUE;
289  	         }
290  	      }
291  	   }
292  	
293  	   assert(!(*success) || bestcandidx >= 0);
294  	
295  	   if( *success )
296  	   {
297  	      solval = SCIPgetSolVal(scip, sol, vars[bestcandidx]);
298  	
299  	      /* if we want to round up the best candidate, it is added as the preferred bound change */
300  	      SCIP_CALL( SCIPaddDiveBoundChange(scip, vars[bestcandidx], SCIP_BRANCHDIR_UPWARDS,
301  	            SCIPceil(scip, solval), bestroundup) );
302  	      SCIP_CALL( SCIPaddDiveBoundChange(scip, vars[bestcandidx], SCIP_BRANCHDIR_DOWNWARDS,
303  	            SCIPfloor(scip, solval), ! bestroundup) );
304  	   }
305  	
306  	   return SCIP_OKAY;
307  	}
308  	
309  	/*
310  	 * constraint specific interface methods
311  	 */
312  	
313  	/** creates the handler for integrality constraint and includes it in SCIP */
314  	SCIP_RETCODE SCIPincludeConshdlrIntegral(
315  	   SCIP*                 scip                /**< SCIP data structure */
316  	   )
317  	{
318  	   SCIP_CONSHDLR* conshdlr;
319  	
320  	   /* include constraint handler */
321  	   SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
322  	         CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
323  	         consEnfolpIntegral, consEnfopsIntegral, consCheckIntegral, consLockIntegral, NULL) );
324  	
325  	   assert(conshdlr != NULL);
326  	
327  	   /* set non-fundamental callbacks via specific setter functions */
328  	   SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyIntegral, consCopyIntegral) );
329  	   SCIP_CALL( SCIPsetConshdlrGetDiveBdChgs(scip, conshdlr, consGetDiveBdChgsIntegral) );
330  	   SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxIntegral) );
331  	
332  	   return SCIP_OKAY;
333  	}
334