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   misc_linear.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  miscellaneous methods for linear constraints
28   	 * @author Jakob Witzig
29   	 * @author Ambros Gleixner
30   	 */
31   	
32   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33   	
34   	#include <assert.h>
35   	#include <string.h>
36   	
37   	#include "scip/def.h"
38   	#include "scip/scip.h"
39   	#include "scip/pub_misc_linear.h"
40   	#include "scip/cons_setppc.h"
41   	#include "scip/scipdefplugins.h"
42   	
43   	
44   	/** returns the right-hand side of an arbitrary SCIP constraint that can be represented as a single linear constraint
45   	 *
46   	 *  @note The success pointer indicates if the individual contraint handler was able to return the involved values
47   	 */
48   	SCIP_Real SCIPconsGetRhs(
49   	   SCIP*                 scip,               /**< SCIP data structure */
50   	   SCIP_CONS*            cons,               /**< constraint for which right-hand side is queried */
51   	   SCIP_Bool*            success             /**< pointer to store whether a valid right-hand side was returned */
52   	   )
53   	{
54   	   SCIP_CONSHDLR* conshdlr;
55   	   const char* conshdlrname;
56   	   SCIP_Real rhs;
57   	
58   	   assert(scip != NULL);
59   	   assert(cons != NULL);
60   	   assert(success != NULL);
61   	
62   	   conshdlr = SCIPconsGetHdlr(cons);
63   	   assert(conshdlr != NULL);
64   	   conshdlrname = SCIPconshdlrGetName(conshdlr);
65   	
66   	   *success = TRUE;
67   	   rhs = SCIP_INVALID;
68   	
69   	   if( strcmp(conshdlrname, "linear") == 0 )
70   	   {
71   	      rhs = SCIPgetRhsLinear(scip, cons);
72   	   }
73   	   else if( strcmp(conshdlrname, "setppc") == 0 )
74   	   {
75   	      switch( SCIPgetTypeSetppc(scip, cons) )
76   	      {
77   	      case SCIP_SETPPCTYPE_PARTITIONING: /* fall through intended */
78   	      case SCIP_SETPPCTYPE_PACKING:
79   	         rhs = 1.0;
80   	         break;
81   	
82   	      case SCIP_SETPPCTYPE_COVERING:
83   	         rhs = SCIPinfinity(scip);
84   	         break;
85   	      }
86   	   }
87   	   else if( strcmp(conshdlrname, "logicor") == 0 )
88   	   {
89   	      rhs = SCIPinfinity(scip);
90   	   }
91   	   else if( strcmp(conshdlrname, "knapsack") == 0 )
92   	   {
93   	      rhs = SCIPgetCapacityKnapsack(scip, cons);
94   	   }
95   	   else if( strcmp(conshdlrname, "varbound") == 0 )
96   	   {
97   	      rhs = SCIPgetRhsVarbound(scip, cons);
98   	   }
99   	   else
100  	   {
101  	      SCIPwarningMessage(scip, "Cannot return rhs for constraint of type <%s>\n", conshdlrname);
102  	      *success = FALSE;
103  	   }
104  	
105  	   return rhs;
106  	}
107  	
108  	/** returns the left-hand side of an arbitrary SCIP constraint that can be represented as a single linear constraint
109  	 *
110  	 *  @note The success pointer indicates if the individual contraint handler was able to return the involved values
111  	 */
112  	SCIP_Real SCIPconsGetLhs(
113  	   SCIP*                 scip,               /**< SCIP data structure */
114  	   SCIP_CONS*            cons,               /**< constraint to get left-hand side for */
115  	   SCIP_Bool*            success             /**< pointer to store whether a valid left-hand side was returned */
116  	   )
117  	{
118  	   SCIP_CONSHDLR* conshdlr;
119  	   const char* conshdlrname;
120  	   SCIP_Real lhs;
121  	
122  	   assert(scip != NULL);
123  	   assert(cons != NULL);
124  	   assert(success != NULL);
125  	
126  	   conshdlr = SCIPconsGetHdlr(cons);
127  	   assert(conshdlr != NULL);
128  	   conshdlrname = SCIPconshdlrGetName(conshdlr);
129  	
130  	   *success = TRUE;
131  	   lhs = SCIP_INVALID;
132  	
133  	   if( strcmp(conshdlrname, "linear") == 0 )
134  	   {
135  	      lhs = SCIPgetLhsLinear(scip, cons);
136  	   }
137  	   else if( strcmp(conshdlrname, "setppc") == 0 )
138  	   {
139  	      switch( SCIPgetTypeSetppc(scip, cons) )
140  	      {
141  	      case SCIP_SETPPCTYPE_PARTITIONING: /* fall through intended */
142  	      case SCIP_SETPPCTYPE_COVERING:
143  	         lhs = 1.0;
144  	         break;
145  	
146  	      case SCIP_SETPPCTYPE_PACKING:
147  	         lhs = -SCIPinfinity(scip);
148  	         break;
149  	      }
150  	   }
151  	   else if( strcmp(conshdlrname, "logicor") == 0 )
152  	   {
153  	      lhs = 1.0;
154  	   }
155  	   else if( strcmp(conshdlrname, "knapsack") == 0 )
156  	   {
157  	      lhs = -SCIPinfinity(scip);
158  	   }
159  	   else if( strcmp(conshdlrname, "varbound") == 0 )
160  	   {
161  	      lhs = SCIPgetLhsVarbound(scip, cons);
162  	   }
163  	   else
164  	   {
165  	      SCIPwarningMessage(scip, "Cannot return lhs for constraint of type <%s>\n", conshdlrname);
166  	      *success = FALSE;
167  	   }
168  	
169  	   return lhs;
170  	}
171  	
172  	/** returns the value array of an arbitrary SCIP constraint that can be represented as a single linear constraint
173  	 *
174  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
175  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
176  	 *
177  	 *  @note The success pointer indicates if the individual contraint handler was able to return the involved values
178  	 */
179  	SCIP_RETCODE SCIPgetConsVals(
180  	   SCIP*                 scip,               /**< SCIP data structure */
181  	   SCIP_CONS*            cons,               /**< constraint for which the coefficients are wanted */
182  	   SCIP_Real*            vals,               /**< array to store the coefficients of the constraint */
183  	   int                   varssize,           /**< available slots in vals array needed to check if the array is large enough */
184  	   SCIP_Bool*            success             /**< pointer to store whether the coefficients are successfully copied */
185  	   )
186  	{
187  	   SCIP_CONSHDLR* conshdlr;
188  	   const char* conshdlrname;
189  	   int nvars;
190  	   int i;
191  	
192  	   assert(scip != NULL);
193  	   assert(cons != NULL);
194  	   assert(vals != NULL);
195  	   assert(success != NULL);
196  	
197  	   conshdlr = SCIPconsGetHdlr(cons);
198  	   assert(conshdlr != NULL);
199  	
200  	   conshdlrname = SCIPconshdlrGetName(conshdlr);
201  	
202  	   *success = TRUE;
203  	
204  	   SCIP_CALL( SCIPgetConsNVars(scip, cons, &nvars, success) );
205  	
206  	   if( !(*success) )
207  	   {
208  	      SCIPwarningMessage(scip, "Cannot return value array for constraint of type <%s>\n", conshdlrname);
209  	      return SCIP_OKAY;
210  	   }
211  	
212  	   if( varssize < nvars )
213  	   {
214  	      SCIPwarningMessage(scip, "Cannot return value array for constraint of type <%s> (insufficient memory provided)\n", conshdlrname);
215  	      *success = FALSE;
216  	      return SCIP_OKAY;
217  	   }
218  	
219  	   if( strcmp(conshdlrname, "linear") == 0 )
220  	   {
221  	      SCIP_Real* linvals;
222  	
223  	      linvals = SCIPgetValsLinear(scip, cons);
224  	      assert(linvals != NULL);
225  	
226  	      for( i = 0; i < nvars; i++ )
227  	      {
228  	         vals[i] = linvals[i];
229  	      }
230  	   }
231  	   else if( strcmp(conshdlrname, "setppc") == 0 )
232  	   {
233  	      for( i = 0; i < nvars; i++ )
234  	      {
235  	         vals[i] = 1.0;
236  	      }
237  	   }
238  	   else if( strcmp(conshdlrname, "logicor") == 0 )
239  	   {
240  	      for( i = 0; i < nvars; i++ )
241  	      {
242  	         vals[i] = 1.0;
243  	      }
244  	   }
245  	   else if( strcmp(conshdlrname, "knapsack") == 0 )
246  	   {
247  	      SCIP_Longint* weights;
248  	
249  	      weights = SCIPgetWeightsKnapsack(scip, cons);
250  	      assert(weights != NULL);
251  	
252  	      for( i = 0; i < nvars; i++ )
253  	      {
254  	         vals[i] = (SCIP_Real)weights[i];
255  	      }
256  	   }
257  	   else if( strcmp(conshdlrname, "varbound") == 0 )
258  	   {
259  	      assert(nvars == 2);
260  	
261  	      vals[0] = 1.0;
262  	      vals[1] = SCIPgetVbdcoefVarbound(scip, cons);
263  	   }
264  	   else if( strcmp(conshdlrname, "SOS1") == 0 )
265  	   {
266  	      SCIP_Real* weights;
267  	
268  	      weights = SCIPgetWeightsSOS1(scip, cons);
269  	      assert(weights != NULL);
270  	
271  	      for( i = 0; i < nvars; i++ )
272  	      {
273  	         vals[i] = weights[i];
274  	      }
275  	   }
276  	   else if( strcmp(conshdlrname, "SOS2") == 0 )
277  	   {
278  	      SCIP_Real* weights;
279  	
280  	      weights = SCIPgetWeightsSOS2(scip, cons);
281  	      assert(weights != NULL);
282  	
283  	      for( i = 0; i < nvars; i++ )
284  	      {
285  	         vals[i] = weights[i];
286  	      }
287  	   }
288  	   else
289  	   {
290  	      SCIPwarningMessage(scip, "Cannot return value array for constraint of type <%s>\n", conshdlrname);
291  	      *success = FALSE;
292  	   }
293  	
294  	   return SCIP_OKAY;
295  	}
296  	
297  	/** returns the dual farkas sol of an arbitrary SCIP constraint that can be represented as a single linear constraint
298  	 *
299  	 *  @note The success pointer indicates if the individual contraint handler was able to return the dual farkas solution
300  	 */
301  	void SCIPconsGetDualfarkas(
302  	   SCIP*                 scip,               /**< SCIP data structure */
303  	   SCIP_CONS*            cons,               /**< constraint to get the dual farkas solution for */
304  	   SCIP_Real*            dualfarkas,         /**< pointer to store the dual farkas solution */
305  	   SCIP_Bool*            success             /**< pointer to store whether the dual farkas solution is successfully returned */
306  	   )
307  	{
308  	   SCIP_CONSHDLR* conshdlr;
309  	   const char* conshdlrname;
310  	
311  	   assert(scip != NULL);
312  	   assert(cons != NULL);
313  	
314  	   conshdlr = SCIPconsGetHdlr(cons);
315  	   assert(conshdlr != NULL);
316  	   conshdlrname = SCIPconshdlrGetName(conshdlr);
317  	
318  	   *success = TRUE;
319  	
320  	   if( strcmp(conshdlrname, "linear") == 0 )
321  	   {
322  	      *dualfarkas = SCIPgetDualfarkasLinear(scip, cons);
323  	   }
324  	   else if( strcmp(conshdlrname, "setppc") == 0 )
325  	   {
326  	      *dualfarkas = SCIPgetDualfarkasSetppc(scip, cons);
327  	   }
328  	   else if( strcmp(conshdlrname, "logicor") == 0 )
329  	   {
330  	      *dualfarkas = SCIPgetDualfarkasLogicor(scip, cons);
331  	   }
332  	   else if( strcmp(conshdlrname, "knapsack") == 0 )
333  	   {
334  	      *dualfarkas = SCIPgetDualfarkasKnapsack(scip, cons);
335  	   }
336  	   else if( strcmp(conshdlrname, "varbound") == 0 )
337  	   {
338  	      *dualfarkas = SCIPgetDualfarkasVarbound(scip, cons);
339  	   }
340  	   /* these are Benders' specific constraint handlers */
341  	   else if( strcmp(conshdlrname, "origbranch") == 0 || strcmp(conshdlrname, "masterbranch") == 0 )
342  	   {
343  	      *dualfarkas = 0.0;
344  	   }
345  	   else
346  	   {
347  	      SCIPwarningMessage(scip, "Cannot return dual farkas solution for constraint of type <%s>\n", conshdlrname);
348  	      *dualfarkas = 0.0;
349  	      *success = FALSE;
350  	   }
351  	}
352  	
353  	/** returns the dual sol of an arbitrary SCIP constraint that can be represented as a single linear constraint
354  	 *
355  	 *  @note The success pointer indicates if the individual contraint handler was able to return the dual solution
356  	 */
357  	void SCIPconsGetDualsol(
358  	   SCIP*                 scip,               /**< SCIP data structure */
359  	   SCIP_CONS*            cons,               /**< constraint to get the dual solution for */
360  	   SCIP_Real*            dualsol,            /**< pointer to store the dual solution */
361  	   SCIP_Bool*            success             /**< pointer to store whether the dual solution is successfully returned */
362  	   )
363  	{
364  	   SCIP_CONSHDLR* conshdlr;
365  	   const char* conshdlrname;
366  	
367  	   assert(scip != NULL);
368  	   assert(cons != NULL);
369  	
370  	   conshdlr = SCIPconsGetHdlr(cons);
371  	   assert(conshdlr != NULL);
372  	   conshdlrname = SCIPconshdlrGetName(conshdlr);
373  	
374  	   *success = TRUE;
375  	
376  	   if( strcmp(conshdlrname, "linear") == 0 )
377  	   {
378  	      *dualsol = SCIPgetDualsolLinear(scip, cons);
379  	   }
380  	   else if( strcmp(conshdlrname, "setppc") == 0 )
381  	   {
382  	      *dualsol = SCIPgetDualsolSetppc(scip, cons);
383  	   }
384  	   else if( strcmp(conshdlrname, "logicor") == 0 )
385  	   {
386  	      *dualsol = SCIPgetDualsolLogicor(scip, cons);
387  	   }
388  	   else if( strcmp(conshdlrname, "knapsack") == 0 )
389  	   {
390  	      *dualsol = SCIPgetDualsolKnapsack(scip, cons);
391  	   }
392  	   else if( strcmp(conshdlrname, "varbound") == 0 )
393  	   {
394  	      *dualsol = SCIPgetDualsolVarbound(scip, cons);
395  	   }
396  	   /* these are Benders' specific constraint handlers */
397  	   else if( strcmp(conshdlrname, "origbranch") == 0 || strcmp(conshdlrname, "masterbranch") == 0 )
398  	   {
399  	      *dualsol = 0.0;
400  	   }
401  	   else
402  	   {
403  	      SCIPwarningMessage(scip, "Cannot return dual solution for constraint of type <%s>\n", conshdlrname);
404  	      *dualsol = 0.0;
405  	      *success = FALSE;
406  	   }
407  	}
408  	
409  	/** returns the row of an arbitrary SCIP constraint that can be represented as a single linear constraint
410  	 *  or NULL of no row is available
411  	 */
412  	SCIP_ROW* SCIPconsGetRow(
413  	   SCIP*                 scip,               /**< SCIP data structure */
414  	   SCIP_CONS*            cons                /**< constraint for which row is queried */
415  	   )
416  	{
417  	   SCIP_CONSHDLR* conshdlr;
418  	   const char* conshdlrname;
419  	
420  	   assert(scip != NULL);
421  	   assert(cons != NULL);
422  	
423  	   conshdlr = SCIPconsGetHdlr(cons);
424  	   assert(conshdlr != NULL);
425  	   conshdlrname = SCIPconshdlrGetName(conshdlr);
426  	
427  	   if( strcmp(conshdlrname, "linear") == 0 )
428  	   {
429  	      return SCIPgetRowLinear(scip, cons);
430  	   }
431  	   else if( strcmp(conshdlrname, "setppc") == 0 )
432  	   {
433  	      return SCIPgetRowSetppc(scip, cons);
434  	   }
435  	   else if( strcmp(conshdlrname, "logicor") == 0 )
436  	   {
437  	      return SCIPgetRowLogicor(scip, cons);
438  	   }
439  	   else if( strcmp(conshdlrname, "knapsack") == 0 )
440  	   {
441  	      return SCIPgetRowKnapsack(scip, cons);
442  	   }
443  	   else if( strcmp(conshdlrname, "varbound") == 0 )
444  	   {
445  	      return SCIPgetRowVarbound(scip, cons);
446  	   }
447  	
448  	   return NULL;
449  	}
450  	
451  	/** adds the given variable to the input constraint.
452  	 *  If the constraint is setppc or logicor the value is ignored. If the constraint is knapsack, then the value is
453  	 *  converted to an int. A warning is passed if the SCIP_Real is not an integer.
454  	 *  TODO: Allow val to be a pointer.
455  	 */
456  	SCIP_RETCODE SCIPconsAddCoef(
457  	   SCIP*                 scip,               /**< SCIP data structure */
458  	   SCIP_CONS*            cons,               /**< constraint for which row is queried */
459  	   SCIP_VAR*             var,                /**< variable of the constraint entry */
460  	   SCIP_Real             val                 /**< the coefficient of the constraint entry */
461  	   )
462  	{
463  	   SCIP_CONSHDLR* conshdlr;
464  	   const char* conshdlrname;
465  	
466  	   assert(scip != NULL);
467  	   assert(cons != NULL);
468  	   assert(var != NULL);
469  	
470  	   conshdlr = SCIPconsGetHdlr(cons);
471  	   assert(conshdlr != NULL);
472  	   conshdlrname = SCIPconshdlrGetName(conshdlr);
473  	
474  	   if( strcmp(conshdlrname, "linear") == 0 )
475  	   {
476  	      SCIP_CALL( SCIPaddCoefLinear(scip, cons, var, val) );
477  	   }
478  	   else if( strcmp(conshdlrname, "setppc") == 0 )
479  	   {
480  	      SCIP_CALL( SCIPaddCoefSetppc(scip, cons, var) );
481  	   }
482  	   else if( strcmp(conshdlrname, "logicor") == 0 )
483  	   {
484  	      SCIP_CALL( SCIPaddCoefLogicor(scip, cons, var) );
485  	   }
486  	   else if( strcmp(conshdlrname, "knapsack") == 0 )
487  	   {
488  	      if( !SCIPisIntegral(scip, val) )
489  	      {
490  	         SCIPerrorMessage("The coefficient value %g is not valid. "
491  	            "The coefficient for a knapsack constraint must be integer.\n", val);
492  	         return SCIP_ERROR;
493  	      }
494  	
495  	      SCIP_CALL( SCIPaddCoefKnapsack(scip, cons, var, (SCIP_Longint)val) );
496  	   }
497  	   else if( strcmp(conshdlrname, "varbound") == 0 )
498  	   {
499  	      SCIPerrorMessage("Sorry, can't add coefficient for constraint of type <%s>\n", conshdlrname);
500  	      return SCIP_ERROR;
501  	   }
502  	   else
503  	   {
504  	      SCIPerrorMessage("Sorry, can't add coefficient for constraint of type <%s>\n", conshdlrname);
505  	      return SCIP_ERROR;
506  	   }
507  	
508  	   return SCIP_OKAY;
509  	}
510