Scippy

SCIP

Solving Constraint Integer Programs

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