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 2002-2022 Zuse Institute Berlin */
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  */
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 */
79  rhs = 1.0;
80  break;
81 
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  */
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 */
143  lhs = 1.0;
144  break;
145 
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  */
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  */
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  */
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 awailable
411  */
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  */
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 }
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:112
internal miscellaneous methods for linear constraints
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9385
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:48
SCIP_Real * SCIPgetWeightsSOS1(SCIP *scip, SCIP_CONS *cons)
Definition: cons_sos1.c:10639
SCIP_ROW * SCIPconsGetRow(SCIP *scip, SCIP_CONS *cons)
Definition: misc_linear.c:412
#define FALSE
Definition: def.h:96
SCIP_Real SCIPgetDualsolVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
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:9502
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:120
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:456
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:64
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4184
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2567
SCIP_Real SCIPgetDualsolLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetDualsolSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9476
#define NULL
Definition: lpi_spx1.cpp:164
#define SCIP_CALL(x)
Definition: def.h:393
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:93
void SCIPconsGetDualsol(SCIP *scip, SCIP_CONS *cons, SCIP_Real *dualsol, SCIP_Bool *success)
Definition: misc_linear.c:357
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9454
SCIP_Real * SCIPgetWeightsSOS2(SCIP *scip, SCIP_CONS *cons)
Definition: cons_sos2.c:2560
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8114
SCIP_ROW * SCIPgetRowSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9530
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:186
SCIP_RETCODE SCIPgetConsVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int varssize, SCIP_Bool *success)
Definition: misc_linear.c:179
#define SCIP_INVALID
Definition: def.h:206
#define SCIP_Longint
Definition: def.h:171
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:301
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.