Scippy

SCIP

Solving Constraint Integer Programs

miniisc.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-2024 Zuse Institute Berlin (ZIB) */
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 miniisc.c
26 * @brief find a minimum IIS cover
27 * @author Marc Pfetsch
28 */
29
30#include <string.h>
31#include <scip/scipdefplugins.h>
32#include <lpi/lpi.h>
33
34#include "benders.h"
35#include "readargs.h"
36
37/* default parameters */
38#define DEFAULT_SOLVEMASTERAPPROX FALSE /**< Solve master problem approximately? */
39#define DEFAULT_MASTERGAPLIMIT 0.1 /**< gap bound for approximately solving the master problem */
40#define DEFAULT_REOPTIMIZATION TRUE /**< Use reoptimization to solve master problem? */
41#define DEFAULT_MASTERSTALLNODES 5000L /**< stall nodes for the master problem */
42
43/** data needed for cut generation */
44struct BENDERS_Data
45{
46 SCIP_LPI* lp; /**< alternative polyhedron */
47 int m; /**< number of constraints considered */
48};
49
50
51/* Macro for setting parameters in LPI */
52#define SCIP_CALL_PARAM(x) /*lint -e527 */ do \
53{ \
54 SCIP_RETCODE _restat_; \
55 if ( (_restat_ = (x)) != SCIP_OKAY && (_restat_ != SCIP_PARAMETERUNKNOWN) ) \
56 { \
57 SCIPerrorMessage("[%s:%d] Error <%d> in function call\n", __FILE__, __LINE__, _restat_); \
58 SCIPABORT(); \
59 return _restat_; \
60 } \
61} \
62while ( FALSE )
63
64
65/** Fix variable @a ind to 0 */
66static
68 SCIP_LPI* lp, /**< alternative LP */
69 int ind /**< variable that should be fixed to 0 */
70 )
71{
72 SCIP_Real lb = 0.0;
73 SCIP_Real ub = 0.0;
74
75 /* change bounds */
76 SCIP_CALL( SCIPlpiChgBounds(lp, 1, &ind, &lb, &ub) );
77
78 return SCIP_OKAY;
79}
80
81
82/** fix variables in @a S to 0 */
83static
85 SCIP* masterscip, /**< SCIP pointer */
86 int nmastervars, /**< number of variables in master */
87 SCIP_Bool* S, /**< indices to fix */
88 SCIP_LPI* lp /**< alternative LP */
89 )
90{
91 SCIP_Real* lb = NULL;
92 SCIP_Real* ub = NULL;
93 int* indices = NULL;
94 int cnt = 0;
95 int j;
96
97 assert( masterscip != NULL );
98 assert( S != NULL );
99 assert( lp != NULL );
100
101 SCIP_CALL( SCIPallocBufferArray(masterscip, &lb, nmastervars) );
102 SCIP_CALL( SCIPallocBufferArray(masterscip, &ub, nmastervars) );
103 SCIP_CALL( SCIPallocBufferArray(masterscip, &indices, nmastervars) );
104
105 /* collect bounds to be changed */
106 for (j = 0; j < nmastervars; ++j)
107 {
108 if ( S[j] )
109 {
110 indices[cnt] = j;
111 lb[cnt] = 0.0;
112 ub[cnt] = 0.0;
113 ++cnt;
114 }
115 }
116
117 /* change bounds */
118 if ( cnt > 0 )
119 {
120 SCIP_CALL( SCIPlpiChgBounds(lp, cnt, indices, lb, ub) );
121 }
122
123 SCIPfreeBufferArray(masterscip, &indices);
124 SCIPfreeBufferArray(masterscip, &ub);
125 SCIPfreeBufferArray(masterscip, &lb);
126
127 return SCIP_OKAY;
128}
129
130/** unfix variables in @a S */
131static
133 SCIP* masterscip, /**< SCIP pointer */
134 int nmastervars, /**< number of variables in master */
135 SCIP_Bool* S, /**< indices to fix */
136 SCIP_LPI* lp /**< alternative LP */
137 )
138{
139 SCIP_Real* lb = NULL;
140 SCIP_Real* ub = NULL;
141 int* indices = NULL;
142 int cnt = 0;
143 int j;
144
145 assert( masterscip != NULL );
146 assert( S != NULL );
147 assert( lp != NULL );
148
149 SCIP_CALL( SCIPallocBufferArray(masterscip, &lb, nmastervars) );
150 SCIP_CALL( SCIPallocBufferArray(masterscip, &ub, nmastervars) );
151 SCIP_CALL( SCIPallocBufferArray(masterscip, &indices, nmastervars) );
152
153 /* collect bounds to be changed */
154 for (j = 0; j < nmastervars; ++j)
155 {
156 if ( S[j] )
157 {
158 indices[cnt] = j;
159 lb[cnt] = 0.0;
160 ub[cnt] = SCIPlpiInfinity(lp);
161 ++cnt;
162 }
163 }
164
165 /* change bounds */
166 if ( cnt > 0 )
167 {
168 SCIP_CALL( SCIPlpiChgBounds(lp, cnt, indices, lb, ub) );
169 }
170
171 SCIPfreeBufferArray(masterscip, &indices);
172 SCIPfreeBufferArray(masterscip, &ub);
173 SCIPfreeBufferArray(masterscip, &lb);
174
175 return SCIP_OKAY;
176}
177
178/** Check whether the given LP is infeasible
179 *
180 * If @a primal is false we assume that the problem is <em>dual feasible</em>, e.g., the problem
181 * was only changed by fixing bounds!
182 *
183 * This is the workhorse for all methods that have to solve the alternative LP. We try in several
184 * ways to recover from possible stability problems.
185 *
186 * @pre It is assumed that all parameters for the alternative LP are set.
187 */
188static
190 SCIP* masterscip, /**< SCIP pointer */
191 SCIP_LPI* lp, /**< LP */
192 SCIP_Bool primal, /**< whether we are using the primal or dual simplex */
193 SCIP_Bool* infeasible, /**< output: whether the LP is infeasible */
194 SCIP_Bool* error /**< output: whether an error occured */
195 )
196{
197 SCIP_RETCODE retcode;
198
199 assert( masterscip != NULL );
200 assert( lp != NULL );
201 assert( infeasible != NULL );
202 assert( error != NULL );
203
204 *error = FALSE;
205
206 /* solve LP */
207 if ( primal )
208 retcode = SCIPlpiSolvePrimal(lp); /* use primal simplex */
209 else
210 retcode = SCIPlpiSolveDual(lp); /* use dual simplex */
211
212 if ( retcode == SCIP_LPERROR )
213 {
214 *error = TRUE;
215 return SCIP_OKAY;
216 }
217 SCIP_CALL( retcode );
218
219 /* resolve if LP is not stable */
220 if ( ! SCIPlpiIsStable(lp) )
221 {
224 SCIPwarningMessage(masterscip, "Numerical problems, retrying ...\n");
225
226 /* re-solve LP */
227 if ( primal )
228 retcode = SCIPlpiSolvePrimal(lp); /* use primal simplex */
229 else
230 retcode = SCIPlpiSolveDual(lp); /* use dual simplex */
231
232 /* reset parameters */
235
236 if ( retcode == SCIP_LPERROR )
237 {
238 *error = TRUE;
239 return SCIP_OKAY;
240 }
241 SCIP_CALL( retcode );
242 }
243
244 /* check whether we are in the paradoxical situation that
245 * - the primal is not infeasible
246 * - the primal is not unbounded
247 * - the LP is not optimal
248 * - we have a primal ray
249 *
250 * If we ran the dual simplex algorithm, then we run again with the primal simplex
251 */
252 if ( ! SCIPlpiIsPrimalInfeasible(lp) && ! SCIPlpiIsPrimalUnbounded(lp) && ! SCIPlpiIsOptimal(lp) && SCIPlpiExistsPrimalRay(lp) && ! primal )
253 {
254 SCIPwarningMessage(masterscip, "The dual simplex produced a primal ray. Retrying with primal ...\n");
255
256 /* the following settings might be changed: */
260
261 SCIP_CALL( SCIPlpiSolvePrimal(lp) ); /* use primal simplex */
262
263 /* reset parameters */
267 }
268
269 /* examine LP solution status */
270 if ( SCIPlpiIsPrimalInfeasible(lp) ) /* the LP is provably infeasible */
271 {
272 assert( ! SCIPlpiIsPrimalUnbounded(lp) ); /* can't be unbounded or optimal */
273 assert( ! SCIPlpiIsOptimal(lp) ); /* if it is infeasible! */
274 *infeasible = TRUE; /* LP is infeasible */
275 return SCIP_OKAY;
276 }
277 else
278 {
279 /* By assumption the dual is feasible if the dual simplex is run, therefore
280 * the status has to be primal unbounded or optimal. */
281 if ( ! SCIPlpiIsPrimalUnbounded(lp) && ! SCIPlpiIsOptimal(lp) )
282 {
283 /* We have a status different from unbounded or optimal. This should not be the case ... */
284 if (primal)
285 SCIPwarningMessage(masterscip, "Primal simplex returned with unknown status: %d\n", SCIPlpiGetInternalStatus(lp));
286 else
287 SCIPwarningMessage(masterscip, "Dual simplex returned with unknown status: %d\n", SCIPlpiGetInternalStatus(lp));
288
289 /* SCIP_CALL( SCIPlpiWriteLP(lp, "debug.lp") ); */
290 *error = TRUE;
291 return SCIP_OKAY;
292 }
293 }
294
295 /* at this point we have a feasible solution */
296 *infeasible = FALSE;
297 return SCIP_OKAY;
298}
299
300
301/** produce Benders cuts from the alternative polyhedron
302 *
303 * input:
304 * - masterscip: SCIP pointer of Benders master problem
305 * - nmastervars: number of variables in master problem
306 * - mastervars: variables in master problem
307 * - mastersolution: solution of Benders master problem
308 * - data: user data for oracle
309 * - timelimit: time limit for subproblem
310 * - ntotalcuts: total number of cuts
311 * output:
312 * - ncuts: number of cuts added
313 * - status: status
314 *
315 * @todo apply time limit
316 */
317static
319{ /*lint --e{715}*/
320#ifdef SCIP_DEBUG
321 char name[SCIP_MAXSTRLEN];
322#endif
323 SCIP_LPI* lp;
324 SCIP_Real* primsol;
325 SCIP_Real value = 0.0;
326 SCIP_Bool* S;
327 int size = 0;
328 int step = 0;
329 int ncols;
330 int j;
331
332 assert( masterscip != NULL );
333 assert( data != NULL );
334 assert( mastersolution != NULL );
335 assert( ncuts != NULL );
336 assert( status != NULL );
337 assert( data->lp != NULL );
338 assert( data->m == nmastervars );
339
340 lp = data->lp;
341
342 *ncuts = 0;
343 *status = BENDERS_STATUS_UNKNOWN;
344
345 SCIP_CALL( SCIPlpiGetNCols(lp, &ncols) );
346 SCIP_CALL( SCIPallocBufferArray(masterscip, &primsol, ncols) );
347 assert( nmastervars <= ncols );
348
349 /* init set S */
350 SCIP_CALL( SCIPallocClearBufferArray(masterscip, &S, nmastervars) );
351 for (j = 0; j < nmastervars; ++j)
352 {
353 assert( SCIPisFeasIntegral(masterscip, mastersolution[j]) );
354 if ( mastersolution[j] > 0.5 )
355 {
356 S[j] = TRUE;
357 ++size;
358 value += SCIPvarGetObj(mastervars[j]);
359 }
360 }
361 SCIP_CALL( fixAltLPVariables(masterscip, nmastervars, S, lp) );
362
363 do
364 {
365 SCIP_CONS* cons;
366 SCIP_VAR** vars;
367 SCIP_Bool infeasible;
368 SCIP_Real candobj = -1.0;
369 SCIP_Bool error;
370 int sizeIIS = 0;
371 int candidate = -1;
372 int cnt = 0;
373
374 if ( step == 0 )
375 {
376 /* the first LP is solved without warm start, after that we use a warmstart. */
378 SCIP_CALL( checkAltLPInfeasible(masterscip, lp, TRUE, &infeasible, &error) );
380 }
381 else
382 SCIP_CALL( checkAltLPInfeasible(masterscip, lp, FALSE, &infeasible, &error) );
383
384 if ( error )
385 {
386 *status = BENDERS_STATUS_ERROR;
387 break;
388 }
389
390 /* if the alternative polyhedron is infeasible, we found a cover */
391 if ( infeasible )
392 {
393 /* if the problem is infeasible in the first step, we are successful */
394 if ( step == 0 )
395 *status = BENDERS_STATUS_SUCCESS;
396
397 SCIPdebugMessage(" size: %4d produced possible cover with objective value %f.\n", size, value);
398 break;
399 }
400
401 /* get solution of alternative LP */
402 SCIP_CALL( SCIPlpiGetSol(lp, NULL, primsol, NULL, NULL, NULL) );
403
404 /* find candidate for variable to add */
405 for (j = 0; j < nmastervars; ++j)
406 {
407 /* check support of the solution, i.e., the corresponding IIS */
408 if ( ! SCIPisFeasZero(masterscip, primsol[j]) )
409 {
410 assert( ! S[j] );
411 ++sizeIIS;
412
413 /* take first element */
414 if ( candidate < 0 )
415 {
416 candidate = j;
417 candobj = SCIPvarGetObj(mastervars[j]);
418 }
419 }
420 }
421
422 /* check for error */
423 if ( candidate < 0 )
424 {
425 /* Because of numerical problem it might happen that the solution primsol above is zero
426 * within the tolerances. In this case we quit. */
427 break;
428 }
429 assert( candidate >= 0 );
430 assert( ! S[candidate] );
431 assert( sizeIIS > 0 );
432
433 SCIPdebugMessage(" size: %4d add %4d with objective value %6g and alt-LP solution value %-8.4g (IIS size: %4d).\n",
434 size, candidate, candobj, primsol[candidate], sizeIIS);
435
436 /* update new set S */
437 S[candidate] = TRUE;
438 ++size;
439 value += candobj;
440
441 SCIP_CALL( SCIPallocBufferArray(masterscip, &vars, nmastervars) );
442
443 /* collect variables corresponding to support to cut */
444 for (j = 0; j < nmastervars; ++j)
445 {
446 /* check support of the solution, i.e., the corresponding IIS */
447 if ( ! SCIPisFeasZero(masterscip, primsol[j]) )
448 vars[cnt++] = mastervars[j];
449 }
450 assert( cnt == sizeIIS );
451
452#ifdef SCIP_DEBUG
453 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "iis%d", (int) ntotalcuts + *ncuts);
454 SCIP_CALL( SCIPcreateConsLogicor(masterscip, &cons, name, cnt, vars, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
455#else
456 SCIP_CALL( SCIPcreateConsLogicor(masterscip, &cons, "", cnt, vars, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
457#endif
458
459#ifdef SCIP_OUTPUT
460 SCIP_CALL( SCIPprintCons(masterscip, cons, NULL) );
461 SCIPinfoMessage(masterscip, NULL, ";\n");
462#endif
463
464 SCIP_CALL( SCIPaddCons(masterscip, cons) );
465 SCIP_CALL( SCIPreleaseCons(masterscip, &cons) );
466
467 SCIPfreeBufferArray(masterscip, &vars);
468
469 ++(*ncuts);
470 *status = BENDERS_STATUS_ADDEDCUT;
471
472 /* fix chosen variable to 0 */
473 SCIP_CALL( fixAltLPVariable(lp, candidate) );
474
475 ++step;
476 }
477 while (step < nmastervars);
478
479 SCIP_CALL( unfixAltLPVariables(masterscip, nmastervars, S, lp) );
480
481 SCIPfreeBufferArray(masterscip, &S);
482 SCIPfreeBufferArray(masterscip, &primsol);
483
484 return SCIP_OKAY;
485}
486
487
488/** creates column in alternative polyhedron */
489static
491 SCIP* origscip, /**< SCIP pointer */
492 SCIP_LPI* lp, /**< alternative LP */
493 int nvars, /**< number of variables in column */
494 SCIP_VAR** vars, /**< variables for column */
495 SCIP_Real* vals, /**< values for column */
496 SCIP_Real rhscoef, /**< coefficient for first row */
497 SCIP_Real sign /**< sign (+1,-1) for column */
498 )
499{
500 SCIP_Real obj = 1.0;
501 SCIP_Real lb = 0.0;
502 SCIP_Real ub;
503 SCIP_Real* matval;
504 int* matind;
505 int matbeg = 0;
506 int cnt = 0;
507 int v;
508
509 assert( origscip != NULL );
510 assert( vars != NULL );
511 assert( vals != NULL );
512 assert( SCIPisEQ(origscip, sign, 1.0) || SCIPisEQ(origscip, sign, -1.0) );
513
514 if ( SCIPisInfinity(origscip, rhscoef) || SCIPisInfinity(origscip, -rhscoef) )
515 return SCIP_OKAY;
516
517 /* set up data for construction */
518 SCIP_CALL( SCIPallocBufferArray(origscip, &matind, nvars + 1) );
519 SCIP_CALL( SCIPallocBufferArray(origscip, &matval, nvars + 1) );
520
521 /* handle first row */
522 if ( ! SCIPisFeasZero(origscip, rhscoef) )
523 {
524 matind[cnt] = 0;
525 matval[cnt++] = sign * rhscoef;
526 }
527
528 /* set up column */
529 for (v = 0; v < nvars; ++v)
530 {
531 assert( vars[v] != NULL );
532 if ( vals != NULL )
533 matval[cnt] = vals[v] * sign;
534 else
535 matval[cnt] = sign;
536 matind[cnt++] = SCIPvarGetIndex(vars[v]) + 1;
537 }
538
539 /* now add column */
540 ub = SCIPlpiInfinity(lp);
541
542 SCIP_CALL( SCIPlpiAddCols(lp, 1, &obj, &lb, &ub, NULL, cnt, &matbeg, matind, matval) );
543
544 SCIPfreeBufferArray(origscip, &matval);
545 SCIPfreeBufferArray(origscip, &matind);
546
547 return SCIP_OKAY;
548}
549
550
551/** create alternative polyhedron */
552static
554 SCIP* origscip, /**< original SCIP instance */
555 SCIP_LPI* lp /**< alternative polyhedron */
556 )
557{
558 SCIP_CONS** origconss;
559 int norigconss;
560 int c;
561 int v;
562
563 assert( origscip != NULL );
564 assert( lp != NULL );
565
566 origconss = SCIPgetConss(origscip);
567 norigconss = SCIPgetNConss(origscip);
568
569 for (c = 0; c < norigconss; ++c)
570 {
571 const char* origconshdlrname;
572 SCIP_CONSHDLR* origconshdlr;
573 SCIP_VAR** origconsvars;
574 SCIP_CONS* origcons;
575 int norigconsvars;
576
577 origcons = origconss[c];
578 assert( origcons != NULL );
579
580 origconshdlr = SCIPconsGetHdlr(origcons);
581 assert( origconshdlr != NULL );
582 origconshdlrname = SCIPconshdlrGetName(origconshdlr);
583
584 if ( strcmp(origconshdlrname, "linear") == 0 )
585 {
586 origconsvars = SCIPgetVarsLinear(origscip, origcons);
587 norigconsvars = SCIPgetNVarsLinear(origscip, origcons);
588
589 SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, SCIPgetValsLinear(origscip, origcons), SCIPgetRhsLinear(origscip, origcons), 1.0) );
590 SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, SCIPgetValsLinear(origscip, origcons), SCIPgetLhsLinear(origscip, origcons), -1.0) );
591 }
592 else if ( strcmp(origconshdlrname, "setppc") == 0 )
593 {
594 origconsvars = SCIPgetVarsSetppc(origscip, origcons);
595 norigconsvars = SCIPgetNVarsSetppc(origscip, origcons);
596
597 switch ( SCIPgetTypeSetppc(origscip, origcons) )
598 {
600 SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, NULL, 1.0, 1.0) );
601 SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, NULL, 1.0, -1.0) );
602 break;
604 SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, NULL, 1.0, 1.0) );
605 break;
607 SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, NULL, 1.0, -1.0) );
608 break;
609 }
610 }
611 else if ( strcmp(origconshdlrname, "logicor") == 0 )
612 {
613 origconsvars = SCIPgetVarsLogicor(origscip, origcons);
614 norigconsvars = SCIPgetNVarsLogicor(origscip, origcons);
615
616 SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, NULL, 1.0, -1.0) );
617 }
618 else if ( strcmp(origconshdlrname, "knapsack") == 0 )
619 {
620 SCIP_Longint* origweights;
621 SCIP_Real* consvals;
622
623 origconsvars = SCIPgetVarsKnapsack(origscip, origcons);
624 norigconsvars = SCIPgetNVarsKnapsack(origscip, origcons);
625
626 /* copy Longint array to SCIP_Real array */
627 origweights = SCIPgetWeightsKnapsack(origscip, origcons);
628 SCIP_CALL( SCIPallocBufferArray(origscip, &consvals, norigconsvars) );
629
630 for ( v = 0; v < norigconsvars; ++v )
631 consvals[v] = (SCIP_Real) origweights[v];
632
633 SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, consvals, (SCIP_Real) SCIPgetCapacityKnapsack(origscip, origcons), 1.0) );
634
635 SCIPfreeBufferArray(origscip, &consvals);
636 }
637 else if ( strcmp(origconshdlrname, "varbound") == 0 )
638 {
639 SCIP_VAR* consvars[2];
640 SCIP_Real consvals[2];
641
642 consvars[0] = SCIPgetVarVarbound(origscip, origcons);
643 consvars[1] = SCIPgetVbdvarVarbound(origscip, origcons);
644
645 consvals[0] = 1.0;
646 consvals[1] = SCIPgetVbdcoefVarbound(origscip, origcons);
647
648 SCIP_CALL( createAltLPColumn(origscip, lp, 2, consvars, consvals, SCIPgetRhsVarbound(origscip, origcons), 1.0) );
649 SCIP_CALL( createAltLPColumn(origscip, lp, 2, consvars, consvals, SCIPgetLhsVarbound(origscip, origcons), -1.0) );
650 }
651 else
652 {
653 SCIPwarningMessage(origscip, "Cannot handle constraints of type <%s>.\n", origconshdlrname);
654 }
655 }
656 return SCIP_OKAY;
657}
658
659
660/** solve minimum IIS cover problem */
661static
663 const char* filename, /**< problem name */
664 const char* settingsname, /**< name of parameter file (or NULL) */
665 SCIP_Real timelimit, /**< time limit read from arguments */
666 SCIP_Real memlimit, /**< memory limit read from arguments */
667 int dispfreq /**< display frequency */
668 )
669{
670 char name[SCIP_MAXSTRLEN];
671 BENDERS_DATA data;
672 SCIP* masterscip;
673 SCIP* origscip;
674 SCIP_STATUS status;
675 SCIP_LPI* lp;
676 SCIP_Real lhs = -1.0;
677 SCIP_Real rhs = -1.0;
678 SCIP_VAR** origvars;
679 SCIP_Real obj = 0.0;
680 SCIP_Real lb = 0.0;
681 SCIP_Real ub;
682 int norigvars;
683 int nrows = 0;
684 int m = 0;
685 int v;
686
687 /* parameters */
688 SCIP_Bool solvemasterapprox;
689 SCIP_Longint masterstallnodes;
690 SCIP_Real mastergaplimit;
691 SCIP_Bool reoptimization;
692
693 /* create master SCIP */
694 SCIP_CALL( SCIPcreate(&masterscip) );
696 if ( getProblemName(filename, name, SCIP_MAXSTRLEN) == 0 )
697 {
698 SCIPerrorMessage("Cannot extract problem name for filename <%s>.\n", filename);
699 return SCIP_ERROR;
700 }
701 SCIP_CALL( SCIPcreateProb(masterscip, name, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
703
704 SCIPinfoMessage(masterscip, NULL, "Finding a minimum IIS cover using a set covering approach.\n");
705 SCIPinfoMessage(masterscip, NULL, "Implemented by Marc Pfetsch, 2015\n\n");
706
707 SCIPprintVersion(masterscip, NULL);
708 SCIPinfoMessage(masterscip, NULL, "\n");
709
710 /* add parameters */
711 SCIP_CALL( SCIPaddBoolParam(masterscip,
712 "miniisc/solvemasterapprox",
713 "Solve master problem approximately?",
714 &solvemasterapprox, TRUE, DEFAULT_SOLVEMASTERAPPROX, NULL, NULL) );
715
716 SCIP_CALL( SCIPaddRealParam(masterscip,
717 "miniisc/mastergaplimit",
718 "gap bound for approximately solving the master problem",
719 &mastergaplimit, TRUE, DEFAULT_MASTERGAPLIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
720
721 SCIP_CALL( SCIPaddLongintParam(masterscip,
722 "miniisc/masterstallnodes",
723 "stall nodes for the master problem",
724 &masterstallnodes, TRUE, DEFAULT_MASTERSTALLNODES, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
725
726 SCIP_CALL( SCIPaddBoolParam(masterscip,
727 "miniisc/reoptimization",
728 "Use reoptimization to solve master problem?",
729 &reoptimization, TRUE, DEFAULT_REOPTIMIZATION, NULL, NULL) );
730
731 /* read parameters if required */
732 if ( settingsname != NULL )
733 {
734 if ( SCIPfileExists(settingsname) )
735 {
736 SCIPinfoMessage(masterscip, NULL, "\nreading user parameter file <%s> ...\n\n", settingsname);
737 SCIP_CALL( SCIPreadParams(masterscip, settingsname) );
738 SCIP_CALL( SCIPwriteParams(masterscip, NULL, FALSE, TRUE) );
739 }
740 else
741 {
742 SCIPwarningMessage(masterscip, "\nparameter file <%s> not found - using default parameters.\n", settingsname);
743 }
744 }
745
746 if ( ! SCIPisInfinity(masterscip, timelimit) )
747 SCIPinfoMessage(masterscip, NULL, "limits/time = %f\n\n", timelimit);
748
749 SCIPinfoMessage(masterscip, NULL, "Input file:\t%s\n", filename);
750 SCIPinfoMessage(masterscip, NULL, "Problem name:\t%s\n\n", name);
751
752 /* ----------------------------------------------------------------------------------------*/
753
754 /* read instance to create alternative polyhedron */
755 SCIP_CALL( SCIPcreate(&origscip) );
756
757 /* include default SCIP plugins */
759
760 /* read problem */
761 SCIP_CALL( SCIPreadProb(origscip, filename, NULL) );
762
763 /* check that we have an LP */
764 if ( SCIPgetNOrigBinVars(origscip) + SCIPgetNOrigIntVars(origscip) > 0 )
765 {
766 SCIPinfoMessage(masterscip, NULL, "ERROR: input file contains integer variables. The code only works for LPs.\n");
767 return SCIP_ERROR;
768 }
769
770 /* ----------------------------------------------------------------------------------------*/
771
772 /* init alternative polyhedron */
773 SCIP_CALL( SCIPlpiCreate(&lp, SCIPgetMessagehdlr(masterscip), "altlp", SCIP_OBJSEN_MINIMIZE) );
774
775 /* init parameters */
780
781 /* add first row */
782 SCIP_CALL( SCIPlpiAddRows(lp, 1, &lhs, &rhs, NULL, 0, NULL, NULL, NULL) );
783
784 norigvars = SCIPgetNOrigVars(origscip);
785 origvars = SCIPgetOrigVars(origscip);
786
787 /* add rows for each variable */
788 lhs = 0.0;
789 rhs = 0.0;
790 for (v = 0; v < norigvars; ++v)
791 {
792 SCIP_CALL( SCIPlpiAddRows(lp, 1, &lhs, &rhs, NULL, 0, NULL, NULL, NULL) );
793 }
794 SCIP_CALL( SCIPlpiGetNRows(lp, &nrows) );
795
796 /* create alternative polyhedron */
797 SCIP_CALL( createAltLP(origscip, lp) );
798
799 /* get number of constraints */
800 SCIP_CALL( SCIPlpiGetNCols(lp, &m) );
801
802 /* add columns for bounds */
803 ub = SCIPlpiInfinity(lp);
804 for (v = 0; v < norigvars; ++v)
805 {
806 SCIP_Real val;
807 SCIP_VAR* var;
808 SCIP_Real matval[2];
809 int matind[2];
810 int matbeg = 0;
811 int cnt = 0;
812
813 var = origvars[v];
814 assert( var != NULL );
815 assert( 0 <= SCIPvarGetIndex(var) && SCIPvarGetIndex(var) < nrows );
816
817 /* if the lower bound is finite */
818 val = SCIPvarGetLbGlobal(var);
819 if ( ! SCIPisInfinity(origscip, -val) )
820 {
821 if ( ! SCIPisZero(origscip, val) )
822 {
823 matind[cnt] = 0;
824 matval[cnt++] = -val;
825 }
826 matind[cnt] = SCIPvarGetIndex(var) + 1;
827 matval[cnt++] = -1.0;
828 SCIP_CALL( SCIPlpiAddCols(lp, 1, &obj, &lb, &ub, NULL, cnt, &matbeg, matind, matval) );
829 }
830
831 /* if the upper bound is finite */
832 cnt = 0;
833 val = SCIPvarGetUbGlobal(var);
834 if ( ! SCIPisInfinity(origscip, val) )
835 {
836 if ( ! SCIPisZero(origscip, val) )
837 {
838 matind[cnt] = 0;
839 matval[cnt++] = val;
840 }
841 matind[cnt] = SCIPvarGetIndex(var) + 1;
842 matval[cnt++] = 1.0;
843 SCIP_CALL( SCIPlpiAddCols(lp, 1, &obj, &lb, &ub, NULL, cnt, &matbeg, matind, matval) );
844 }
845 }
846
847 /* free SCIP instance */
848 SCIP_CALL( SCIPfree(&origscip) );
849
850#ifdef SCIP_OUTPUT
851 SCIP_CALL( SCIPlpiWriteLP(lp, "alt.lp") );
852#endif
853
854 /* ----------------------------------------------------------------------------------------*/
855 /* initialize master problem */
856 for (v = 0; v < m; ++v)
857 {
858 SCIP_VAR* var;
859
860 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "y%d", v);
861 SCIP_CALL( SCIPcreateVar(masterscip, &var, name, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
862 SCIP_CALL( SCIPaddVar(masterscip, var) );
863 SCIP_CALL( SCIPreleaseVar(masterscip, &var) );
864 }
865
866 /* run Benders algorithm */
867 data.lp = lp;
868 data.m = m;
869 SCIP_CALL( runBenders(masterscip, cutoracle, &data, timelimit, memlimit, dispfreq, reoptimization, solvemasterapprox,
870 masterstallnodes, mastergaplimit, SCIP_VERBLEVEL_NORMAL, &status) );
871
872 SCIP_CALL( SCIPlpiFree(&lp) );
873
874 SCIP_CALL( SCIPfree(&masterscip) );
875
876 return SCIP_OKAY;
877}
878
879
880
881
882/** main function */
883int
885 int argc, /**< number of shell parameters */
886 char** argv /**< array with shell parameters */
887 )
888{
889 SCIP_RETCODE retcode;
890 const char* filename;
891 const char* settingsname;
892 SCIP_Real timelimit;
893 SCIP_Real memlimit;
894 SCIP_Longint nodelimit;
895 int dispfreq;
896
897 retcode = readArguments(argc, argv, &filename, &settingsname, &timelimit, &memlimit, &nodelimit, &dispfreq);
898 if ( retcode != SCIP_OKAY )
899 return -1;
900 assert( filename != NULL );
901
902 /* read file */
903 if ( ! SCIPfileExists(filename) )
904 {
905 SCIPerrorMessage("file <%s> does not exist.\n", filename);
906 return -1;
907 }
908
909 retcode = solveMinIISC(filename, settingsname, timelimit, memlimit, dispfreq);
910 if ( retcode != SCIP_OKAY )
911 {
912 SCIPprintError(retcode);
913 return -1;
914 }
915
917
918 return 0;
919}
SCIP_RETCODE runBenders(SCIP *masterscip, BENDERS_CUTORACLE((*Oracle)), BENDERS_DATA *data, SCIP_Real timelimit, SCIP_Real memlimit, int dispfreq, SCIP_Bool usereopt, SCIP_Bool solvemasterapprox, SCIP_Longint masterstallnodes, SCIP_Real mastergaplimit, SCIP_VERBLEVEL verblevel, SCIP_STATUS *status)
Definition: benders.c:207
@ BENDERS_STATUS_ERROR
Definition: benders.h:49
@ BENDERS_STATUS_ADDEDCUT
Definition: benders.h:45
@ BENDERS_STATUS_SUCCESS
Definition: benders.h:46
@ BENDERS_STATUS_UNKNOWN
Definition: benders.h:44
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_LONGINT_MAX
Definition: def.h:159
#define SCIP_CALL(x)
Definition: def.h:374
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9545
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9568
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9591
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
@ SCIP_SETPPCTYPE_PARTITIONING
Definition: cons_setppc.h:87
@ SCIP_SETPPCTYPE_COVERING
Definition: cons_setppc.h:89
@ SCIP_SETPPCTYPE_PACKING
Definition: cons_setppc.h:88
SCIP_Bool SCIPfileExists(const char *filename)
Definition: misc.c:11079
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
int SCIPgetNOrigBinVars(SCIP *scip)
Definition: scip_prob.c:2459
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2405
int SCIPgetNOrigIntVars(SCIP *scip)
Definition: scip_prob.c:2486
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3088
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2432
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1242
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:117
SCIP_RETCODE SCIPreadProb(SCIP *scip, const char *filename, const char *extension)
Definition: scip_prob.c:339
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:3919
SCIP_Bool SCIPlpiExistsPrimalRay(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2450
SCIP_RETCODE SCIPlpiAddRows(SCIP_LPI *lpi, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
Definition: lpi_clp.cpp:914
SCIP_RETCODE SCIPlpiWriteLP(SCIP_LPI *lpi, const char *fname)
Definition: lpi_clp.cpp:4001
int SCIPlpiGetInternalStatus(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2752
SCIP_RETCODE SCIPlpiChgBounds(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
Definition: lpi_clp.cpp:1084
SCIP_Bool SCIPlpiIsPrimalUnbounded(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2488
SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
Definition: lpi_clp.cpp:643
SCIP_RETCODE SCIPlpiSetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int ival)
Definition: lpi_clp.cpp:3692
SCIP_Bool SCIPlpiIsOptimal(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2623
SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
Definition: lpi_clp.cpp:2788
SCIP_Bool SCIPlpiIsPrimalInfeasible(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2502
SCIP_RETCODE SCIPlpiSolveDual(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:1880
SCIP_RETCODE SCIPlpiAddCols(SCIP_LPI *lpi, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
Definition: lpi_clp.cpp:758
SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:1805
SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
Definition: lpi_clp.cpp:531
SCIP_Bool SCIPlpiIsStable(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2647
SCIP_RETCODE SCIPlpiGetNCols(SCIP_LPI *lpi, int *ncols)
Definition: lpi_clp.cpp:1435
SCIP_RETCODE SCIPlpiGetNRows(SCIP_LPI *lpi, int *nrows)
Definition: lpi_clp.cpp:1417
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:88
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
void SCIPprintError(SCIP_RETCODE retcode)
Definition: scip_general.c:221
void SCIPprintVersion(SCIP *scip, FILE *file)
Definition: scip_general.c:156
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:111
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPreadParams(SCIP *scip, const char *filename)
Definition: scip_param.c:772
SCIP_RETCODE SCIPwriteParams(SCIP *scip, const char *filename, SCIP_Bool comments, SCIP_Bool onlychanged)
Definition: scip_param.c:813
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8234
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2537
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17758
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:114
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
interface methods for specific LP solvers
#define BMScheckEmptyMemory()
Definition: memory.h:155
#define SCIP_CALL_PARAM(x)
Definition: miniisc.c:52
static BENDERS_CUTORACLE(cutoracle)
Definition: miniisc.c:318
#define DEFAULT_MASTERSTALLNODES
Definition: miniisc.c:41
int main(int argc, char **argv)
Definition: miniisc.c:884
static SCIP_RETCODE solveMinIISC(const char *filename, const char *settingsname, SCIP_Real timelimit, SCIP_Real memlimit, int dispfreq)
Definition: miniisc.c:662
static SCIP_RETCODE fixAltLPVariables(SCIP *masterscip, int nmastervars, SCIP_Bool *S, SCIP_LPI *lp)
Definition: miniisc.c:84
static SCIP_RETCODE createAltLPColumn(SCIP *origscip, SCIP_LPI *lp, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real rhscoef, SCIP_Real sign)
Definition: miniisc.c:490
static SCIP_RETCODE fixAltLPVariable(SCIP_LPI *lp, int ind)
Definition: miniisc.c:67
#define DEFAULT_REOPTIMIZATION
Definition: miniisc.c:40
#define DEFAULT_SOLVEMASTERAPPROX
Definition: miniisc.c:38
static SCIP_RETCODE createAltLP(SCIP *origscip, SCIP_LPI *lp)
Definition: miniisc.c:553
static SCIP_RETCODE unfixAltLPVariables(SCIP *masterscip, int nmastervars, SCIP_Bool *S, SCIP_LPI *lp)
Definition: miniisc.c:132
static SCIP_RETCODE checkAltLPInfeasible(SCIP *masterscip, SCIP_LPI *lp, SCIP_Bool primal, SCIP_Bool *infeasible, SCIP_Bool *error)
Definition: miniisc.c:189
#define DEFAULT_MASTERGAPLIMIT
Definition: miniisc.c:39
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebugMessage
Definition: pub_message.h:96
SCIP_RETCODE readArguments(int argc, char **argv, const char **filename, const char **settingsname, SCIP_Real *timelimit, SCIP_Real *memlimit, SCIP_Longint *nodelimit, int *dispfreq)
Definition: readargs.c:95
int getProblemName(const char *filename, char *probname, int maxsize)
Definition: readargs.c:37
read comand line arguments
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
default SCIP plugins
internal methods for Benders' decomposition
SCIP_LPI * lp
Definition: classify.c:49
@ SCIP_LPPAR_SCALING
Definition: type_lpi.h:52
@ SCIP_LPPAR_PRESOLVING
Definition: type_lpi.h:53
@ SCIP_LPPAR_FASTMIP
Definition: type_lpi.h:51
@ SCIP_LPPAR_FROMSCRATCH
Definition: type_lpi.h:50
@ SCIP_OBJSEN_MINIMIZE
Definition: type_lpi.h:43
@ SCIP_VERBLEVEL_NORMAL
Definition: type_message.h:55
@ SCIP_OBJSENSE_MINIMIZE
Definition: type_prob.h:48
@ SCIP_LPERROR
Definition: type_retcode.h:49
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_ERROR
Definition: type_retcode.h:43
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:67
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62