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