iisfinder_greedy.c File Reference

Detailed Description

greedy deletion and addition filter heuristic to compute (I)ISs

Author

Marc Pfetsch

Mark Turner

Paul Meinhold

Definition in file iisfinder_greedy.c.

#include <assert.h>
#include "scip/iisfinder_greedy.h"

Go to the source code of this file.

Macros
#define	IISFINDER_NAME   "greedy"
#define	IISFINDER_DESC   "greedy deletion or addition constraint deletion"
#define	IISFINDER_PRIORITY   8000
#define	DEFAULT_TIMELIMPERITER   1e+20
#define	DEFAULT_NODELIMPERITER   -1L
#define	DEFAULT_ADDITIVE   TRUE
#define	DEFAULT_CONSERVATIVE   TRUE
#define	DEFAULT_DELAFTERADD   TRUE
#define	DEFAULT_DYNAMICREORDERING   TRUE
#define	DEFAULT_INITBATCHSIZE   16
#define	DEFAULT_INITRELBATCHSIZE   0.03125
#define	DEFAULT_MAXBATCHSIZE   INT_MAX
#define	DEFAULT_MAXRELBATCHSIZE   0.5
#define	DEFAULT_BATCHINGFACTOR   2.0
#define	DEFAULT_BATCHINGOFFSET   0.0
#define	DEFAULT_BATCHUPDATEINTERVAL   1

Functions
static SCIP_RETCODE	setLimits (SCIP *scip, SCIP_IIS *iis, SCIP_Real timelim, SCIP_Real timelimperiter, SCIP_Longint nodelim, SCIP_Longint nodelimperiter)
static SCIP_RETCODE	revertBndChgs (SCIP *scip, SCIP_VAR **vars, SCIP_Real *bounds, int *idxs, int ndelbounds, SCIP_Bool islb)
static SCIP_RETCODE	revertConssDeletions (SCIP *scip, SCIP_CONS **conss, int *idxs, int ndelconss, SCIP_Bool releaseonly)
static SCIP_RETCODE	updateBatchsize (SCIP *scip, int initbatchsize, int maxbatchsize, int iteration, SCIP_Bool resettoinit, SCIP_Real batchingfactor, SCIP_Real batchingoffset, int batchupdateinterval, int *batchsize)
static SCIP_RETCODE	deletionSubproblem (SCIP_IIS *iis, SCIP_CONS **conss, SCIP_VAR **vars, int *idxs, int ndels, SCIP_Real timelim, SCIP_Real timelimperiter, SCIP_Longint nodelim, SCIP_Longint nodelimperiter, SCIP_Bool conservative, SCIP_Bool delbounds, SCIP_Bool islb, SCIP_Bool *deleted, SCIP_Bool *stop, SCIP_Bool *alldeletionssolved)
static SCIP_RETCODE	additionSubproblem (SCIP_IIS *iis, SCIP_Real timelim, SCIP_Real timelimperiter, SCIP_Longint nodelim, SCIP_Longint nodelimperiter, SCIP_Bool *feasible, SCIP_Bool *stop)
static SCIP_RETCODE	deletionFilterBatch (SCIP_IIS *iis, SCIP_Real timelim, SCIP_Longint nodelim, SCIP_Bool removebounds, SCIP_Bool silent, SCIP_Real timelimperiter, SCIP_Longint nodelimperiter, SCIP_Bool conservative, int initbatchsize, int maxbatchsize, SCIP_Real batchingfactor, SCIP_Real batchingoffset, int batchupdateinterval, SCIP_Bool *alldeletionssolved)
static SCIP_RETCODE	additionFilterBatch (SCIP_IIS *iis, SCIP_Real timelim, SCIP_Longint nodelim, SCIP_Bool silent, SCIP_Real timelimperiter, SCIP_Longint nodelimperiter, SCIP_Bool dynamicreordering, int initbatchsize, int maxbatchsize, SCIP_Real batchingfactor, SCIP_Real batchingoffset, int batchupdateinterval)
static SCIP_RETCODE	execIISfinderGreedy (SCIP_IIS *iis, SCIP_IISFINDERDATA *iisfinderdata, SCIP_RESULT *result)
static	SCIP_DECL_IISFINDERCOPY (iisfinderCopyGreedy)
static	SCIP_DECL_IISFINDERFREE (iisfinderFreeGreedy)
static	SCIP_DECL_IISFINDEREXEC (iisfinderExecGreedy)
SCIP_RETCODE	SCIPincludeIISfinderGreedy (SCIP *scip)
SCIP_RETCODE	SCIPiisGreedyMakeIrreducible (SCIP_IIS *iis)

