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