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