Macro Definition Documentation

IISFINDER_NAME

#define IISFINDER_NAME   "greedy"

Definition at line 36 of file iisfinder_greedy.c.

IISFINDER_DESC

#define IISFINDER_DESC   "greedy deletion or addition constraint deletion"

Definition at line 37 of file iisfinder_greedy.c.

IISFINDER_PRIORITY

#define IISFINDER_PRIORITY   8000

Definition at line 38 of file iisfinder_greedy.c.

DEFAULT_TIMELIMPERITER

#define DEFAULT_TIMELIMPERITER   1e+20

time limit of optimization process for each individual subproblem

Definition at line 40 of file iisfinder_greedy.c.

DEFAULT_NODELIMPERITER

#define DEFAULT_NODELIMPERITER   -1L

node limit of optimization process for each individual subproblem

Definition at line 41 of file iisfinder_greedy.c.

DEFAULT_ADDITIVE

#define DEFAULT_ADDITIVE   TRUE

should an additive constraint approach be used instead of deletion

Definition at line 43 of file iisfinder_greedy.c.

DEFAULT_CONSERVATIVE

#define DEFAULT_CONSERVATIVE   TRUE

should an unsolved problem (by e.g. user interrupt, node limit, time limit) be considered feasible when deleting constraints

Definition at line 44 of file iisfinder_greedy.c.

DEFAULT_DELAFTERADD

#define DEFAULT_DELAFTERADD   TRUE

should the deletion routine be performed after the addition routine (in the case of additive)

Definition at line 45 of file iisfinder_greedy.c.

DEFAULT_DYNAMICREORDERING

#define DEFAULT_DYNAMICREORDERING   TRUE

should satisfied constraints outside the batch of an intermediate solve be added during the additive method

Definition at line 46 of file iisfinder_greedy.c.

DEFAULT_INITBATCHSIZE

#define DEFAULT_INITBATCHSIZE   16

the initial batchsize for the first iteration, ignored if initrelbatchsize is positive

Definition at line 48 of file iisfinder_greedy.c.

DEFAULT_INITRELBATCHSIZE

#define DEFAULT_INITRELBATCHSIZE   0.03125

the initial batchsize relative to the original problem for the first iteration (0.0: use initbatchsize)

Definition at line 49 of file iisfinder_greedy.c.

DEFAULT_MAXBATCHSIZE

#define DEFAULT_MAXBATCHSIZE   INT_MAX

the maximum batchsize per iteration

Definition at line 50 of file iisfinder_greedy.c.

DEFAULT_MAXRELBATCHSIZE

#define DEFAULT_MAXRELBATCHSIZE   0.5

the maximum batchsize relative to the original problem per iteration

Definition at line 51 of file iisfinder_greedy.c.

DEFAULT_BATCHINGFACTOR

#define DEFAULT_BATCHINGFACTOR   2.0

the factor with which the batchsize is multiplied in every update

Definition at line 52 of file iisfinder_greedy.c.

DEFAULT_BATCHINGOFFSET

#define DEFAULT_BATCHINGOFFSET   0.0

the offset which is added to the multiplied batchsize in every update

Definition at line 53 of file iisfinder_greedy.c.

DEFAULT_BATCHUPDATEINTERVAL

#define DEFAULT_BATCHUPDATEINTERVAL   1

the number of iterations to run with a constant batchsize before updating (1: always update)

Definition at line 54 of file iisfinder_greedy.c.

Function Documentation

setLimits()

static SCIP_RETCODE setLimits ( SCIP *  scip, SCIP_IIS *  iis, SCIP_Real  timelim, SCIP_Real  timelimperiter, SCIP_Longint  nodelim, SCIP_Longint  nodelimperiter  )

static

Parameters

scip	SCIP instance to analyze
iis	IIS data structure containing subscip
timelim	total time limit allowed of the whole call
timelimperiter	time limit per individual solve call
nodelim	node limit allowed for the whole call
nodelimperiter	maximum number of nodes per individual solve call

Definition at line 87 of file iisfinder_greedy.c.

References MAX, MIN, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPiisGetNNodes(), SCIPiisGetTime(), SCIPsetLongintParam(), and SCIPsetRealParam().

Referenced by additionSubproblem(), and deletionSubproblem().

revertBndChgs()

