Detailed Description
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) |
Macro Definition Documentation
◆ DEFAULT_SOLVEMASTERAPPROX
#define DEFAULT_SOLVEMASTERAPPROX FALSE |
Solve master problem approximately?
Definition at line 39 of file classify.c.
Referenced by solveClassification().
◆ DEFAULT_MASTERGAPLIMIT
#define DEFAULT_MASTERGAPLIMIT 0.1 |
gap bound for approximately solving the master problem
Definition at line 40 of file classify.c.
Referenced by solveClassification().
◆ DEFAULT_REOPTIMIZATION
#define DEFAULT_REOPTIMIZATION FALSE |
Use reoptimization to solve master problem?
Definition at line 41 of file classify.c.
Referenced by solveClassification().
◆ DEFAULT_MASTERSTALLNODES
#define DEFAULT_MASTERSTALLNODES 5000L |
stall nodes for the master problem
Definition at line 42 of file classify.c.
Referenced by solveClassification().
◆ DEFAULT_BOUNDSONCLASSIFIER
#define DEFAULT_BOUNDSONCLASSIFIER FALSE |
Use unit bounds on classifier?
Definition at line 43 of file classify.c.
Referenced by solveClassification().
◆ SCIP_CALL_PARAM
#define SCIP_CALL_PARAM | ( | x | ) |
Definition at line 55 of file classify.c.
Referenced by BENDERS_CUTORACLE(), checkAltLPInfeasible(), and solveClassification().
Function Documentation
◆ fixAltLPVariable()
|
static |
Fix variable ind to 0
- Parameters
-
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().
◆ fixAltLPVariables()
|
static |
fix variables in S to 0
- Parameters
-
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 NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPlpiChgBounds().
Referenced by BENDERS_CUTORACLE().
◆ unfixAltLPVariables()
|
static |
unfix variables in S
- Parameters
-
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 NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPlpiChgBounds(), and SCIPlpiInfinity().
Referenced by BENDERS_CUTORACLE().
◆ checkAltLPInfeasible()
|
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.
- Precondition
- It is assumed that all parameters for the alternative LP are set.
- Parameters
-
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 FALSE, NULL, 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().
◆ BENDERS_CUTORACLE()
|
static |
produce Benders cuts from the alternative polyhedron
input:
- masterscip: SCIP pointer of Benders master problem
- nmastervars: number of variables in master problem
- mastervars: variables in master problem
- mastersolution: solution of Benders master problem
- data: user data for oracle
- timelimit: time limit for subproblem
- ntotalcuts: total number of cuts output:
- ncuts: number of cuts added
- status: status
Definition at line 321 of file classify.c.
References BENDERS_STATUS_ADDEDCUT, BENDERS_STATUS_ERROR, BENDERS_STATUS_SUCCESS, BENDERS_STATUS_UNKNOWN, checkAltLPInfeasible(), FALSE, fixAltLPVariable(), fixAltLPVariables(), BENDERS_Data::lp, NULL, 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, and unfixAltLPVariables().
◆ createAltLPColumn()
|
static |
creates column in alternative polyhedron
- Parameters
-
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 NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPlpiAddCols(), SCIPlpiInfinity(), and SCIPvarGetIndex().
Referenced by createAltLP().
◆ createAltLP()
|
static |
create alternative polyhedron
- Parameters
-
origscip original SCIP instance lp alternative polyhedron
Definition at line 556 of file classify.c.
References 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().
◆ getNextInt()
|
static |
Get next int from string s
- Parameters
-
s string pointer (modified)
Definition at line 664 of file classify.c.
Referenced by readLIBSVM().
◆ getNextPair()
Get next pair from string s
- Parameters
-
s string pointer (modified) idx index of value val value
Definition at line 684 of file classify.c.
References FALSE, NULL, and TRUE.
Referenced by readLIBSVM().
◆ readLIBSVM()
|
static |
read classification instance in LIBSVM format and generate infeasible problem
Format: class type (+1, -1) points in sparse format: index:value
- Parameters
-
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 FALSE, getNextInt(), getNextPair(), NULL, 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(), and TRUE.
Referenced by solveClassification().
◆ solveClassification()
|
static |
find linear classifier that minimizes the number of misclassified points
- Parameters
-
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 createAltLP(), DEFAULT_BOUNDSONCLASSIFIER, DEFAULT_MASTERGAPLIMIT, DEFAULT_MASTERSTALLNODES, DEFAULT_REOPTIMIZATION, DEFAULT_SOLVEMASTERAPPROX, FALSE, getProblemName(), BENDERS_Data::lp, BENDERS_Data::m, NULL, 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(), and TRUE.
Referenced by main().
◆ main()
int main | ( | int | argc, |
char ** | argv | ||
) |
main function
- Parameters
-
argc number of shell parameters argv array with shell parameters
Definition at line 1151 of file classify.c.
References BMScheckEmptyMemory, NULL, readArguments(), SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, SCIPfileExists(), SCIPprintError(), and solveClassification().