1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 */
SCIPconsGetRhs(SCIP * scip,SCIP_CONS * cons,SCIP_Bool * success)39 SCIP_Real SCIPconsGetRhs(
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 */
69 case SCIP_SETPPCTYPE_PACKING:
70 rhs = 1.0;
71 break;
72
73 case SCIP_SETPPCTYPE_COVERING:
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 */
SCIPconsGetLhs(SCIP * scip,SCIP_CONS * cons,SCIP_Bool * success)103 SCIP_Real SCIPconsGetLhs(
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 */
133 case SCIP_SETPPCTYPE_COVERING:
134 lhs = 1.0;
135 break;
136
137 case SCIP_SETPPCTYPE_PACKING:
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 */
SCIPgetConsVals(SCIP * scip,SCIP_CONS * cons,SCIP_Real * vals,int varssize,SCIP_Bool * success)170 SCIP_RETCODE SCIPgetConsVals(
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 */
SCIPconsGetDualfarkas(SCIP * scip,SCIP_CONS * cons,SCIP_Real * dualfarkas,SCIP_Bool * success)292 void SCIPconsGetDualfarkas(
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 */
SCIPconsGetDualsol(SCIP * scip,SCIP_CONS * cons,SCIP_Real * dualsol,SCIP_Bool * success)348 void SCIPconsGetDualsol(
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 */
SCIPconsGetRow(SCIP * scip,SCIP_CONS * cons)403 SCIP_ROW* SCIPconsGetRow(
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 else
439 {
440 SCIPwarningMessage(scip, "Cannot return row for constraint of type <%s>\n", conshdlrname);
441 }
442
443 return NULL;
444 }
445
446 /** adds the given variable to the input constraint.
447 * If the constraint is setppc or logicor the value is ignored. If the constraint is knapsack, then the value is
448 * converted to an int. A warning is passed if the SCIP_Real is not an integer.
449 * TODO: Allow val to be a pointer.
450 */
SCIPconsAddCoef(SCIP * scip,SCIP_CONS * cons,SCIP_VAR * var,SCIP_Real val)451 SCIP_RETCODE SCIPconsAddCoef(
452 SCIP* scip, /**< SCIP data structure */
453 SCIP_CONS* cons, /**< constraint for which row is queried */
454 SCIP_VAR* var, /**< variable of the constraint entry */
455 SCIP_Real val /**< the coefficient of the constraint entry */
456 )
457 {
458 SCIP_CONSHDLR* conshdlr;
459 const char* conshdlrname;
460
461 assert(scip != NULL);
462 assert(cons != NULL);
463 assert(var != NULL);
464
465 conshdlr = SCIPconsGetHdlr(cons);
466 assert(conshdlr != NULL);
467 conshdlrname = SCIPconshdlrGetName(conshdlr);
468
469 if( strcmp(conshdlrname, "linear") == 0 )
470 {
471 SCIP_CALL( SCIPaddCoefLinear(scip, cons, var, val) );
472 }
473 else if( strcmp(conshdlrname, "setppc") == 0 )
474 {
475 SCIP_CALL( SCIPaddCoefSetppc(scip, cons, var) );
476 }
477 else if( strcmp(conshdlrname, "logicor") == 0 )
478 {
479 SCIP_CALL( SCIPaddCoefLogicor(scip, cons, var) );
480 }
481 else if( strcmp(conshdlrname, "knapsack") == 0 )
482 {
483 if( !SCIPisIntegral(scip, val) )
484 {
485 SCIPerrorMessage("The coefficient value %g is not valid. "
486 "The coefficient for a knapsack constraint must be integer.\n", val);
487 return SCIP_ERROR;
488 }
489
490 SCIP_CALL( SCIPaddCoefKnapsack(scip, cons, var, (SCIP_Longint)val) );
491 }
492 else if( strcmp(conshdlrname, "varbound") == 0 )
493 {
494 SCIPerrorMessage("Sorry, can't add coefficient for constraint of type <%s>\n", conshdlrname);
495 return SCIP_ERROR;
496 }
497 else
498 {
499 SCIPerrorMessage("Sorry, can't add coefficient for constraint of type <%s>\n", conshdlrname);
500 return SCIP_ERROR;
501 }
502
503 return SCIP_OKAY;
504 }
505