static SCIP_RETCODE revertBndChgs ( SCIP *  scip, SCIP_VAR **  vars, SCIP_Real *  bounds, int *  idxs, int  ndelbounds, SCIP_Bool  islb  )

static

Parameters

scip	SCIP instance to analyze
vars	the array of variables whose bounds are changed
bounds	the array of original bounds for the variables
idxs	the indices of the vars (in the vars array) that have been deleted
ndelbounds	the number of bounds that will be deleted
islb	are the bounds that are being deleted LBs?

Definition at line 131 of file iisfinder_greedy.c.

References SCIP_CALL, SCIP_OKAY, SCIPchgVarLb(), SCIPchgVarUb(), and SCIPisInfinity().

Referenced by deletionSubproblem().

revertConssDeletions()

static SCIP_RETCODE revertConssDeletions ( SCIP *  scip, SCIP_CONS **  conss, int *  idxs, int  ndelconss, SCIP_Bool  releaseonly  )

static

Parameters

scip	SCIP instance to analyze
conss	the array of constraints where some have been deleted
idxs	the indices of the cons (in the conss array) that have been deleted
ndelconss	the number of constraints that have been deleted
releaseonly	Should the constraints just be released instead of added back

Definition at line 161 of file iisfinder_greedy.c.

References SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPconsGetNUses(), and SCIPreleaseCons().

Referenced by deletionSubproblem().

updateBatchsize()

static SCIP_RETCODE updateBatchsize ( SCIP *  scip, int  initbatchsize, int  maxbatchsize, int  iteration, SCIP_Bool  resettoinit, SCIP_Real  batchingfactor, SCIP_Real  batchingoffset, int  batchupdateinterval, int *  batchsize  )

static

Parameters

scip	SCIP data structure
initbatchsize	the initial batchsize
maxbatchsize	the maximum batchsize per iteration
iteration	the current iteration
resettoinit	should the batchsize be reset to the initial batchsize?
batchingfactor	the factor with which the batchsize is multiplied in every update
batchingoffset	the offset which is added to the multiplied batchsize in every update
batchupdateinterval	the number of iterations to run with a constant batchsize before updating (1: always update)
batchsize	the batchsize to be updated

Definition at line 192 of file iisfinder_greedy.c.

References MAX, MIN, SCIP_OKAY, and SCIPdebugMsg.

Referenced by additionFilterBatch(), and deletionFilterBatch().

deletionSubproblem()

static SCIP_RETCODE deletionSubproblem ( SCIP_IIS *  iis, SCIP_CONS **  conss, SCIP_VAR **  vars, int *  idxs, int  ndels, SCIP_Real  timelim, SCIP_Real  timelimperiter, SCIP_Longint  nodelim, SCIP_Longint  nodelimperiter, SCIP_Bool  conservative, SCIP_Bool  delbounds, SCIP_Bool  islb, SCIP_Bool *  deleted, SCIP_Bool *  stop, SCIP_Bool *  alldeletionssolved  )

static

solve subproblem for deletionFilter

Parameters

iis	IIS data structure containing subscip
conss	The array of constraints (may be a superset of the current constraints)
vars	the array of vars
idxs	the indices of the constraints / vars that will be deleted / bounds removed
ndels	the number of bounds that will be deleted
timelim	The global time limit on the IIS finder call
timelimperiter	time limit per individual solve call
nodelim	The global node limit on the IIS finder call
nodelimperiter	maximum number of nodes per individual solve call
conservative	whether we treat a subproblem to be feasible, if it reaches some status that could result in infeasible, e.g. node limit
delbounds	whether bounds should be deleted instead of constraints
islb	are the bounds that are being deleted LBs?
deleted	have the deleted bounds or constraints stayed deleted
stop	pointer to store whether we have to stop
alldeletionssolved	pointer to store whether all the subscips solved

Definition at line 219 of file iisfinder_greedy.c.

