Scippy

SCIP

Solving Constraint Integer Programs

classify.c File Reference

Detailed Description

determine linear classifier using a Benders approach

Author
Marc Pfetsch

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 30 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 31 of file classify.c.

Referenced by solveClassification().

◆ DEFAULT_REOPTIMIZATION

#define DEFAULT_REOPTIMIZATION   FALSE

Use reoptimization to solve master problem?

Definition at line 32 of file classify.c.

Referenced by solveClassification().

◆ DEFAULT_MASTERSTALLNODES

#define DEFAULT_MASTERSTALLNODES   5000L

stall nodes for the master problem

Definition at line 33 of file classify.c.

Referenced by solveClassification().

◆ DEFAULT_BOUNDSONCLASSIFIER

#define DEFAULT_BOUNDSONCLASSIFIER   FALSE

Use unit bounds on classifier?

Definition at line 34 of file classify.c.

Referenced by solveClassification().

◆ SCIP_CALL_PARAM

#define SCIP_CALL_PARAM (   x)
Value:
/*lint -e527 */ do \
{ \
SCIP_RETCODE _restat_; \
if ( (_restat_ = (x)) != SCIP_OKAY && (_restat_ != SCIP_PARAMETERUNKNOWN) ) \
{ \
SCIPerrorMessage("[%s:%d] Error <%d> in function call\n", __FILE__, __LINE__, _restat_); \
SCIPABORT(); \
return _restat_; \
} \
} \
while ( FALSE )
#define FALSE
Definition: def.h:87
SCIP_VAR ** x
Definition: circlepacking.c:54

Definition at line 46 of file classify.c.

Referenced by BENDERS_CUTORACLE(), checkAltLPInfeasible(), and solveClassification().

Function Documentation

◆ fixAltLPVariable()

static SCIP_RETCODE fixAltLPVariable ( SCIP_LPI lp,
int  ind 
)
static

Fix variable ind to 0

Parameters
lpalternative LP
indvariable that should be fixed to 0

Definition at line 61 of file classify.c.

References SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPlpiChgBounds().

Referenced by BENDERS_CUTORACLE().

◆ fixAltLPVariables()

static SCIP_RETCODE fixAltLPVariables ( SCIP masterscip,
int  nmastervars,
SCIP_Bool S,
SCIP_LPI lp 
)
static

fix variables in S to 0

Parameters
masterscipSCIP pointer
nmastervarsnumber of variables in master
Sindices to fix
lpalternative LP

Definition at line 78 of file classify.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPlpiChgBounds().

Referenced by BENDERS_CUTORACLE().

◆ unfixAltLPVariables()

static SCIP_RETCODE unfixAltLPVariables ( SCIP masterscip,
int  nmastervars,
SCIP_Bool S,
SCIP_LPI lp 
)
static

unfix variables in S

Parameters
masterscipSCIP pointer
nmastervarsnumber of variables in master
Sindices to fix
lpalternative LP

Definition at line 126 of file classify.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPlpiChgBounds(), and SCIPlpiInfinity().

Referenced by BENDERS_CUTORACLE().

◆ checkAltLPInfeasible()

static SCIP_RETCODE checkAltLPInfeasible ( SCIP masterscip,
SCIP_LPI lp,
SCIP_Bool  primal,
SCIP_Bool infeasible,
SCIP_Bool error 
)
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
masterscipSCIP pointer
lpLP
primalwhether we are using the primal or dual simplex
infeasibleoutput: whether the LP is infeasible
erroroutput: whether an error occured

Definition at line 183 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 BENDERS_CUTORACLE ( 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 312 of file classify.c.

References BENDERS_STATUS_ADDEDCUT, BENDERS_STATUS_ERROR, BENDERS_STATUS_SUCESS, 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 SCIP_RETCODE createAltLPColumn ( SCIP origscip,
SCIP_LPI lp,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real vals,
SCIP_Real  rhscoef,
SCIP_Real  sign 
)
static

creates column in alternative polyhedron

Parameters
origscipSCIP pointer
lpalternative LP
nvarsnumber of variables in column
varsvariables for column
valsvalues for column
rhscoefcoefficient for first row
signsign (+1,-1) for column

Definition at line 484 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()

◆ getNextInt()

static int getNextInt ( char **  s)
static

Get next int from string s

Parameters
sstring pointer (modified)

Definition at line 655 of file classify.c.

Referenced by readLIBSVM().

◆ getNextPair()

static SCIP_Bool getNextPair ( char **  s,
int *  idx,
SCIP_Real val 
)
static

Get next pair from string s

Parameters
sstring pointer (modified)
idxindex of value
valvalue

Definition at line 675 of file classify.c.

References FALSE, NULL, and TRUE.

Referenced by readLIBSVM().

◆ readLIBSVM()

static SCIP_RETCODE readLIBSVM ( SCIP scip,
const char *  filename,
SCIP_Bool  boundsonclassifier,
int *  nclass1,
int *  nclass2 
)
static

read classification instance in LIBSVM format and generate infeasible problem

Format: class type (+1, -1) points in sparse format: index:value

Parameters
scipSCIP data structure
filenamename of file to read
boundsonclassifierUse unit bounds on classifier?
nclass1pointer to store the number of points in class 1
nclass2pointer to store the number of points in class 2

Definition at line 708 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 SCIP_RETCODE solveClassification ( const char *  filename,
const char *  settingsname,
SCIP_Real  timelimit,
SCIP_Real  memlimit,
int  dispfreq 
)
static

find linear classifier that minimizes the number of misclassified points

Parameters
filenameproblem name
settingsnamename of parameter file (or NULL)
timelimittime limit read from arguments
memlimitmemory limit read from arguments
dispfreqdisplay frequency

Definition at line 896 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
argcnumber of shell parameters
argvarray with shell parameters

Definition at line 1142 of file classify.c.

References BMScheckEmptyMemory, NULL, readArguments(), SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, SCIPfileExists(), SCIPprintError(), and solveClassification().