39#define DEFAULT_SOLVEMASTERAPPROX FALSE
40#define DEFAULT_MASTERGAPLIMIT 0.1
41#define DEFAULT_REOPTIMIZATION FALSE
42#define DEFAULT_MASTERSTALLNODES 5000L
43#define DEFAULT_BOUNDSONCLASSIFIER FALSE
55#define SCIP_CALL_PARAM(x) do \
57 SCIP_RETCODE _restat_; \
58 if ( (_restat_ = (x)) != SCIP_OKAY && (_restat_ != SCIP_PARAMETERUNKNOWN) ) \
60 SCIPerrorMessage("[%s:%d] Error <%d> in function call\n", __FILE__, __LINE__, _restat_); \
109 for (j = 0; j < nmastervars; ++j)
142 SCIP_Real* lb =
NULL;
143 SCIP_Real* ub =
NULL;
157 for (j = 0; j < nmastervars; ++j)
196 SCIP_Bool* infeasible,
257 SCIPwarningMessage(masterscip,
"The dual simplex produced a primal ray. Retrying with primal ...\n");
328 SCIP_Real value = 0.0;
341 assert( data->m == nmastervars );
350 assert( nmastervars <= ncols );
354 for (j = 0; j < nmastervars; ++j)
357 if ( mastersolution[j] > 0.5 )
370 SCIP_Bool infeasible;
371 SCIP_Real candobj = -1.0;
400 SCIPdebugMessage(
" size: %4d produced possible cover with objective value %f.\n", size, value);
408 for (j = 0; j < nmastervars; ++j)
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);
447 for (j = 0; j < nmastervars; ++j)
451 vars[cnt++] = mastervars[j];
457 SCIP_CALL(
SCIPcreateConsLogicor(masterscip, &cons, name, cnt,
vars,
FALSE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
TRUE,
TRUE,
FALSE) );
459 SCIP_CALL(
SCIPcreateConsLogicor(masterscip, &cons,
"", cnt,
vars,
FALSE,
TRUE,
TRUE,
TRUE,
TRUE,
FALSE,
FALSE,
TRUE,
TRUE,
FALSE) );
480 while (step < nmastervars);
528 matval[cnt++] = sign * rhscoef;
532 for (v = 0; v <
nvars; ++v)
536 matval[cnt] = vals[v] * sign;
572 for (
c = 0;
c < norigconss; ++
c)
574 const char* origconshdlrname;
580 origcons = origconss[
c];
587 if ( strcmp(origconshdlrname,
"linear") == 0 )
595 else if ( strcmp(origconshdlrname,
"setppc") == 0 )
614 else if ( strcmp(origconshdlrname,
"logicor") == 0 )
621 else if ( strcmp(origconshdlrname,
"knapsack") == 0 )
623 SCIP_Longint* origweights;
633 for ( v = 0; v < norigconsvars; ++v )
634 consvals[v] = (SCIP_Real) origweights[v];
640 else if ( strcmp(origconshdlrname,
"varbound") == 0 )
643 SCIP_Real consvals[2];
656 SCIPwarningMessage(origscip,
"Cannot handle constraints of type <%s>.\n", origconshdlrname);
671 while ( isspace(**s) )
676 while ( (**s != 0) && (! isspace(**s)) )
696 while ( isspace(**s) )
699 status = sscanf(*s,
"%d:%lf", idx, val);
704 while ( (**s != 0) && (! isspace(**s)) )
719 const char* filename,
720 SCIP_Bool boundsonclassifier,
733 SCIP_Real delta = 1.0;
734 int class1 = INT_MAX;
735 int class2 = INT_MAX;
746 file = fopen(filename,
"r");
759 for (j = 0; j < nmaxvars; ++j)
767 SCIP_CALL(
SCIPcreateVar(
scip, &rhsvar,
"b", -
SCIPinfinity(
scip),
SCIPinfinity(
scip), 0.0,
SCIP_VARTYPE_CONTINUOUS,
TRUE,
FALSE,
NULL,
NULL,
NULL,
NULL,
NULL) );
771 if ( boundsonclassifier )
775 while ( ! feof(file) )
792 if ( class1 == INT_MAX )
798 else if (
class != class1 && class2 == INT_MAX )
806 if (
class != class1 &&
class != class2 )
808 SCIPerrorMessage(
"Invalid class value: %d (valid: %d, %d).\n",
class, class1, class2);
811 if (
class == class1 )
818 assert(
class == class2 );
834 if ( idx >= nmaxvars )
838 newsize = 2 * nmaxvars;
843 for (j = nmaxvars; j < newsize; ++j)
854 if ( boundsonclassifier )
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) );
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) );
866 consvars[cnt] =
vars[idx-1];
867 consvals[cnt++] = ((
SCIP_Real)
class) * val;
868 assert( cnt <= nmaxvars );
873 consvars[cnt] = rhsvar;
874 consvals[cnt++] = -1.0 * ((
SCIP_Real)
class);
885 for (j = 0; j < nmaxvars; ++j)
906 const char* filename,
907 const char* settingsname,
920 SCIP_Real lhs = -1.0;
921 SCIP_Real rhs = -1.0;
934 SCIP_Bool solvemasterapprox;
935 SCIP_Longint masterstallnodes;
936 SCIP_Real mastergaplimit;
937 SCIP_Bool reoptimization;
938 SCIP_Bool boundsonclassifier;
945 SCIPerrorMessage(
"Cannot extract problem name for filename <%s>.\n", filename);
951 SCIPinfoMessage(masterscip,
NULL,
"Finding a linear classifier minimizing the number misclassifications using a Benders approach.\n");
959 "miniisc/solvemasterapprox",
960 "Solve master problem approximately?",
964 "miniisc/mastergaplimit",
965 "gap bound for approximately solving the master problem",
969 "miniisc/masterstallnodes",
970 "stall nodes for the master problem",
974 "miniisc/reoptimization",
975 "Use reoptimization to solve master problem?",
979 "miniisc/boundsonclassifier",
980 "Add unit bounds on the classifier?",
984 if ( settingsname !=
NULL )
988 SCIPinfoMessage(masterscip,
NULL,
"\nreading user parameter file <%s> ...\n\n", settingsname);
994 SCIPwarningMessage(masterscip,
NULL,
"\nparameter file <%s> not found - using default parameters.\n", settingsname);
1003 if ( boundsonclassifier )
1023 if ( boundsonclassifier )
1027 SCIPinfoMessage(masterscip,
NULL,
"Writing infeasible classification model to file: %s.\n", name);
1033 SCIPinfoMessage(masterscip,
NULL,
"ERROR: input file contains integer variables. The code only works for LPs.\n");
1057 for (v = 0; v < norigvars; ++v)
1071 for (v = 0; v < norigvars; ++v)
1075 SCIP_Real matval[2];
1091 matval[cnt++] = -val;
1094 matval[cnt++] = -1.0;
1106 matval[cnt++] = val;
1109 matval[cnt++] = 1.0;
1123 for (v = 0; v < m; ++v)
1128 SCIP_CALL(
SCIPcreateVar(masterscip, &
var, name, 0.0, 1.0, 1.0,
SCIP_VARTYPE_BINARY,
TRUE,
FALSE,
NULL,
NULL,
NULL,
NULL,
NULL) );
1136 SCIP_CALL(
runBenders(masterscip, cutoracle, &data, timelimit, memlimit, dispfreq, reoptimization, solvemasterapprox,
1157 const char* filename;
1158 const char* settingsname;
1159 SCIP_Real timelimit;
1161 SCIP_Longint nodelimit;
1164 retcode =
readArguments(argc, argv, &filename, &settingsname, &timelimit, &memlimit, &nodelimit, &dispfreq);
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)
@ BENDERS_STATUS_ADDEDCUT
#define BENDERS_CUTORACLE(x)
#define SCIP_CALL_PARAM(x)
#define DEFAULT_MASTERSTALLNODES
int main(int argc, char **argv)
static SCIP_RETCODE solveClassification(const char *filename, const char *settingsname, SCIP_Real timelimit, SCIP_Real memlimit, int dispfreq)
static int getNextInt(char **s)
#define DEFAULT_BOUNDSONCLASSIFIER
static SCIP_RETCODE fixAltLPVariables(SCIP *masterscip, int nmastervars, SCIP_Bool *S, SCIP_LPI *lp)
static SCIP_RETCODE readLIBSVM(SCIP *scip, const char *filename, SCIP_Bool boundsonclassifier, int *nclass1, int *nclass2)
static SCIP_RETCODE createAltLPColumn(SCIP *origscip, SCIP_LPI *lp, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real rhscoef, SCIP_Real sign)
static SCIP_RETCODE fixAltLPVariable(SCIP_LPI *lp, int ind)
#define DEFAULT_REOPTIMIZATION
static SCIP_Bool getNextPair(char **s, int *idx, SCIP_Real *val)
#define DEFAULT_SOLVEMASTERAPPROX
static SCIP_RETCODE createAltLP(SCIP *origscip, SCIP_LPI *lp)
static SCIP_RETCODE unfixAltLPVariables(SCIP *masterscip, int nmastervars, SCIP_Bool *S, SCIP_LPI *lp)
static SCIP_RETCODE checkAltLPInfeasible(SCIP *masterscip, SCIP_LPI *lp, SCIP_Bool primal, SCIP_Bool *infeasible, SCIP_Bool *error)
#define DEFAULT_MASTERGAPLIMIT
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
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)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
@ SCIP_SETPPCTYPE_PARTITIONING
@ SCIP_SETPPCTYPE_COVERING
@ SCIP_SETPPCTYPE_PACKING
SCIP_Bool SCIPfileExists(const char *filename)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
int SCIPgetNOrigBinVars(SCIP *scip)
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
int SCIPgetNOrigIntVars(SCIP *scip)
SCIP_CONS ** SCIPgetConss(SCIP *scip)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNConss(SCIP *scip)
int SCIPgetNOrigVars(SCIP *scip)
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
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)
SCIP_Real SCIPlpiInfinity(SCIP_LPI *lpi)
SCIP_Bool SCIPlpiExistsPrimalRay(SCIP_LPI *lpi)
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)
SCIP_RETCODE SCIPlpiWriteLP(SCIP_LPI *lpi, const char *fname)
int SCIPlpiGetInternalStatus(SCIP_LPI *lpi)
SCIP_RETCODE SCIPlpiChgBounds(SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
SCIP_Bool SCIPlpiIsPrimalUnbounded(SCIP_LPI *lpi)
SCIP_RETCODE SCIPlpiFree(SCIP_LPI **lpi)
SCIP_RETCODE SCIPlpiSetIntpar(SCIP_LPI *lpi, SCIP_LPPARAM type, int ival)
SCIP_Bool SCIPlpiIsOptimal(SCIP_LPI *lpi)
SCIP_RETCODE SCIPlpiGetSol(SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
SCIP_Bool SCIPlpiIsPrimalInfeasible(SCIP_LPI *lpi)
SCIP_RETCODE SCIPlpiSolveDual(SCIP_LPI *lpi)
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)
SCIP_RETCODE SCIPlpiSolvePrimal(SCIP_LPI *lpi)
SCIP_RETCODE SCIPlpiCreate(SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
SCIP_Bool SCIPlpiIsStable(SCIP_LPI *lpi)
SCIP_RETCODE SCIPlpiGetNCols(SCIP_LPI *lpi, int *ncols)
SCIP_RETCODE SCIPlpiGetNRows(SCIP_LPI *lpi, int *nrows)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
void SCIPprintError(SCIP_RETCODE retcode)
void SCIPprintVersion(SCIP *scip, FILE *file)
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)
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)
SCIP_RETCODE SCIPreadParams(SCIP *scip, const char *filename)
SCIP_RETCODE SCIPwriteParams(SCIP *scip, const char *filename, SCIP_Bool comments, SCIP_Bool onlychanged)
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)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
#define SCIPallocClearBufferArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPreallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
int SCIPvarGetIndex(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
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)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
int SCIPsnprintf(char *t, int len, const char *s,...)
void SCIPprintSysError(const char *message)
assert(minobj< SCIPgetCutoffbound(scip))
interface methods for specific LP solvers
#define BMScheckEmptyMemory()
SCIP_RETCODE readArguments(int argc, char **argv, const char **filename, const char **settingsname, SCIP_Real *timelimit, SCIP_Real *memlimit, SCIP_Longint *nodelimit, int *dispfreq)
int getProblemName(const char *filename, char *probname, int maxsize)
read comand line arguments
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
enum SCIP_Retcode SCIP_RETCODE
enum SCIP_Status SCIP_STATUS
@ SCIP_VARTYPE_CONTINUOUS