References FALSE, NULL, revertBndChgs(), revertConssDeletions(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_DUALLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_PRIMALLIMIT, SCIP_STATUS_RESTARTLIMIT, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TERMINATE, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIPallocBlockMemoryArray, SCIPcaptureCons(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPconsIsInProb(), SCIPdebugMsg, SCIPdelCons(), SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPfreeTransform(), SCIPgetNTotalNodes(), SCIPgetStatus(), SCIPiisAddNNodes(), SCIPiisGetSubscip(), SCIPiisSetSubscipInfeasible(), SCIPinfinity(), SCIPisInfinity(), SCIPsolve(), SCIPvarGetLbOriginal(), SCIPvarGetUbOriginal(), setLimits(), and TRUE.

Referenced by deletionFilterBatch().

additionSubproblem()

static SCIP_RETCODE additionSubproblem ( SCIP_IIS *  iis, SCIP_Real  timelim, SCIP_Real  timelimperiter, SCIP_Longint  nodelim, SCIP_Longint  nodelimperiter, SCIP_Bool *  feasible, SCIP_Bool *  stop  )

static

solve subproblem for additionFilter

Parameters

iis	IIS data structure containing subscip
timelim	The global time limit on the IIS finder call
timelimperiter	time limit per individual solve call
nodelim	The global node limit on the IIS finder call
nodelimperiter	maximum number of nodes per individual solve call
feasible	pointer to store whether the problem is feasible
stop	pointer to store whether we have to stop

Definition at line 408 of file iisfinder_greedy.c.

References FALSE, NULL, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_DUALLIMIT, SCIP_STATUS_GAPLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_PRIMALLIMIT, SCIP_STATUS_RESTARTLIMIT, SCIP_STATUS_SOLLIMIT, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TERMINATE, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_TOTALNODELIMIT, SCIP_STATUS_UNBOUNDED, SCIP_STATUS_UNKNOWN, SCIP_STATUS_USERINTERRUPT, SCIPdebugMsg, SCIPerrorMessage, SCIPgetNTotalNodes(), SCIPgetStatus(), SCIPiisAddNNodes(), SCIPiisGetSubscip(), SCIPsolve(), setLimits(), and TRUE.

Referenced by additionFilterBatch().

deletionFilterBatch()

static SCIP_RETCODE deletionFilterBatch ( SCIP_IIS *  iis, SCIP_Real  timelim, SCIP_Longint  nodelim, SCIP_Bool  removebounds, SCIP_Bool  silent, SCIP_Real  timelimperiter, SCIP_Longint  nodelimperiter, SCIP_Bool  conservative, int  initbatchsize, int  maxbatchsize, SCIP_Real  batchingfactor, SCIP_Real  batchingoffset, int  batchupdateinterval, SCIP_Bool *  alldeletionssolved  )

static

Deletion filter to greedily remove constraints to obtain an (I)IS

Parameters

iis	IIS data structure containing subscip
timelim	The global time limit on the IIS finder call
nodelim	The global node limit on the IIS finder call
removebounds	Whether the algorithm should remove bounds as well as constraints
silent	should the run be performed silently without printing progress information
timelimperiter	time limit per individual solve call
nodelimperiter	maximum number of nodes per individual solve call
conservative	should a node or time limit solve be counted as feasible when deleting constraints
initbatchsize	the initial batchsize for the first iteration
maxbatchsize	the maximum batchsize per iteration
batchingfactor	the factor with which the batchsize is multiplied in every update
batchingoffset	the offset which is added to the multiplied batchsize in every update
batchupdateinterval	the number of iterations to run with a constant batchsize before updating (1: always update)
alldeletionssolved	pointer to store whether all the subscips solved

Definition at line 487 of file iisfinder_greedy.c.

References deletionSubproblem(), FALSE, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_PROBLEM, SCIP_VARTYPE_BINARY, SCIPallocBlockMemoryArray, SCIPconsGetNUses(), SCIPduplicateBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPfreeTransform(), SCIPgetNOrigConss(), SCIPgetNOrigVars(), SCIPgetOrigConss(), SCIPgetOrigVars(), SCIPgetStage(), SCIPiisfinderInfoMessage(), SCIPiisGetNNodes(), SCIPiisGetRandnumgen(), SCIPiisGetSubscip(), SCIPiisGetTime(), SCIPiisIsSubscipInfeasible(), SCIPisInfinity(), SCIPrandomPermuteIntArray(), SCIPvarGetLbOriginal(), SCIPvarGetType(), SCIPvarGetUbOriginal(), TRUE, and updateBatchsize().

Referenced by execIISfinderGreedy(), and SCIPiisGreedyMakeIrreducible().

additionFilterBatch()

static SCIP_RETCODE additionFilterBatch ( SCIP_IIS *  iis, SCIP_Real  timelim, SCIP_Longint  nodelim, SCIP_Bool  silent, SCIP_Real  timelimperiter, SCIP_Longint  nodelimperiter, SCIP_Bool  dynamicreordering, int  initbatchsize, int  maxbatchsize, SCIP_Real  batchingfactor, SCIP_Real  batchingoffset, int  batchupdateinterval  )

static

Addition filter to greedily add constraints to obtain an (I)IS

Parameters

iis	IIS data structure containing subscip
timelim	The global time limit on the IIS finder call
nodelim	The global node limit on the IIS finder call
silent	should the run be performed silently without printing progress information
timelimperiter	time limit per individual solve call
nodelimperiter	maximum number of nodes per individual solve call
dynamicreordering	should satisfied constraints outside the batch of an intermediate solve be added during the additive method
initbatchsize	the initial batchsize for the first iteration
maxbatchsize	the maximum batchsize per iteration
batchingfactor	the factor with which the batchsize is multiplied in every update
batchingoffset	the offset which is added to the multiplied batchsize in every update
batchupdateinterval	the number of iterations to run with a constant batchsize before updating (1: always update)

Definition at line 677 of file iisfinder_greedy.c.

References additionSubproblem(), FALSE, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_OKAY, SCIP_STAGE_PROBLEM, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPcaptureCons(), SCIPcheckCons(), SCIPconsGetHdlr(), SCIPconsGetNUses(), SCIPconshdlrGetName(), SCIPconsIsInProb(), SCIPcreateSolCopyOrig(), SCIPdebugMsg, SCIPdelCons(), SCIPduplicateBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPfreeSol(), SCIPfreeTransform(), SCIPgetBestSol(), SCIPgetNOrigConss(), SCIPgetOrigConss(), SCIPgetStage(), SCIPiisfinderInfoMessage(), SCIPiisGetNNodes(), SCIPiisGetRandnumgen(), SCIPiisGetSubscip(), SCIPiisGetTime(), SCIPiisIsSubscipInfeasible(), SCIPiisSetSubscipInfeasible(), SCIPrandomPermuteIntArray(), SCIPreleaseCons(), SCIPunlinkSol(), TRUE, and updateBatchsize().

Referenced by execIISfinderGreedy().

execIISfinderGreedy()

static SCIP_RETCODE execIISfinderGreedy ( SCIP_IIS *  iis, SCIP_IISFINDERDATA *  iisfinderdata, SCIP_RESULT *  result  )

static

perform a greedy addition or deletion algorithm to obtain an infeasible subsystem (IS).

This is the generation method for the greedy IIS finder rule. Depending on the parameter choices, constraints are either greedily added from an empty problem, or deleted from a complete problem. In the case of constraints being added, this is done until the problem becomes infeasible, after which one can then begin deleting constraints. In the case of deleting constraints, this is done until no more constraints (or batches of constraints) can be deleted without making the problem feasible.

Parameters

iis	IIS data structure
iisfinderdata	IIS finder data
result	pointer to store the result of the IIS finder run. SCIP_DIDNOTFIND if the algorithm failed, otherwise SCIP_SUCCESS.

Definition at line 882 of file iisfinder_greedy.c.

References additionFilterBatch(), deletionFilterBatch(), FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIPdebugMsg, SCIPgetBoolParam(), SCIPgetLongintParam(), SCIPgetNOrigConss(), SCIPgetNOrigVars(), SCIPgetRealParam(), SCIPiisGetNNodes(), SCIPiisGetSubscip(), SCIPiisGetTime(), SCIPiisSetSubscipIrreducible(), and TRUE.

Referenced by SCIP_DECL_IISFINDEREXEC().

SCIP_DECL_IISFINDERCOPY()

static SCIP_DECL_IISFINDERCOPY ( iisfinderCopyGreedy  )

static

copy method for IIS finder plugin (called when SCIP copies plugins)

Definition at line 976 of file iisfinder_greedy.c.

References IISFINDER_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPiisfinderGetName(), and SCIPincludeIISfinderGreedy().

SCIP_DECL_IISFINDERFREE()

static SCIP_DECL_IISFINDERFREE ( iisfinderFreeGreedy  )

static

destructor of IIS finder to free user data (called when SCIP is exiting) ! [SnippetIISfinderFreeGreedy]

Definition at line 991 of file iisfinder_greedy.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPiisfinderGetData(), and SCIPiisfinderSetData().

SCIP_DECL_IISFINDEREXEC()

static SCIP_DECL_IISFINDEREXEC ( iisfinderExecGreedy  )

static

! [SnippetIISfinderFreeGreedy] IIS finder generation method of IIS

Definition at line 1007 of file iisfinder_greedy.c.

References execIISfinderGreedy(), NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, and SCIPiisfinderGetData().