Detailed Description

find a minimum IIS cover

Author: Marc Pfetsch

Definition in file miniisc.c.

#include <string.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 TRUE

#define	DEFAULT_MASTERSTALLNODES 5000L

#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 SCIP_RETCODE	solveMinIISC (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 38 of file miniisc.c.

◆ DEFAULT_MASTERGAPLIMIT

#define DEFAULT_MASTERGAPLIMIT 0.1

gap bound for approximately solving the master problem

Definition at line 39 of file miniisc.c.

◆ DEFAULT_REOPTIMIZATION

#define DEFAULT_REOPTIMIZATION TRUE

Use reoptimization to solve master problem?

Definition at line 40 of file miniisc.c.

◆ DEFAULT_MASTERSTALLNODES

#define DEFAULT_MASTERSTALLNODES 5000L

stall nodes for the master problem

Definition at line 41 of file miniisc.c.

◆ 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 52 of file miniisc.c.

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 67 of file miniisc.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 84 of file miniisc.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 132 of file miniisc.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 189 of file miniisc.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 318 of file miniisc.c.

References BENDERS_STATUS_ADDEDCUT, BENDERS_STATUS_ERROR, BENDERS_STATUS_SUCCESS, BENDERS_STATUS_UNKNOWN, checkAltLPInfeasible(), FALSE, fixAltLPVariable(), fixAltLPVariables(), 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 490 of file miniisc.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 553 of file miniisc.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 solveMinIISC().

◆ solveMinIISC()

static SCIP_RETCODE solveMinIISC	(	const char *	filename,
		const char *	settingsname,
		SCIP_Real	timelimit,
		SCIP_Real	memlimit,
		int	dispfreq
	)

static

solve minimum IIS cover problem

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 662 of file miniisc.c.

References createAltLP(), DEFAULT_MASTERGAPLIMIT, DEFAULT_MASTERSTALLNODES, DEFAULT_REOPTIMIZATION, DEFAULT_SOLVEMASTERAPPROX, FALSE, getProblemName(), BENDERS_Data::lp, BENDERS_Data::m, NULL, 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(), SCIPcreateVar(), SCIPerrorMessage, SCIPfileExists(), SCIPfree(), SCIPgetMessagehdlr(), SCIPgetNOrigBinVars(), SCIPgetNOrigIntVars(), SCIPgetNOrigVars(), SCIPgetOrigVars(), SCIPincludeDefaultPlugins(), SCIPinfoMessage(), SCIPisInfinity(), SCIPisZero(), SCIPlpiAddCols(), SCIPlpiAddRows(), SCIPlpiCreate(), SCIPlpiFree(), SCIPlpiGetNCols(), SCIPlpiGetNRows(), SCIPlpiInfinity(), SCIPlpiSetIntpar(), SCIPlpiWriteLP(), SCIPprintVersion(), SCIPreadParams(), SCIPreadProb(), SCIPreleaseVar(), SCIPsetObjsense(), SCIPsnprintf(), SCIPvarGetIndex(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), 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 884 of file miniisc.c.

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

SCIP

Detailed Description

Data Structures

Macros

Functions

Macro Definition Documentation

◆ DEFAULT_SOLVEMASTERAPPROX

◆ DEFAULT_MASTERGAPLIMIT

◆ DEFAULT_REOPTIMIZATION

◆ DEFAULT_MASTERSTALLNODES

◆ SCIP_CALL_PARAM

Function Documentation

◆ fixAltLPVariable()

◆ fixAltLPVariables()

◆ unfixAltLPVariables()

◆ checkAltLPInfeasible()

◆ BENDERS_CUTORACLE()

◆ createAltLPColumn()

◆ createAltLP()

◆ solveMinIISC()

◆ main()