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   branch_mostinf.c
26   	 * @ingroup DEFPLUGINS_BRANCH
27   	 * @brief  most infeasible LP branching rule
28   	 * @author Tobias Achterberg
29   	 */
30   	
31   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32   	
33   	#include "scip/branch_mostinf.h"
34   	#include "scip/pub_branch.h"
35   	#include "scip/pub_message.h"
36   	#include "scip/pub_var.h"
37   	#include "scip/scip_branch.h"
38   	#include "scip/scip_message.h"
39   	#include "scip/scip_numerics.h"
40   	#include "scip/scip_var.h"
41   	#include <string.h>
42   	
43   	
44   	#define BRANCHRULE_NAME          "mostinf"
45   	#define BRANCHRULE_DESC          "most infeasible branching"
46   	#define BRANCHRULE_PRIORITY      100
47   	#define BRANCHRULE_MAXDEPTH      -1
48   	#define BRANCHRULE_MAXBOUNDDIST  1.0
49   	
50   	/*
51   	 * Local methods
52   	 */
53   	
54   	/** compares the so far best branching candidate with a new candidate and updates best candidate, if new candidate is better */
55   	static
56   	void updateBestCandidate(
57   	   SCIP*                 scip,               /**< SCIP data structure */
58   	   SCIP_VAR**            bestvar,            /**< best branching candidate */
59   	   SCIP_Real*            bestscore,          /**< score of best branching candidate */
60   	   SCIP_Real*            bestobj,            /**< absolute objective value of best branching candidate */
61   	   SCIP_Real*            bestsol,            /**< proposed branching point of best branching candidate */
62   	   SCIP_VAR*             cand,               /**< branching candidate to consider */
63   	   SCIP_Real             candscore,          /**< scoring of branching candidate */
64   	   SCIP_Real             candsol             /**< proposed branching point of branching candidate */
65   	   )
66   	{
67   	   SCIP_Real obj;
68   	
69   	   assert(scip != NULL);
70   	   assert(bestvar != NULL);
71   	   assert(bestscore != NULL);
72   	   assert(bestobj != NULL);
73   	   assert(*bestobj >= 0.0);
74   	   assert(cand != NULL);
75   	
76   	   /* a branching variable candidate should either be an active problem variable or a multi-aggregated variable */
77   	   assert(SCIPvarIsActive(SCIPvarGetProbvar(cand)) ||
78   	      SCIPvarGetStatus(SCIPvarGetProbvar(cand)) == SCIP_VARSTATUS_MULTAGGR);
79   	
80   	   if( SCIPvarGetStatus(SCIPvarGetProbvar(cand)) == SCIP_VARSTATUS_MULTAGGR )
81   	   {
82   	      /* for a multi-aggregated variable, we call updateBestCandidate function recursively with all variables in the multi-aggregation */
83   	      SCIP_VAR** multvars;
84   	      int nmultvars;
85   	      int i;
86   	      SCIP_Bool success;
87   	      SCIP_Real multvarlb;
88   	      SCIP_Real multvarub;
89   	
90   	      cand = SCIPvarGetProbvar(cand);
91   	      multvars = SCIPvarGetMultaggrVars(cand);
92   	      nmultvars = SCIPvarGetMultaggrNVars(cand);
93   	
94   	      /* if we have a candidate branching point, then first register only aggregation variables
95   	       * for which we can compute a corresponding branching point too (see also comments below)
96   	       * if this fails, then register all (unfixed) aggregation variables, thereby forgetting about candsol
97   	       */
98   	      success = FALSE;
99   	      if( candsol != SCIP_INVALID ) /*lint !e777*/
100  	      {
101  	         SCIP_Real* multscalars;
102  	         SCIP_Real minact;
103  	         SCIP_Real maxact;
104  	         SCIP_Real aggrvarsol;
105  	         SCIP_Real aggrvarsol1;
106  	         SCIP_Real aggrvarsol2;
107  	
108  	         multscalars = SCIPvarGetMultaggrScalars(cand);
109  	
110  	         /* for computing the branching point, we need the current bounds of the multi-aggregated variable */
111  	         minact = SCIPcomputeVarLbLocal(scip, cand);
112  	         maxact = SCIPcomputeVarUbLocal(scip, cand);
113  	
114  	         for( i = 0; i < nmultvars; ++i )
115  	         {
116  	            /* skip fixed variables */
117  	            multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]);
118  	            multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]);
119  	            if( SCIPisEQ(scip, multvarlb, multvarub) )
120  	               continue;
121  	
122  	            assert(multscalars != NULL);
123  	            assert(multscalars[i] != 0.0);
124  	
125  	            /* we cannot ensure that both the upper bound in the left node and the lower bound in the right node
126  	             * will be candsol by a clever choice for the branching point of multvars[i],
127  	             * but we can try to ensure that at least one of them will be at candsol
128  	             */
129  	            if( multscalars[i] > 0.0 )
130  	            {
131  	               /*    cand >= candsol
132  	                * if multvars[i] >= (candsol - (maxact - multscalars[i] * ub(multvars[i]))) / multscalars[i]
133  	                *                 = (candsol - maxact) / multscalars[i] + ub(multvars[i])
134  	                */
135  	               aggrvarsol1 = (candsol - maxact) / multscalars[i] + multvarub;
136  	
137  	               /*     cand <= candsol
138  	                * if multvars[i] <= (candsol - (minact - multscalar[i] * lb(multvars[i]))) / multscalars[i]
139  	                *                 = (candsol - minact) / multscalars[i] + lb(multvars[i])
140  	                */
141  	               aggrvarsol2 = (candsol - minact) / multscalars[i] + multvarlb;
142  	            }
143  	            else
144  	            {
145  	               /*    cand >= candsol
146  	                * if multvars[i] <= (candsol - (maxact - multscalars[i] * lb(multvars[i]))) / multscalars[i]
147  	                *                 = (candsol - maxact) / multscalars[i] + lb(multvars[i])
148  	                */
149  	               aggrvarsol2 = (candsol - maxact) / multscalars[i] + multvarlb;
150  	
151  	               /*    cand <= candsol
152  	                * if multvars[i] >= (candsol - (minact - multscalar[i] * ub(multvars[i]))) / multscalars[i]
153  	                *                 = (candsol - minact) / multscalars[i] + ub(multvars[i])
154  	                */
155  	               aggrvarsol1 = (candsol - minact) / multscalars[i] + multvarub;
156  	            }
157  	
158  	            /* by the above choice, aggrvarsol1 <= ub(multvars[i]) and aggrvarsol2 >= lb(multvars[i])
159  	             * if aggrvarsol1 <= lb(multvars[i]) or aggrvarsol2 >= ub(multvars[i]), then choose the other one
160  	             * if both are out of bounds, then give up
161  	             * if both are inside bounds, then choose the one closer to 0.0 (someone has better idea???)
162  	             */
163  	            if( SCIPisFeasLE(scip, aggrvarsol1, multvarlb) )
164  	            {
165  	               if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) )
166  	                  continue;
167  	               else
168  	                  aggrvarsol = aggrvarsol2;
169  	            }
170  	            else
171  	            {
172  	               if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) )
173  	                  aggrvarsol = aggrvarsol1;
174  	               else
175  	                  aggrvarsol = REALABS(aggrvarsol1) < REALABS(aggrvarsol2) ? aggrvarsol1 : aggrvarsol2;
176  	            }
177  	            success = TRUE;
178  	
179  	            updateBestCandidate(scip, bestvar, bestscore, bestobj, bestsol,
180  	                  multvars[i], candscore, aggrvarsol);
181  	         }
182  	      }
183  	
184  	      if( !success )
185  	         for( i = 0; i < nmultvars; ++i )
186  	         {
187  	            /* skip fixed variables */
188  	            multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]);
189  	            multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]);
190  	            if( SCIPisEQ(scip, multvarlb, multvarub) )
191  	               continue;
192  	
193  	            updateBestCandidate(scip, bestvar, bestscore, bestobj, bestsol,
194  	               multvars[i], candscore, SCIP_INVALID);
195  	         }
196  	
197  	      assert(*bestvar != NULL); /* if all variables were fixed, something is strange */
198  	
199  	      return;
200  	   }
201  	
202  	   candscore *= SCIPvarGetBranchFactor(cand);
203  	   obj = SCIPvarGetObj(cand);
204  	   obj = REALABS(obj);
205  	   if( SCIPisInfinity(scip, candscore)
206  	      || (!SCIPisInfinity(scip, *bestscore) && 
207  	          (SCIPisGT(scip, candscore, *bestscore) || (SCIPisGE(scip, candscore, *bestscore) && obj > *bestobj))) )
208  	   {
209  	      *bestvar = cand;
210  	      *bestscore = candscore;
211  	      *bestobj = obj;
212  	      *bestsol = candsol;
213  	   }
214  	}
215  	
216  	/*
217  	 * Callback methods
218  	 */
219  	
220  	/** copy method for branchrule plugins (called when SCIP copies plugins) */
221  	static
222  	SCIP_DECL_BRANCHCOPY(branchCopyMostinf)
223  	{  /*lint --e{715}*/
224  	   assert(scip != NULL);
225  	   assert(branchrule != NULL);
226  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
227  	
228  	   /* call inclusion method of branchrule */
229  	   SCIP_CALL( SCIPincludeBranchruleMostinf(scip) );
230  	
231  	   return SCIP_OKAY;
232  	}
233  	
234  	
235  	/** branching execution method for fractional LP solutions */
236  	static
237  	SCIP_DECL_BRANCHEXECLP(branchExeclpMostinf)
238  	{  /*lint --e{715}*/
239  	   SCIP_VAR** lpcands;
240  	   SCIP_Real* lpcandsfrac;
241  	   int nlpcands;
242  	   SCIP_Real infeasibility;
243  	   SCIP_Real score;
244  	   SCIP_Real obj;
245  	   SCIP_Real bestscore;
246  	   SCIP_Real bestobj;
247  	   int bestcand;
248  	   int i;
249  	
250  	   assert(branchrule != NULL);
251  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
252  	   assert(scip != NULL);
253  	   assert(result != NULL);
254  	
255  	   SCIPdebugMsg(scip, "Execlp method of mostinf branching\n");
256  	
257  	   /* get branching candidates */
258  	   SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, NULL, &lpcandsfrac, NULL, &nlpcands, NULL) );
259  	   assert(nlpcands > 0);
260  	
261  	   /* search the most infeasible candidate */
262  	   bestscore = SCIP_REAL_MIN;
263  	   bestobj = 0.0;
264  	   bestcand = -1;
265  	   for( i = 0; i < nlpcands; ++i )
266  	   {
267  	      assert(lpcands[i] != NULL);
268  	
269  	      infeasibility = lpcandsfrac[i];
270  	      infeasibility = MIN(infeasibility, 1.0-infeasibility);
271  	      score = infeasibility;
272  	      score *= SCIPvarGetBranchFactor(lpcands[i]);
273  	      obj = SCIPvarGetObj(lpcands[i]);
274  	      obj = REALABS(obj);
275  	      if( SCIPisGT(scip, score, bestscore)
276  	         || (SCIPisGE(scip, score, bestscore) && obj > bestobj) )
277  	      {
278  	         bestscore = score;
279  	         bestobj = obj;
280  	         bestcand = i;
281  	      }
282  	   }
283  	   assert(bestcand >= 0);
284  	
285  	   SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (frac=%g, obj=%g, factor=%g, score=%g)\n",
286  	      nlpcands, bestcand, SCIPvarGetName(lpcands[bestcand]), lpcandsfrac[bestcand], bestobj,
287  	      SCIPvarGetBranchFactor(lpcands[bestcand]), bestscore);
288  	
289  	   /* perform the branching */
290  	   SCIP_CALL( SCIPbranchVar(scip, lpcands[bestcand], NULL, NULL, NULL) );
291  	   *result = SCIP_BRANCHED;
292  	
293  	   return SCIP_OKAY;
294  	}
295  	
296  	/** branching execution method for external candidates */
297  	static
298  	SCIP_DECL_BRANCHEXECEXT(branchExecextMostinf)
299  	{  /*lint --e{715}*/
300  	   SCIP_VAR** externcands;
301  	   SCIP_Real* externcandssol;
302  	   SCIP_Real* externcandsscore;
303  	   int nexterncands;
304  	   SCIP_VAR* bestcand;
305  	   SCIP_Real bestscore;
306  	   SCIP_Real bestobj;
307  	   SCIP_Real bestsol;
308  	   SCIP_Real brpoint;
309  	   int i;
310  	   SCIP_NODE* downchild;
311  	   SCIP_NODE* eqchild;
312  	   SCIP_NODE* upchild;
313  	
314  	   assert(branchrule != NULL);
315  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
316  	   assert(scip != NULL);
317  	   assert(result != NULL);
318  	
319  	   SCIPdebugMsg(scip, "Execext method of mostinf branching\n");
320  	
321  	   /* get branching candidates */
322  	   SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, &externcandsscore, NULL, &nexterncands, NULL, NULL, NULL) );
323  	   assert(nexterncands > 0);
324  	
325  	   /* search the most infeasible candidate */
326  	   bestscore = SCIP_REAL_MIN;
327  	   bestobj = 0.0;
328  	   bestcand = NULL;
329  	   bestsol = SCIP_INVALID;
330  	   for( i = 0; i < nexterncands; ++i )
331  	   {
332  	      updateBestCandidate(scip, &bestcand, &bestscore, &bestobj, &bestsol, externcands[i], externcandsscore[i], externcandssol[i]);
333  	   }
334  	
335  	   if( bestcand == NULL )
336  	   {
337  	      SCIPerrorMessage("branchExecextMostinf failed to select a branching variable from %d candidates\n", nexterncands);
338  	      *result = SCIP_DIDNOTRUN;
339  	      return SCIP_OKAY;
340  	   }
341  	
342  	   brpoint = SCIPgetBranchingPoint(scip, bestcand, bestsol);
343  	
344  	   SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s> (sol=%g, locdom=[%g,%g], obj=%g, factor=%g, score=%g), branching point=%g\n",
345  	      nexterncands, SCIPvarGetName(bestcand), bestsol, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand), bestobj,
346  	      SCIPvarGetBranchFactor(bestcand), bestscore, brpoint);
347  	
348  	   /* perform the branching */
349  	   SCIP_CALL( SCIPbranchVarVal(scip, bestcand, brpoint, &downchild, &eqchild, &upchild) );
350  	
351  	   if( downchild != NULL || eqchild != NULL || upchild != NULL )
352  	   {
353  	      *result = SCIP_BRANCHED;
354  	   }
355  	   else
356  	   {
357  	      /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
358  	      assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestcand), SCIPvarGetUbLocal(bestcand)));
359  	      *result = SCIP_REDUCEDDOM;
360  	   }
361  	
362  	   return SCIP_OKAY;
363  	}
364  	
365  	
366  	/*
367  	 * branching specific interface methods
368  	 */
369  	
370  	/** creates the most infeasible LP branching rule and includes it in SCIP */
371  	SCIP_RETCODE SCIPincludeBranchruleMostinf(
372  	   SCIP*                 scip                /**< SCIP data structure */
373  	   )
374  	{
375  	   SCIP_BRANCHRULE* branchrule;
376  	
377  	   /* include branching rule */
378  	   SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
379  	         BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, NULL) );
380  	
381  	   assert(branchrule != NULL);
382  	
383  	   /* set non-fundamental callbacks via specific setter functions*/
384  	   SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyMostinf) );
385  	   SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpMostinf) );
386  	   SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextMostinf) );
387  	
388  	   return SCIP_OKAY;
389  	}
390