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 )

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

lp	alternative LP
ind	variable 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

masterscip	SCIP pointer
nmastervars	number of variables in master
S	indices to fix
lp	alternative 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

masterscip	SCIP pointer
nmastervars	number of variables in master
S	indices to fix
lp	alternative 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

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 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

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 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()

static SCIP_RETCODE createAltLP	(	SCIP *	origscip,
		SCIP_LPI *	lp
	)

static

create alternative polyhedron

Parameters

origscip	original SCIP instance
lp	alternative polyhedron

Definition at line 547 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 int getNextInt ( char ** s )

static

Get next int from string s

Parameters

s	string 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

s	string pointer (modified)
idx	index of value
val	value

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

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 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

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 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

argc	number of shell parameters
argv	array 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().

SCIP

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ DEFAULT_SOLVEMASTERAPPROX

◆ DEFAULT_MASTERGAPLIMIT

◆ DEFAULT_REOPTIMIZATION

◆ DEFAULT_MASTERSTALLNODES

◆ DEFAULT_BOUNDSONCLASSIFIER

◆ SCIP_CALL_PARAM

Function Documentation

◆ fixAltLPVariable()

◆ fixAltLPVariables()

◆ unfixAltLPVariables()

◆ checkAltLPInfeasible()

◆ BENDERS_CUTORACLE()

◆ createAltLPColumn()

◆ createAltLP()

◆ getNextInt()

◆ getNextPair()

◆ readLIBSVM()

◆ solveClassification()

◆ main()