determine linear classifier using a Benders approach
Definition in file classify.c.
#include <string.h>
#include <ctype.h>
#include <scip/scipdefplugins.h>
#include <lpi/lpi.h>
#include "benders.h"
#include "readargs.h"
Go to the source code of this file.
Data Structures | |
struct | BENDERS_Data |
Macros | |
#define | DEFAULT_SOLVEMASTERAPPROX FALSE |
#define | DEFAULT_MASTERGAPLIMIT 0.1 |
#define | DEFAULT_REOPTIMIZATION FALSE |
#define | DEFAULT_MASTERSTALLNODES 5000L |
#define | DEFAULT_BOUNDSONCLASSIFIER FALSE |
#define | SCIP_CALL_PARAM(x) |
Functions | |
static SCIP_RETCODE | fixAltLPVariable (SCIP_LPI *lp, int ind) |
static SCIP_RETCODE | fixAltLPVariables (SCIP *masterscip, int nmastervars, SCIP_Bool *S, 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) |
static | BENDERS_CUTORACLE (cutoracle) |
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 | createAltLP (SCIP *origscip, SCIP_LPI *lp) |
static int | getNextInt (char **s) |
static SCIP_Bool | getNextPair (char **s, int *idx, SCIP_Real *val) |
static SCIP_RETCODE | readLIBSVM (SCIP *scip, const char *filename, SCIP_Bool boundsonclassifier, int *nclass1, int *nclass2) |
static SCIP_RETCODE | solveClassification (const char *filename, const char *settingsname, SCIP_Real timelimit, SCIP_Real memlimit, int dispfreq) |
int | main (int argc, char **argv) |
#define DEFAULT_SOLVEMASTERAPPROX FALSE |
Solve master problem approximately?
Definition at line 39 of file classify.c.
Referenced by solveClassification(), and solveMinIISC().
#define DEFAULT_MASTERGAPLIMIT 0.1 |
gap bound for approximately solving the master problem
Definition at line 40 of file classify.c.
Referenced by solveClassification(), and solveMinIISC().
#define DEFAULT_REOPTIMIZATION FALSE |
Use reoptimization to solve master problem?
Definition at line 41 of file classify.c.
Referenced by solveClassification(), and solveMinIISC().
#define DEFAULT_MASTERSTALLNODES 5000L |
stall nodes for the master problem
Definition at line 42 of file classify.c.
Referenced by solveClassification(), and solveMinIISC().
#define DEFAULT_BOUNDSONCLASSIFIER FALSE |
Use unit bounds on classifier?
Definition at line 43 of file classify.c.
Referenced by solveClassification().
#define SCIP_CALL_PARAM | ( | x | ) |
Definition at line 55 of file classify.c.
Referenced by BENDERS_CUTORACLE(), checkAltLPInfeasible(), and solveClassification().
|
static |
Fix variable ind to 0
lp | alternative LP |
ind | variable that should be fixed to 0 |
Definition at line 70 of file classify.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPlpiChgBounds().
Referenced by BENDERS_CUTORACLE().
|
static |
fix variables in S to 0
masterscip | SCIP pointer |
nmastervars | number of variables in master |
S | indices to fix |
lp | alternative LP |
Definition at line 87 of file classify.c.
References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPlpiChgBounds().
Referenced by BENDERS_CUTORACLE().
|
static |
unfix variables in S
masterscip | SCIP pointer |
nmastervars | number of variables in master |
S | indices to fix |
lp | alternative LP |
Definition at line 135 of file classify.c.
References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPlpiChgBounds(), and SCIPlpiInfinity().
Referenced by BENDERS_CUTORACLE().
|
static |
Check whether the given LP is infeasible
If primal is false we assume that the problem is dual feasible, e.g., the problem was only changed by fixing bounds!
This is the workhorse for all methods that have to solve the alternative LP. We try in several ways to recover from possible stability problems.
masterscip | SCIP pointer |
lp | LP |
primal | whether we are using the primal or dual simplex |
infeasible | output: whether the LP is infeasible |
error | output: whether an error occured |
Definition at line 192 of file classify.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CALL_PARAM, SCIP_LPERROR, SCIP_LPPAR_FROMSCRATCH, SCIP_LPPAR_PRESOLVING, SCIP_LPPAR_SCALING, SCIP_OKAY, SCIPlpiExistsPrimalRay(), SCIPlpiGetInternalStatus(), SCIPlpiIsOptimal(), SCIPlpiIsPrimalInfeasible(), SCIPlpiIsPrimalUnbounded(), SCIPlpiIsStable(), SCIPlpiSetIntpar(), SCIPlpiSolveDual(), SCIPlpiSolvePrimal(), SCIPwarningMessage(), and TRUE.
Referenced by BENDERS_CUTORACLE().
|
static |
produce Benders cuts from the alternative polyhedron
input:
Definition at line 321 of file classify.c.
References assert(), BENDERS_STATUS_ADDEDCUT, BENDERS_STATUS_ERROR, BENDERS_STATUS_SUCCESS, BENDERS_STATUS_UNKNOWN, checkAltLPInfeasible(), FALSE, fixAltLPVariable(), fixAltLPVariables(), NULL, primsol, SCIP_Bool, SCIP_CALL, SCIP_CALL_PARAM, SCIP_LPPAR_FROMSCRATCH, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateConsLogicor(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPinfoMessage(), SCIPisFeasIntegral(), SCIPisFeasZero(), SCIPlpiGetNCols(), SCIPlpiGetSol(), SCIPlpiSetIntpar(), SCIPprintCons(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetObj(), TRUE, unfixAltLPVariables(), and vars.
|
static |
creates column in alternative polyhedron
origscip | SCIP pointer |
lp | alternative LP |
nvars | number of variables in column |
vars | variables for column |
vals | values for column |
rhscoef | coefficient for first row |
sign | sign (+1,-1) for column |
Definition at line 493 of file classify.c.
References assert(), NULL, nvars, obj, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPlpiAddCols(), SCIPlpiInfinity(), SCIPvarGetIndex(), and vars.
Referenced by createAltLP().
|
static |
create alternative polyhedron
origscip | original SCIP instance |
lp | alternative polyhedron |
Definition at line 556 of file classify.c.
References assert(), c, createAltLPColumn(), NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPfreeBufferArray, SCIPgetCapacityKnapsack(), SCIPgetConss(), SCIPgetLhsLinear(), SCIPgetLhsVarbound(), SCIPgetNConss(), SCIPgetNVarsKnapsack(), SCIPgetNVarsLinear(), SCIPgetNVarsLogicor(), SCIPgetNVarsSetppc(), SCIPgetRhsLinear(), SCIPgetRhsVarbound(), SCIPgetTypeSetppc(), SCIPgetValsLinear(), SCIPgetVarsKnapsack(), SCIPgetVarsLinear(), SCIPgetVarsLogicor(), SCIPgetVarsSetppc(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPgetWeightsKnapsack(), and SCIPwarningMessage().
Referenced by solveClassification().
|
static |
Get next int from string s
s | string pointer (modified) |
Definition at line 664 of file classify.c.
Referenced by readLIBSVM().
Get next pair from string s
s | string pointer (modified) |
idx | index of value |
val | value |
Definition at line 684 of file classify.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, and TRUE.
Referenced by readLIBSVM().
|
static |
read classification instance in LIBSVM format and generate infeasible problem
Format: class type (+1, -1) points in sparse format: index:value
scip | SCIP data structure |
filename | name of file to read |
boundsonclassifier | Use unit bounds on classifier? |
nclass1 | pointer to store the number of points in class 1 |
nclass2 | pointer to store the number of points in class 2 |
Definition at line 717 of file classify.c.
References assert(), FALSE, getNextInt(), getNextPair(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_NOFILE, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreateConsBasicLinear(), SCIPcreateVar(), SCIPdebugMsg, SCIPerrorMessage, SCIPfeastol(), SCIPfreeBufferArray, SCIPinfinity(), SCIPprintSysError(), SCIPreallocBufferArray, SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), TRUE, and vars.
Referenced by solveClassification().
|
static |
find linear classifier that minimizes the number of misclassified points
filename | problem name |
settingsname | name of parameter file (or NULL) |
timelimit | time limit read from arguments |
memlimit | memory limit read from arguments |
dispfreq | display frequency |
Definition at line 905 of file classify.c.
References assert(), createAltLP(), DEFAULT_BOUNDSONCLASSIFIER, DEFAULT_MASTERGAPLIMIT, DEFAULT_MASTERSTALLNODES, DEFAULT_REOPTIMIZATION, DEFAULT_SOLVEMASTERAPPROX, FALSE, getProblemName(), BENDERS_Data::lp, BENDERS_Data::m, NULL, obj, readLIBSVM(), runBenders(), SCIP_Bool, SCIP_CALL, SCIP_CALL_PARAM, SCIP_ERROR, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_LPPAR_FASTMIP, SCIP_LPPAR_FROMSCRATCH, SCIP_LPPAR_PRESOLVING, SCIP_LPPAR_SCALING, SCIP_MAXSTRLEN, SCIP_OBJSEN_MINIMIZE, SCIP_OBJSENSE_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_VARTYPE_BINARY, SCIP_VERBLEVEL_NORMAL, SCIPaddBoolParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPaddVar(), SCIPcreate(), SCIPcreateProb(), SCIPcreateProbBasic(), SCIPcreateVar(), SCIPerrorMessage, SCIPfileExists(), SCIPfree(), SCIPgetMessagehdlr(), SCIPgetNOrigBinVars(), SCIPgetNOrigIntVars(), SCIPgetNOrigVars(), SCIPgetOrigVars(), SCIPincludeDefaultPlugins(), SCIPinfoMessage(), SCIPisInfinity(), SCIPisZero(), SCIPlpiAddCols(), SCIPlpiAddRows(), SCIPlpiCreate(), SCIPlpiFree(), SCIPlpiGetNCols(), SCIPlpiGetNRows(), SCIPlpiInfinity(), SCIPlpiSetIntpar(), SCIPlpiWriteLP(), SCIPprintVersion(), SCIPreadParams(), SCIPreleaseVar(), SCIPsetObjsense(), SCIPsnprintf(), SCIPvarGetIndex(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), SCIPwriteOrigProblem(), SCIPwriteParams(), TRUE, and var.
Referenced by main().
int main | ( | int | argc, |
char ** | argv ) |
main function
argc | number of shell parameters |
argv | array with shell parameters |
Definition at line 1151 of file classify.c.
References assert(), BMScheckEmptyMemory, NULL, readArguments(), SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, SCIPfileExists(), SCIPprintError(), and solveClassification().