Scippy

SCIP

Solving Constraint Integer Programs

classify.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-2022 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 classify.c
17  * @brief determine linear classifier using a Benders approach
18  * @author Marc Pfetsch
19  */
20 
21 #include <string.h>
22 #include <ctype.h>
23 #include <scip/scipdefplugins.h>
24 #include <lpi/lpi.h>
25 
26 #include "benders.h"
27 #include "readargs.h"
28 
29 /* default parameters */
30 #define DEFAULT_SOLVEMASTERAPPROX FALSE /**< Solve master problem approximately? */
31 #define DEFAULT_MASTERGAPLIMIT 0.1 /**< gap bound for approximately solving the master problem */
32 #define DEFAULT_REOPTIMIZATION FALSE /**< Use reoptimization to solve master problem? */
33 #define DEFAULT_MASTERSTALLNODES 5000L /**< stall nodes for the master problem */
34 #define DEFAULT_BOUNDSONCLASSIFIER FALSE /**< Use unit bounds on classifier? */
35 
36 
37 /** data needed for cut generation */
39 {
40  SCIP_LPI* lp; /**< alternative polyhedron */
41  int m; /**< number of constraints considered */
42 };
43 
44 
45 /* Macro for setting parameters in LPI */
46 #define SCIP_CALL_PARAM(x) /*lint -e527 */ do \
47 { \
48  SCIP_RETCODE _restat_; \
49  if ( (_restat_ = (x)) != SCIP_OKAY && (_restat_ != SCIP_PARAMETERUNKNOWN) ) \
50  { \
51  SCIPerrorMessage("[%s:%d] Error <%d> in function call\n", __FILE__, __LINE__, _restat_); \
52  SCIPABORT(); \
53  return _restat_; \
54  } \
55 } \
56 while ( FALSE )
57 
58 
59 /** Fix variable @a ind to 0 */
60 static
62  SCIP_LPI* lp, /**< alternative LP */
63  int ind /**< variable that should be fixed to 0 */
64  )
65 {
66  SCIP_Real lb = 0.0;
67  SCIP_Real ub = 0.0;
68 
69  /* change bounds */
70  SCIP_CALL( SCIPlpiChgBounds(lp, 1, &ind, &lb, &ub) );
71 
72  return SCIP_OKAY;
73 }
74 
75 
76 /** fix variables in @a S to 0 */
77 static
79  SCIP* masterscip, /**< SCIP pointer */
80  int nmastervars, /**< number of variables in master */
81  SCIP_Bool* S, /**< indices to fix */
82  SCIP_LPI* lp /**< alternative LP */
83  )
84 {
85  SCIP_Real* lb = NULL;
86  SCIP_Real* ub = NULL;
87  int* indices = NULL;
88  int cnt = 0;
89  int j;
90 
91  assert( masterscip != NULL );
92  assert( S != NULL );
93  assert( lp != NULL );
94 
95  SCIP_CALL( SCIPallocBufferArray(masterscip, &lb, nmastervars) );
96  SCIP_CALL( SCIPallocBufferArray(masterscip, &ub, nmastervars) );
97  SCIP_CALL( SCIPallocBufferArray(masterscip, &indices, nmastervars) );
98 
99  /* collect bounds to be changed */
100  for (j = 0; j < nmastervars; ++j)
101  {
102  if ( S[j] )
103  {
104  indices[cnt] = j;
105  lb[cnt] = 0.0;
106  ub[cnt] = 0.0;
107  ++cnt;
108  }
109  }
110 
111  /* change bounds */
112  if ( cnt > 0 )
113  {
114  SCIP_CALL( SCIPlpiChgBounds(lp, cnt, indices, lb, ub) );
115  }
116 
117  SCIPfreeBufferArray(masterscip, &indices);
118  SCIPfreeBufferArray(masterscip, &ub);
119  SCIPfreeBufferArray(masterscip, &lb);
120 
121  return SCIP_OKAY;
122 }
123 
124 /** unfix variables in @a S */
125 static
127  SCIP* masterscip, /**< SCIP pointer */
128  int nmastervars, /**< number of variables in master */
129  SCIP_Bool* S, /**< indices to fix */
130  SCIP_LPI* lp /**< alternative LP */
131  )
132 {
133  SCIP_Real* lb = NULL;
134  SCIP_Real* ub = NULL;
135  int* indices = NULL;
136  int cnt = 0;
137  int j;
138 
139  assert( masterscip != NULL );
140  assert( S != NULL );
141  assert( lp != NULL );
142 
143  SCIP_CALL( SCIPallocBufferArray(masterscip, &lb, nmastervars) );
144  SCIP_CALL( SCIPallocBufferArray(masterscip, &ub, nmastervars) );
145  SCIP_CALL( SCIPallocBufferArray(masterscip, &indices, nmastervars) );
146 
147  /* collect bounds to be changed */
148  for (j = 0; j < nmastervars; ++j)
149  {
150  if ( S[j] )
151  {
152  indices[cnt] = j;
153  lb[cnt] = 0.0;
154  ub[cnt] = SCIPlpiInfinity(lp);
155  ++cnt;
156  }
157  }
158 
159  /* change bounds */
160  if ( cnt > 0 )
161  {
162  SCIP_CALL( SCIPlpiChgBounds(lp, cnt, indices, lb, ub) );
163  }
164 
165  SCIPfreeBufferArray(masterscip, &indices);
166  SCIPfreeBufferArray(masterscip, &ub);
167  SCIPfreeBufferArray(masterscip, &lb);
168 
169  return SCIP_OKAY;
170 }
171 
172 /** Check whether the given LP is infeasible
173  *
174  * If @a primal is false we assume that the problem is <em>dual feasible</em>, e.g., the problem
175  * was only changed by fixing bounds!
176  *
177  * This is the workhorse for all methods that have to solve the alternative LP. We try in several
178  * ways to recover from possible stability problems.
179  *
180  * @pre It is assumed that all parameters for the alternative LP are set.
181  */
182 static
184  SCIP* masterscip, /**< SCIP pointer */
185  SCIP_LPI* lp, /**< LP */
186  SCIP_Bool primal, /**< whether we are using the primal or dual simplex */
187  SCIP_Bool* infeasible, /**< output: whether the LP is infeasible */
188  SCIP_Bool* error /**< output: whether an error occured */
189  )
190 {
191  SCIP_RETCODE retcode;
192 
193  assert( masterscip != NULL );
194  assert( lp != NULL );
195  assert( infeasible != NULL );
196  assert( error != NULL );
197 
198  *error = FALSE;
199 
200  /* solve LP */
201  if ( primal )
202  retcode = SCIPlpiSolvePrimal(lp); /* use primal simplex */
203  else
204  retcode = SCIPlpiSolveDual(lp); /* use dual simplex */
205 
206  if ( retcode == SCIP_LPERROR )
207  {
208  *error = TRUE;
209  return SCIP_OKAY;
210  }
211  SCIP_CALL( retcode );
212 
213  /* resolve if LP is not stable */
214  if ( ! SCIPlpiIsStable(lp) )
215  {
218  SCIPwarningMessage(masterscip, "Numerical problems, retrying ...\n");
219 
220  /* re-solve LP */
221  if ( primal )
222  retcode = SCIPlpiSolvePrimal(lp); /* use primal simplex */
223  else
224  retcode = SCIPlpiSolveDual(lp); /* use dual simplex */
225 
226  /* reset parameters */
229 
230  if ( retcode == SCIP_LPERROR )
231  {
232  *error = TRUE;
233  return SCIP_OKAY;
234  }
235  SCIP_CALL( retcode );
236  }
237 
238  /* check whether we are in the paradoxical situation that
239  * - the primal is not infeasible
240  * - the primal is not unbounded
241  * - the LP is not optimal
242  * - we have a primal ray
243  *
244  * If we ran the dual simplex algorithm, then we run again with the primal simplex
245  */
246  if ( ! SCIPlpiIsPrimalInfeasible(lp) && ! SCIPlpiIsPrimalUnbounded(lp) && ! SCIPlpiIsOptimal(lp) && SCIPlpiExistsPrimalRay(lp) && ! primal )
247  {
248  SCIPwarningMessage(masterscip, "The dual simplex produced a primal ray. Retrying with primal ...\n");
249 
250  /* the following settings might be changed: */
254 
255  SCIP_CALL( SCIPlpiSolvePrimal(lp) ); /* use primal simplex */
256 
257  /* reset parameters */
261  }
262 
263  /* examine LP solution status */
264  if ( SCIPlpiIsPrimalInfeasible(lp) ) /* the LP is provably infeasible */
265  {
266  assert( ! SCIPlpiIsPrimalUnbounded(lp) ); /* can't be unbounded or optimal */
267  assert( ! SCIPlpiIsOptimal(lp) ); /* if it is infeasible! */
268  *infeasible = TRUE; /* LP is infeasible */
269  return SCIP_OKAY;
270  }
271  else
272  {
273  /* By assumption the dual is feasible if the dual simplex is run, therefore
274  * the status has to be primal unbounded or optimal. */
275  if ( ! SCIPlpiIsPrimalUnbounded(lp) && ! SCIPlpiIsOptimal(lp) )
276  {
277  /* We have a status different from unbounded or optimal. This should not be the case ... */
278  if (primal)
279  SCIPwarningMessage(masterscip, "Primal simplex returned with unknown status: %d\n", SCIPlpiGetInternalStatus(lp));
280  else
281  SCIPwarningMessage(masterscip, "Dual simplex returned with unknown status: %d\n", SCIPlpiGetInternalStatus(lp));
282 
283  /* SCIP_CALL( SCIPlpiWriteLP(lp, "debug.lp") ); */
284  *error = TRUE;
285  return SCIP_OKAY;
286  }
287  }
288 
289  /* at this point we have a feasible solution */
290  *infeasible = FALSE;
291  return SCIP_OKAY;
292 }
293 
294 
295 /** produce Benders cuts from the alternative polyhedron
296  *
297  * input:
298  * - masterscip: SCIP pointer of Benders master problem
299  * - nmastervars: number of variables in master problem
300  * - mastervars: variables in master problem
301  * - mastersolution: solution of Benders master problem
302  * - data: user data for oracle
303  * - timelimit: time limit for subproblem
304  * - ntotalcuts: total number of cuts
305  * output:
306  * - ncuts: number of cuts added
307  * - status: status
308  *
309  * @todo apply time limit
310  */
311 static
313 { /*lint --e{715}*/
314 #ifdef SCIP_DEBUG
315  char name[SCIP_MAXSTRLEN];
316 #endif
317  SCIP_LPI* lp;
318  SCIP_Real* primsol;
319  SCIP_Real value = 0.0;
320  SCIP_Bool* S;
321  int size = 0;
322  int step = 0;
323  int ncols;
324  int j;
325 
326  assert( masterscip != NULL );
327  assert( data != NULL );
328  assert( mastersolution != NULL );
329  assert( ncuts != NULL );
330  assert( status != NULL );
331  assert( data->lp != NULL );
332  assert( data->m == nmastervars );
333 
334  lp = data->lp;
335 
336  *ncuts = 0;
337  *status = BENDERS_STATUS_UNKNOWN;
338 
339  SCIP_CALL( SCIPlpiGetNCols(lp, &ncols) );
340  SCIP_CALL( SCIPallocBufferArray(masterscip, &primsol, ncols) );
341  assert( nmastervars <= ncols );
342 
343  /* init set S */
344  SCIP_CALL( SCIPallocClearBufferArray(masterscip, &S, nmastervars) );
345  for (j = 0; j < nmastervars; ++j)
346  {
347  assert( SCIPisFeasIntegral(masterscip, mastersolution[j]) );
348  if ( mastersolution[j] > 0.5 )
349  {
350  S[j] = TRUE;
351  ++size;
352  value += SCIPvarGetObj(mastervars[j]);
353  }
354  }
355  SCIP_CALL( fixAltLPVariables(masterscip, nmastervars, S, lp) );
356 
357  do
358  {
359  SCIP_CONS* cons;
360  SCIP_VAR** vars;
361  SCIP_Bool infeasible;
362  SCIP_Real candobj = -1.0;
363  SCIP_Bool error;
364  int sizeIIS = 0;
365  int candidate = -1;
366  int cnt = 0;
367 
368  if ( step == 0 )
369  {
370  /* the first LP is solved without warm start, after that we use a warmstart. */
372  SCIP_CALL( checkAltLPInfeasible(masterscip, lp, TRUE, &infeasible, &error) );
374  }
375  else
376  SCIP_CALL( checkAltLPInfeasible(masterscip, lp, FALSE, &infeasible, &error) );
377 
378  if ( error )
379  {
380  *status = BENDERS_STATUS_ERROR;
381  break;
382  }
383 
384  /* if the alternative polyhedron is infeasible, we found a cover */
385  if ( infeasible )
386  {
387  /* if the problem is infeasible in the first step, we are successful */
388  if ( step == 0 )
389  *status = BENDERS_STATUS_SUCESS;
390 
391  SCIPdebugMessage(" size: %4d produced possible cover with objective value %f.\n", size, value);
392  break;
393  }
394 
395  /* get solution of alternative LP */
396  SCIP_CALL( SCIPlpiGetSol(lp, NULL, primsol, NULL, NULL, NULL) );
397 
398  /* find candidate for variable to add */
399  for (j = 0; j < nmastervars; ++j)
400  {
401  /* check support of the solution, i.e., the corresponding IIS */
402  if ( ! SCIPisFeasZero(masterscip, primsol[j]) )
403  {
404  assert( ! S[j] );
405  ++sizeIIS;
406 
407  /* take first element */
408  if ( candidate < 0 )
409  {
410  candidate = j;
411  candobj = SCIPvarGetObj(mastervars[j]);
412  }
413  }
414  }
415 
416  /* check for error */
417  if ( candidate < 0 )
418  {
419  /* Because of numerical problem it might happen that the solution primsol above is zero
420  * within the tolerances. In this case we quit. */
421  break;
422  }
423  assert( candidate >= 0 );
424  assert( ! S[candidate] );
425  assert( sizeIIS > 0 );
426 
427  SCIPdebugMessage(" size: %4d add %4d with objective value %6g and alt-LP solution value %-8.4g (IIS size: %4d).\n",
428  size, candidate, candobj, primsol[candidate], sizeIIS);
429 
430  /* update new set S */
431  S[candidate] = TRUE;
432  ++size;
433  value += candobj;
434 
435  SCIP_CALL( SCIPallocBufferArray(masterscip, &vars, nmastervars) );
436 
437  /* collect variables corresponding to support to cut */
438  for (j = 0; j < nmastervars; ++j)
439  {
440  /* check support of the solution, i.e., the corresponding IIS */
441  if ( ! SCIPisFeasZero(masterscip, primsol[j]) )
442  vars[cnt++] = mastervars[j];
443  }
444  assert( cnt == sizeIIS );
445 
446 #ifdef SCIP_DEBUG
447  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "iis%d", (int) ntotalcuts + *ncuts);
448  SCIP_CALL( SCIPcreateConsLogicor(masterscip, &cons, name, cnt, vars, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
449 #else
450  SCIP_CALL( SCIPcreateConsLogicor(masterscip, &cons, "", cnt, vars, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
451 #endif
452 
453 #ifdef SCIP_OUTPUT
454  SCIP_CALL( SCIPprintCons(masterscip, cons, NULL) );
455  SCIPinfoMessage(masterscip, NULL, ";\n");
456 #endif
457 
458  SCIP_CALL( SCIPaddCons(masterscip, cons) );
459  SCIP_CALL( SCIPreleaseCons(masterscip, &cons) );
460 
461  SCIPfreeBufferArray(masterscip, &vars);
462 
463  ++(*ncuts);
464  *status = BENDERS_STATUS_ADDEDCUT;
465 
466  /* fix chosen variable to 0 */
467  SCIP_CALL( fixAltLPVariable(lp, candidate) );
468 
469  ++step;
470  }
471  while (step < nmastervars);
472 
473  SCIP_CALL( unfixAltLPVariables(masterscip, nmastervars, S, lp) );
474 
475  SCIPfreeBufferArray(masterscip, &S);
476  SCIPfreeBufferArray(masterscip, &primsol);
477 
478  return SCIP_OKAY;
479 }
480 
481 
482 /** creates column in alternative polyhedron */
483 static
485  SCIP* origscip, /**< SCIP pointer */
486  SCIP_LPI* lp, /**< alternative LP */
487  int nvars, /**< number of variables in column */
488  SCIP_VAR** vars, /**< variables for column */
489  SCIP_Real* vals, /**< values for column */
490  SCIP_Real rhscoef, /**< coefficient for first row */
491  SCIP_Real sign /**< sign (+1,-1) for column */
492  )
493 {
494  SCIP_Real obj = 1.0;
495  SCIP_Real lb = 0.0;
496  SCIP_Real ub;
497  SCIP_Real* matval;
498  int* matind;
499  int matbeg = 0;
500  int cnt = 0;
501  int v;
502 
503  assert( origscip != NULL );
504  assert( vars != NULL );
505  assert( vals != NULL );
506  assert( SCIPisEQ(origscip, sign, 1.0) || SCIPisEQ(origscip, sign, -1.0) );
507 
508  if ( SCIPisInfinity(origscip, rhscoef) || SCIPisInfinity(origscip, -rhscoef) )
509  return SCIP_OKAY;
510 
511  /* set up data for construction */
512  SCIP_CALL( SCIPallocBufferArray(origscip, &matind, nvars + 1) );
513  SCIP_CALL( SCIPallocBufferArray(origscip, &matval, nvars + 1) );
514 
515  /* handle first row */
516  if ( ! SCIPisFeasZero(origscip, rhscoef) )
517  {
518  matind[cnt] = 0;
519  matval[cnt++] = sign * rhscoef;
520  }
521 
522  /* set up column */
523  for (v = 0; v < nvars; ++v)
524  {
525  assert( vars[v] != NULL );
526  if ( vals != NULL )
527  matval[cnt] = vals[v] * sign;
528  else
529  matval[cnt] = sign;
530  matind[cnt++] = SCIPvarGetIndex(vars[v]) + 1;
531  }
532 
533  /* now add column */
534  ub = SCIPlpiInfinity(lp);
535 
536  SCIP_CALL( SCIPlpiAddCols(lp, 1, &obj, &lb, &ub, NULL, cnt, &matbeg, matind, matval) );
537 
538  SCIPfreeBufferArray(origscip, &matval);
539  SCIPfreeBufferArray(origscip, &matind);
540 
541  return SCIP_OKAY;
542 }
543 
544 
545 /** create alternative polyhedron */
546 static
548  SCIP* origscip, /**< original SCIP instance */
549  SCIP_LPI* lp /**< alternative polyhedron */
550  )
551 {
552  SCIP_CONS** origconss;
553  int norigconss;
554  int c;
555  int v;
556 
557  assert( origscip != NULL );
558  assert( lp != NULL );
559 
560  origconss = SCIPgetConss(origscip);
561  norigconss = SCIPgetNConss(origscip);
562 
563  for (c = 0; c < norigconss; ++c)
564  {
565  const char* origconshdlrname;
566  SCIP_CONSHDLR* origconshdlr;
567  SCIP_VAR** origconsvars;
568  SCIP_CONS* origcons;
569  int norigconsvars;
570 
571  origcons = origconss[c];
572  assert( origcons != NULL );
573 
574  origconshdlr = SCIPconsGetHdlr(origcons);
575  assert( origconshdlr != NULL );
576  origconshdlrname = SCIPconshdlrGetName(origconshdlr);
577 
578  if ( strcmp(origconshdlrname, "linear") == 0 )
579  {
580  origconsvars = SCIPgetVarsLinear(origscip, origcons);
581  norigconsvars = SCIPgetNVarsLinear(origscip, origcons);
582 
583  SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, SCIPgetValsLinear(origscip, origcons), SCIPgetRhsLinear(origscip, origcons), 1.0) );
584  SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, SCIPgetValsLinear(origscip, origcons), SCIPgetLhsLinear(origscip, origcons), -1.0) );
585  }
586  else if ( strcmp(origconshdlrname, "setppc") == 0 )
587  {
588  origconsvars = SCIPgetVarsSetppc(origscip, origcons);
589  norigconsvars = SCIPgetNVarsSetppc(origscip, origcons);
590 
591  switch ( SCIPgetTypeSetppc(origscip, origcons) )
592  {
594  SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, NULL, 1.0, 1.0) );
595  SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, NULL, 1.0, -1.0) );
596  break;
598  SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, NULL, 1.0, 1.0) );
599  break;
601  SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, NULL, 1.0, -1.0) );
602  break;
603  }
604  }
605  else if ( strcmp(origconshdlrname, "logicor") == 0 )
606  {
607  origconsvars = SCIPgetVarsLogicor(origscip, origcons);
608  norigconsvars = SCIPgetNVarsLogicor(origscip, origcons);
609 
610  SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, NULL, 1.0, -1.0) );
611  }
612  else if ( strcmp(origconshdlrname, "knapsack") == 0 )
613  {
614  SCIP_Longint* origweights;
615  SCIP_Real* consvals;
616 
617  origconsvars = SCIPgetVarsKnapsack(origscip, origcons);
618  norigconsvars = SCIPgetNVarsKnapsack(origscip, origcons);
619 
620  /* copy Longint array to SCIP_Real array */
621  origweights = SCIPgetWeightsKnapsack(origscip, origcons);
622  SCIP_CALL( SCIPallocBufferArray(origscip, &consvals, norigconsvars) );
623 
624  for ( v = 0; v < norigconsvars; ++v )
625  consvals[v] = (SCIP_Real) origweights[v];
626 
627  SCIP_CALL( createAltLPColumn(origscip, lp, norigconsvars, origconsvars, consvals, (SCIP_Real) SCIPgetCapacityKnapsack(origscip, origcons), 1.0) );
628 
629  SCIPfreeBufferArray(origscip, &consvals);
630  }
631  else if ( strcmp(origconshdlrname, "varbound") == 0 )
632  {
633  SCIP_VAR* consvars[2];
634  SCIP_Real consvals[2];
635 
636  consvars[0] = SCIPgetVarVarbound(origscip, origcons);
637  consvars[1] = SCIPgetVbdvarVarbound(origscip, origcons);
638 
639  consvals[0] = 1.0;
640  consvals[1] = SCIPgetVbdcoefVarbound(origscip, origcons);
641 
642  SCIP_CALL( createAltLPColumn(origscip, lp, 2, consvars, consvals, SCIPgetRhsVarbound(origscip, origcons), 1.0) );
643  SCIP_CALL( createAltLPColumn(origscip, lp, 2, consvars, consvals, SCIPgetLhsVarbound(origscip, origcons), -1.0) );
644  }
645  else
646  {
647  SCIPwarningMessage(origscip, "Cannot handle constraints of type <%s>.\n", origconshdlrname);
648  }
649  }
650  return SCIP_OKAY;
651 }
652 
653 /** Get next int from string s */
654 static
656  char** s /**< string pointer (modified) */
657  )
658 {
659  int tmp;
660 
661  /* skip whitespace */
662  while ( isspace(**s) )
663  ++(*s);
664  tmp = atoi(*s);
665 
666  /* skip number */
667  while ( (**s != 0) && (! isspace(**s)) )
668  ++(*s);
669 
670  return tmp;
671 }
672 
673 /** Get next pair from string s */
674 static
676  char** s, /**< string pointer (modified) */
677  int* idx, /**< index of value */
678  SCIP_Real* val /**< value */
679  )
680 {
681  int status;
682 
683  assert( idx != NULL );
684  assert( val != NULL );
685 
686  /* skip whitespace */
687  while ( isspace(**s) )
688  ++(*s);
689 
690  status = sscanf(*s, "%d:%lf", idx, val);
691  if ( status != 2 )
692  return FALSE;
693 
694  /* skip numbers */
695  while ( (**s != 0) && (! isspace(**s)) )
696  ++(*s);
697 
698  return TRUE;
699 }
700 
701 /** read classification instance in LIBSVM format and generate infeasible problem
702  *
703  * Format:
704  * class type (+1, -1)
705  * points in sparse format: index:value
706  */
707 static
709  SCIP* scip, /**< SCIP data structure */
710  const char* filename, /**< name of file to read */
711  SCIP_Bool boundsonclassifier, /**< Use unit bounds on classifier? */
712  int* nclass1, /**< pointer to store the number of points in class 1 */
713  int* nclass2 /**< pointer to store the number of points in class 2 */
714  )
715 {
716  char name[SCIP_MAXSTRLEN];
717  char* buffer;
718  FILE *file;
719  SCIP_VAR** vars;
720  SCIP_VAR** consvars;
721  SCIP_Real* consvals;
722  SCIP_VAR* rhsvar;
723  SCIP_CONS* cons;
724  SCIP_Real delta = 1.0;
725  int class1 = INT_MAX;
726  int class2 = INT_MAX;
727  int nmaxvars = 100;
728  int nconss = 0;
729  int j;
730 
731  assert( nclass1 != NULL );
732  assert( nclass2 != NULL );
733  *nclass1 = 0;
734  *nclass2 = 0;
735 
736  /* open file */
737  file = fopen(filename, "r");
738  if ( file == NULL )
739  {
740  SCIPerrorMessage("Could not open file <%s>.\n", filename);
741  SCIPprintSysError(filename);
742  return SCIP_NOFILE;
743  }
744 
745  /* reserve space for string */
746  SCIP_CALL( SCIPallocBufferArray(scip, &buffer, 100 * SCIP_MAXSTRLEN) );
747 
748  /* init variables */
749  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nmaxvars) );
750  for (j = 0; j < nmaxvars; ++j)
751  vars[j] = NULL;
752 
753  /* init constraint data */
754  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nmaxvars + 1) );
755  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nmaxvars + 1) );
756 
757  /* create rhs variable */
758  SCIP_CALL( SCIPcreateVar(scip, &rhsvar, "b", -SCIPinfinity(scip), SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
759  SCIP_CALL( SCIPaddVar(scip, rhsvar) );
760 
761  /* determine rhs */
762  if ( boundsonclassifier )
763  delta = 10.0 * SCIPfeastol(scip);
764 
765  /* loop through file */
766  while ( ! feof(file) )
767  {
768  SCIP_Real val;
769  int idx;
770  int class;
771  int cnt = 0;
772  char* s;
773 
774  SCIPdebugMsg(scip, "constraint: %d\n", nconss);
775 
776  /* read line */
777  if ( fgets(buffer, 100 * SCIP_MAXSTRLEN, file) == NULL )
778  break;
779  s = buffer;
780 
781  /* parse class - allow for arbitrary classes */
782  class = getNextInt(&s);
783  if ( class1 == INT_MAX )
784  {
785  class1 = class;
786  class = 1;
787  ++(*nclass1);
788  }
789  else if ( class != class1 && class2 == INT_MAX )
790  {
791  class2 = class;
792  class = -1;
793  ++(*nclass2);
794  }
795  else
796  {
797  if ( class != class1 && class != class2 )
798  {
799  SCIPerrorMessage("Invalid class value: %d (valid: %d, %d).\n", class, class1, class2);
800  return SCIP_READERROR;
801  }
802  if ( class == class1 )
803  {
804  class = 1;
805  ++(*nclass1);
806  }
807  else
808  {
809  assert( class == class2 );
810  class = -1;
811  ++(*nclass2);
812  }
813  }
814 
815  /* parse values */
816  while ( getNextPair(&s, &idx, &val) )
817  {
818  if ( idx <= 0 )
819  {
820  SCIPerrorMessage("Index %d out of range.\n", idx);
821  return SCIP_READERROR;
822  }
823 
824  /* possibly resize arrays */
825  if ( idx >= nmaxvars )
826  {
827  int newsize;
828 
829  newsize = 2 * nmaxvars;
830  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, newsize + 1) );
831  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, newsize + 1) );
832  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, newsize) );
833 
834  for (j = nmaxvars; j < newsize; ++j)
835  vars[j] = NULL;
836 
837  nmaxvars = newsize;
838  }
839  else
840  {
841  /* check if we do not yet know the variable */
842  if ( vars[idx-1] == NULL )
843  {
844  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "w#%d", idx-1);
845  if ( boundsonclassifier )
846  {
847  SCIP_CALL( SCIPcreateVar(scip, &vars[idx-1], name, -1.0, 1.0, 0.0, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
848  }
849  else
850  {
851  SCIP_CALL( SCIPcreateVar(scip, &vars[idx-1], name, -SCIPinfinity(scip), SCIPinfinity(scip), 0.0, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
852  }
853  SCIP_CALL( SCIPaddVar(scip, vars[idx-1]) );
854  }
855  assert( vars[idx-1] != NULL );
856 
857  consvars[cnt] = vars[idx-1];
858  consvals[cnt++] = ((SCIP_Real) class) * val;
859  assert( cnt <= nmaxvars );
860  }
861  }
862 
863  /* create linear constraint */
864  consvars[cnt] = rhsvar;
865  consvals[cnt++] = -1.0 * ((SCIP_Real) class);
866 
867  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "datapoint%d", nconss++);
868  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name, cnt, consvars, consvals, delta, SCIPinfinity(scip)) );
869  SCIP_CALL( SCIPaddCons(scip, cons) );
870  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
871  }
872 
873  fclose( file );
874 
875  /* release variables */
876  for (j = 0; j < nmaxvars; ++j)
877  {
878  if ( vars[j] != NULL )
879  {
880  SCIP_CALL( SCIPreleaseVar(scip, &vars[j]) );
881  }
882  }
883  SCIP_CALL( SCIPreleaseVar(scip, &rhsvar) );
884 
885  SCIPfreeBufferArray(scip, &consvals);
886  SCIPfreeBufferArray(scip, &consvars);
887  SCIPfreeBufferArray(scip, &vars);
888 
889  SCIPfreeBufferArray(scip, &buffer);
890 
891  return SCIP_OKAY;
892 }
893 
894 /** find linear classifier that minimizes the number of misclassified points */
895 static
897  const char* filename, /**< problem name */
898  const char* settingsname, /**< name of parameter file (or NULL) */
899  SCIP_Real timelimit, /**< time limit read from arguments */
900  SCIP_Real memlimit, /**< memory limit read from arguments */
901  int dispfreq /**< display frequency */
902  )
903 {
904  char probname[SCIP_MAXSTRLEN];
905  char name[SCIP_MAXSTRLEN];
906  BENDERS_DATA data;
907  SCIP* masterscip;
908  SCIP* origscip;
909  SCIP_STATUS status;
910  SCIP_LPI* lp;
911  SCIP_Real lhs = -1.0;
912  SCIP_Real rhs = -1.0;
913  SCIP_VAR** origvars;
914  SCIP_Real obj = 0.0;
915  SCIP_Real lb = 0.0;
916  SCIP_Real ub;
917  int nclass1;
918  int nclass2;
919  int norigvars;
920  int nrows = 0;
921  int m = 0;
922  int v;
923 
924  /* parameters */
925  SCIP_Bool solvemasterapprox;
926  SCIP_Longint masterstallnodes;
927  SCIP_Real mastergaplimit;
928  SCIP_Bool reoptimization;
929  SCIP_Bool boundsonclassifier;
930 
931  /* create master SCIP */
932  SCIP_CALL( SCIPcreate(&masterscip) );
933  SCIP_CALL( SCIPincludeDefaultPlugins(masterscip) );
934  if ( getProblemName(filename, probname, SCIP_MAXSTRLEN) == 0 )
935  {
936  SCIPerrorMessage("Cannot extract problem name for filename <%s>.\n", filename);
937  return SCIP_ERROR;
938  }
939  SCIP_CALL( SCIPcreateProb(masterscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
941 
942  SCIPinfoMessage(masterscip, NULL, "Finding a linear classifier minimizing the number misclassifications using a Benders approach.\n");
943  SCIPinfoMessage(masterscip, NULL, "Implemented by Marc Pfetsch, 2016\n\n");
944 
945  SCIPprintVersion(masterscip, NULL);
946  SCIPinfoMessage(masterscip, NULL, "\n");
947 
948  /* add parameters */
949  SCIP_CALL( SCIPaddBoolParam(masterscip,
950  "miniisc/solvemasterapprox",
951  "Solve master problem approximately?",
952  &solvemasterapprox, TRUE, DEFAULT_SOLVEMASTERAPPROX, NULL, NULL) );
953 
954  SCIP_CALL( SCIPaddRealParam(masterscip,
955  "miniisc/mastergaplimit",
956  "gap bound for approximately solving the master problem",
957  &mastergaplimit, TRUE, DEFAULT_MASTERGAPLIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
958 
959  SCIP_CALL( SCIPaddLongintParam(masterscip,
960  "miniisc/masterstallnodes",
961  "stall nodes for the master problem",
962  &masterstallnodes, TRUE, DEFAULT_MASTERSTALLNODES, 0L, SCIP_LONGINT_MAX, NULL, NULL) );
963 
964  SCIP_CALL( SCIPaddBoolParam(masterscip,
965  "miniisc/reoptimization",
966  "Use reoptimization to solve master problem?",
967  &reoptimization, TRUE, DEFAULT_REOPTIMIZATION, NULL, NULL) );
968 
969  SCIP_CALL( SCIPaddBoolParam(masterscip,
970  "miniisc/boundsonclassifier",
971  "Add unit bounds on the classifier?",
972  &boundsonclassifier, TRUE, DEFAULT_BOUNDSONCLASSIFIER, NULL, NULL) );
973 
974  /* read parameters if required */
975  if ( settingsname != NULL )
976  {
977  if ( SCIPfileExists(settingsname) )
978  {
979  SCIPinfoMessage(masterscip, NULL, "\nreading user parameter file <%s> ...\n\n", settingsname);
980  SCIP_CALL( SCIPreadParams(masterscip, settingsname) );
981  SCIP_CALL( SCIPwriteParams(masterscip, NULL, FALSE, TRUE) );
982  }
983  else
984  {
985  SCIPwarningMessage(masterscip, NULL, "\nparameter file <%s> not found - using default parameters.\n", settingsname);
986  }
987  }
988 
989  if ( ! SCIPisInfinity(masterscip, timelimit) )
990  SCIPinfoMessage(masterscip, NULL, "limits/time = %f\n\n", timelimit);
991 
992  SCIPinfoMessage(masterscip, NULL, "Input file:\t%s\n", filename);
993  SCIPinfoMessage(masterscip, NULL, "Problem name:\t%s\n\n", probname);
994  if ( boundsonclassifier )
995  SCIPinfoMessage(masterscip, NULL, "Using unit bounds on classifier.\n");
996 
997  /* ----------------------------------------------------------------------------------------*/
998 
999  /* read instance to create alternative polyhedron */
1000  SCIP_CALL( SCIPcreate(&origscip) );
1001 
1002  /* include default SCIP plugins */
1003  SCIP_CALL( SCIPincludeDefaultPlugins(origscip) );
1004 
1005  /* create problem */
1006  SCIP_CALL( SCIPcreateProbBasic(origscip, "infeasible") );
1007 
1008  /* read data and create problem */
1009  SCIP_CALL( readLIBSVM(origscip, filename, boundsonclassifier, &nclass1, &nclass2) );
1010 
1011  SCIPinfoMessage(masterscip, NULL, "Number of data point in class 1: %d.\n", nclass1);
1012  SCIPinfoMessage(masterscip, NULL, "Number of data point in class 2: %d.\n\n", nclass2);
1013 
1014  if ( boundsonclassifier )
1015  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "classify-bnd-%s.lp", probname);
1016  else
1017  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "classify-%s.lp", probname);
1018  SCIPinfoMessage(masterscip, NULL, "Writing infeasible classification model to file: %s.\n", name);
1019  SCIP_CALL( SCIPwriteOrigProblem(origscip, name, "lp", FALSE) );
1020 
1021  /* check that we have an LP */
1022  if ( SCIPgetNOrigBinVars(origscip) + SCIPgetNOrigIntVars(origscip) > 0 )
1023  {
1024  SCIPinfoMessage(masterscip, NULL, "ERROR: input file contains integer variables. The code only works for LPs.\n");
1025  return SCIP_ERROR;
1026  }
1027 
1028  /* ----------------------------------------------------------------------------------------*/
1029 
1030  /* init alternative polyhedron */
1031  SCIP_CALL( SCIPlpiCreate(&lp, SCIPgetMessagehdlr(masterscip), "altlp", SCIP_OBJSEN_MINIMIZE) );
1032 
1033  /* init parameters */
1038 
1039  /* add first row */
1040  SCIP_CALL( SCIPlpiAddRows(lp, 1, &lhs, &rhs, NULL, 0, NULL, NULL, NULL) );
1041 
1042  norigvars = SCIPgetNOrigVars(origscip);
1043  origvars = SCIPgetOrigVars(origscip);
1044 
1045  /* add rows for each variable */
1046  lhs = 0.0;
1047  rhs = 0.0;
1048  for (v = 0; v < norigvars; ++v)
1049  {
1050  SCIP_CALL( SCIPlpiAddRows(lp, 1, &lhs, &rhs, NULL, 0, NULL, NULL, NULL) );
1051  }
1052  SCIP_CALL( SCIPlpiGetNRows(lp, &nrows) );
1053 
1054  /* create alternative polyhedron */
1055  SCIP_CALL( createAltLP(origscip, lp) );
1056 
1057  /* get number of constraints */
1058  SCIP_CALL( SCIPlpiGetNCols(lp, &m) );
1059 
1060  /* add columns for bounds */
1061  ub = SCIPlpiInfinity(lp);
1062  for (v = 0; v < norigvars; ++v)
1063  {
1064  SCIP_Real val;
1065  SCIP_VAR* var;
1066  SCIP_Real matval[2];
1067  int matind[2];
1068  int matbeg = 0;
1069  int cnt = 0;
1070 
1071  var = origvars[v];
1072  assert( var != NULL );
1073  assert( 0 <= SCIPvarGetIndex(var) && SCIPvarGetIndex(var) < nrows );
1074 
1075  /* if the lower bound is finite */
1076  val = SCIPvarGetLbGlobal(var);
1077  if ( ! SCIPisInfinity(origscip, -val) )
1078  {
1079  if ( ! SCIPisZero(origscip, val) )
1080  {
1081  matind[cnt] = 0;
1082  matval[cnt++] = -val;
1083  }
1084  matind[cnt] = SCIPvarGetIndex(var) + 1;
1085  matval[cnt++] = -1.0;
1086  SCIP_CALL( SCIPlpiAddCols(lp, 1, &obj, &lb, &ub, NULL, cnt, &matbeg, matind, matval) );
1087  }
1088 
1089  /* if the upper bound is finite */
1090  cnt = 0;
1091  val = SCIPvarGetUbGlobal(var);
1092  if ( ! SCIPisInfinity(origscip, val) )
1093  {
1094  if ( ! SCIPisZero(origscip, val) )
1095  {
1096  matind[cnt] = 0;
1097  matval[cnt++] = val;
1098  }
1099  matind[cnt] = SCIPvarGetIndex(var) + 1;
1100  matval[cnt++] = 1.0;
1101  SCIP_CALL( SCIPlpiAddCols(lp, 1, &obj, &lb, &ub, NULL, cnt, &matbeg, matind, matval) );
1102  }
1103  }
1104 
1105  /* free SCIP instance */
1106  SCIP_CALL( SCIPfree(&origscip) );
1107 
1108 #ifdef SCIP_OUTPUT
1109  SCIP_CALL( SCIPlpiWriteLP(lp, "alt.lp") );
1110 #endif
1111 
1112  /* ----------------------------------------------------------------------------------------*/
1113  /* initialize master problem */
1114  for (v = 0; v < m; ++v)
1115  {
1116  SCIP_VAR* var;
1117 
1118  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "y%d", v);
1119  SCIP_CALL( SCIPcreateVar(masterscip, &var, name, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1120  SCIP_CALL( SCIPaddVar(masterscip, var) );
1121  SCIP_CALL( SCIPreleaseVar(masterscip, &var) );
1122  }
1123 
1124  /* run Benders algorithm */
1125  data.lp = lp;
1126  data.m = m;
1127  SCIP_CALL( runBenders(masterscip, cutoracle, &data, timelimit, memlimit, dispfreq, reoptimization, solvemasterapprox,
1128  masterstallnodes, mastergaplimit, SCIP_VERBLEVEL_NORMAL, &status) );
1129 
1130  SCIP_CALL( SCIPlpiFree(&lp) );
1131 
1132  SCIP_CALL( SCIPfree(&masterscip) );
1133 
1134  return SCIP_OKAY;
1135 }
1136 
1137 
1138 
1139 
1140 /** main function */
1141 int
1143  int argc, /**< number of shell parameters */
1144  char** argv /**< array with shell parameters */
1145  )
1146 {
1147  SCIP_RETCODE retcode;
1148  const char* filename;
1149  const char* settingsname;
1150  SCIP_Real timelimit;
1151  SCIP_Real memlimit;
1152  SCIP_Longint nodelimit;
1153  int dispfreq;
1154 
1155  retcode = readArguments(argc, argv, &filename, &settingsname, &timelimit, &memlimit, &nodelimit, &dispfreq);
1156  if ( retcode != SCIP_OKAY )
1157  return -1;
1158  assert( filename != NULL );
1159 
1160  /* read file */
1161  if ( ! SCIPfileExists(filename) )
1162  {
1163  SCIPerrorMessage("file <%s> does not exist.\n", filename);
1164  return -1;
1165  }
1166 
1167  retcode = solveClassification(filename, settingsname, timelimit, memlimit, dispfreq);
1168  if ( retcode != SCIP_OKAY )
1169  {
1170  SCIPprintError(retcode);
1171  return -1;
1172  }
1173 
1175 
1176  return 0;
1177 }
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPlpiGetNRows(SCIP_LPI *lpi, int *nrows)
Definition: lpi_clp.cpp:1408
#define DEFAULT_REOPTIMIZATION
Definition: classify.c:32
#define BMScheckEmptyMemory()
Definition: memory.h:148
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
Definition: lpi_clp.cpp:634
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9394
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
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:2774
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
#define DEFAULT_SOLVEMASTERAPPROX
Definition: classify.c:30
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPlpiSetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int ival)
Definition: lpi_clp.cpp:3678
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:1796
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:107
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2430
static SCIP_RETCODE fixAltLPVariable(SCIP_LPI *lp, int ind)
Definition: classify.c:61
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
interface methods for specific LP solvers
static SCIP_RETCODE createAltLP(SCIP *origscip, SCIP_LPI *lp)
Definition: classify.c:547
#define FALSE
Definition: def.h:87
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:102
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:198
static SCIP_Bool getNextPair(char **s, int *idx, SCIP_Real *val)
Definition: classify.c:675
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:599
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2403
SCIP_RETCODE SCIPlpiGetNCols(SCIP_LPI *lpi, int *ncols)
Definition: lpi_clp.cpp:1426
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:79
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3086
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_LONGINT_MAX
Definition: def.h:163
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
Definition: lpi_clp.cpp:522
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:170
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:749
static SCIP_RETCODE readLIBSVM(SCIP *scip, const char *filename, SCIP_Bool boundsonclassifier, int *nclass1, int *nclass2)
Definition: classify.c:708
SCIP_Bool SCIPlpiIsPrimalUnbounded(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2474
int SCIPlpiGetInternalStatus(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2738
SCIP_Bool SCIPfileExists(const char *filename)
Definition: misc.c:10958
#define DEFAULT_MASTERGAPLIMIT
Definition: classify.c:31
SCIP_RETCODE SCIPlpiSolveDual(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:1871
SCIP_Bool SCIPlpiIsStable(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2633
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1240
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:905
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPlpiWriteLP(SCIP_LPI *lpi, const char *fname)
Definition: lpi_clp.cpp:3987
static SCIP_RETCODE solveClassification(const char *filename, const char *settingsname, SCIP_Real timelimit, SCIP_Real memlimit, int dispfreq)
Definition: classify.c:896
#define DEFAULT_BOUNDSONCLASSIFIER
Definition: classify.c:34
static SCIP_RETCODE checkAltLPInfeasible(SCIP *masterscip, SCIP_LPI *lp, SCIP_Bool primal, SCIP_Bool *infeasible, SCIP_Bool *error)
Definition: classify.c:183
#define SCIPerrorMessage
Definition: pub_message.h:55
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2768
static SCIP_RETCODE fixAltLPVariables(SCIP *masterscip, int nmastervars, SCIP_Bool *S, SCIP_LPI *lp)
Definition: classify.c:78
SCIP_Bool SCIPlpiIsPrimalInfeasible(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2488
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_LPI * lp
Definition: classify.c:40
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
static BENDERS_CUTORACLE(cutoracle)
Definition: classify.c:312
SCIP_Bool SCIPlpiExistsPrimalRay(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2436
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
int main(int argc, char **argv)
Definition: classify.c:1142
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
void SCIPprintVersion(SCIP *scip, FILE *file)
Definition: scip_general.c:146
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:3905
void SCIPprintSysError(const char *message)
Definition: misc.c:10664
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:58
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9440
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2473
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8105
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
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:105
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
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_Bool SCIPlpiIsOptimal(SCIP_LPI *lpi)
Definition: lpi_clp.cpp:2609
#define DEFAULT_MASTERSTALLNODES
Definition: classify.c:33
SCIP_RETCODE SCIPlpiChgBounds(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
Definition: lpi_clp.cpp:1075
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9417
#define SCIP_REAL_MAX
Definition: def.h:178
#define SCIP_CALL_PARAM(x)
Definition: classify.c:46
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:86
int SCIPgetNOrigIntVars(SCIP *scip)
Definition: scip_prob.c:2484
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1666
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3040
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_RETCODE SCIPreadParams(SCIP *scip, const char *filename)
Definition: scip_param.c:742
static int getNextInt(char **s)
Definition: classify.c:655
#define SCIP_Real
Definition: def.h:177
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
#define SCIP_Longint
Definition: def.h:162
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17590
run Benders algorithm
read comand line arguments
int getProblemName(const char *filename, char *probname, int maxsize)
Definition: readargs.c:28
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPwriteParams(SCIP *scip, const char *filename, SCIP_Bool comments, SCIP_Bool onlychanged)
Definition: scip_param.c:783
int SCIPgetNOrigBinVars(SCIP *scip)
Definition: scip_prob.c:2457
void SCIPprintError(SCIP_RETCODE retcode)
Definition: scip_general.c:211
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
default SCIP plugins
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
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:130
static SCIP_RETCODE unfixAltLPVariables(SCIP *masterscip, int nmastervars, SCIP_Bool *S, SCIP_LPI *lp)
Definition: classify.c:126
static SCIP_RETCODE createAltLPColumn(SCIP *origscip, SCIP_LPI *lp, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real rhscoef, SCIP_Real sign)
Definition: classify.c:484
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:48
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119