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

Referenced by solveClassification(), and solveMinIISC().

◆ 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(), and solveMinIISC().

◆ DEFAULT_REOPTIMIZATION

#define DEFAULT_REOPTIMIZATION FALSE

Use reoptimization to solve master problem?

Definition at line 41 of file classify.c.

Referenced by solveClassification(), and solveMinIISC().

◆ DEFAULT_MASTERSTALLNODES

#define DEFAULT_MASTERSTALLNODES 5000L

stall nodes for the master problem

Definition at line 42 of file classify.c.

Referenced by solveClassification(), and solveMinIISC().

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

Value:

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

Function Documentation

◆ fixAltLPVariable()

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

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

Referenced by BENDERS_CUTORACLE(), BENDERS_CUTORACLE(), deleteAltLPConstraint(), extendToCover(), fixAltLPVariable(), fixAltLPVariable(), fixAltLPVariable(), and SCIP_DECL_CONSDISABLE().

◆ fixAltLPVariables()

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

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

Referenced by BENDERS_CUTORACLE(), BENDERS_CUTORACLE(), enforceCuts(), fixAltLPVariables(), fixAltLPVariables(), fixAltLPVariables(), SCIP_DECL_CONSCHECK(), and separateIISRounding().

◆ unfixAltLPVariables()

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

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

Referenced by BENDERS_CUTORACLE(), BENDERS_CUTORACLE(), enforceCuts(), SCIP_DECL_CONSCHECK(), separateIISRounding(), unfixAltLPVariables(), unfixAltLPVariables(), and unfixAltLPVariables().

◆ checkAltLPInfeasible()

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 occurred

Definition at line 192 of file classify.c.

References assert(), checkAltLPInfeasible(), 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(), BENDERS_CUTORACLE(), checkAltLPInfeasible(), checkAltLPInfeasible(), checkAltLPInfeasible(), extendToCover(), and SCIP_DECL_CONSCHECK().

◆ BENDERS_CUTORACLE()

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

References assert(), BENDERS_CUTORACLE, 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.

◆ createAltLPColumn()

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

References assert(), createAltLPColumn(), NULL, nvars, obj, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPlpiAddCols(), SCIPlpiInfinity(), SCIPvarGetIndex(), and vars.

Referenced by createAltLP(), createAltLP(), createAltLPColumn(), and createAltLPColumn().

◆ createAltLP()

SCIP_RETCODE createAltLP	(	SCIP *	origscip,
		SCIP_LPI *	lp )

static

create alternative polyhedron

Parameters

origscip	original SCIP instance
lp	alternative polyhedron

Definition at line 556 of file classify.c.

References assert(), c, createAltLP(), 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 createAltLP(), createAltLP(), solveClassification(), and solveMinIISC().

◆ getNextInt()

int getNextInt ( char ** s )

static

Get next int from string s

Parameters

s	string pointer (modified)

Definition at line 664 of file classify.c.

References getNextInt().

Referenced by getNextInt(), and readLIBSVM().

◆ getNextPair()

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

References assert(), FALSE, getNextPair(), NULL, SCIP_Bool, SCIP_Real, and TRUE.

Referenced by getNextPair(), and readLIBSVM().

◆ readLIBSVM()

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

References assert(), FALSE, getNextInt(), getNextPair(), NULL, readLIBSVM(), 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 readLIBSVM(), and solveClassification().

◆ solveClassification()

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 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(), solveClassification(), TRUE, and var.

Referenced by main(), and solveClassification().

◆ 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 assert(), BMScheckEmptyMemory, main(), NULL, readArguments(), SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, SCIPfileExists(), SCIPprintError(), and solveClassification().

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