Detailed Description

propagator for orbital fixing

Author: Marc Pfetsch

This propagator implements orbital fixing as introduced by

F. Margot: Exploiting orbits in symmetric ILP. Math. Program., 98(1-3):3–21, 2003.

The method obtains symmetries from the symmetry presolver and then computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the variables branched to 1. Then one can fix all variables in an orbit to 0 or 1 if one of the other variables in the orbit is fixed to 0 or 1, respectively. Different from Margot, the subgroup is obtained by filtering out generators that do not individually stabilize the variables branched to 1.

Definition in file prop_orbitalfixing.c.

#include "prop_orbitalfixing.h"
#include <scip/pub_tree.h>
#include <scip/pub_table.h>
#include "presol_symmetry.h"
#include "presol_symbreak.h"

Go to the source code of this file.

Macros
#define	PROP_NAME "orbitalfixing"

#define	PROP_DESC "propagator for orbital fixing"

#define	PROP_TIMING SCIP_PROPTIMING_BEFORELP

#define	PROP_PRIORITY -1000000

#define	PROP_FREQ 1

#define	PROP_DELAY FALSE

#define	PROP_PRESOL_PRIORITY -1000000

#define	PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */

#define	PROP_PRESOL_MAXROUNDS -1

#define	DEFAULT_SYMCOMPTIMING 2

#define	DEFAULT_PERFORMPRESOLVING FALSE

#define	DEFAULT_ENABLEDAFTERRESTARTS FALSE

#define	TABLE_NAME_ORBITALFIXING "orbitalfixing"

#define	TABLE_DESC_ORBITALFIXING "orbital fixing statistics"

#define	TABLE_POSITION_ORBITALFIXING 7001

#define	TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING

Functions
static	SCIP_DECL_TABLEOUTPUT (tableOutputOrbitalfixing)

static	SCIP_DECL_TABLEFREE (tableFreeOrbitalfixing)

static SCIP_RETCODE	getSymmetries (SCIP scip, SCIP_PROPDATA propdata)

static SCIP_RETCODE	performOrbitalFixing (SCIP scip, SCIP_VAR permvars, int npermvars, int orbits, int orbitbegins, int norbits, SCIP_Bool infeasible, int nfixedzero, int nfixedone)

static SCIP_RETCODE	computeBranchingVariables (SCIP scip, int nvars, SCIP_HASHMAP varmap, SCIP_Shortbool b1, SCIP_Bool success)

static SCIP_RETCODE	propagateOrbitalFixing (SCIP scip, SCIP_PROPDATA propdata, SCIP_Bool infeasible, int nprop)

static	SCIP_DECL_PROPFREE (propFreeOrbitalfixing)

static	SCIP_DECL_PROPINIT (propInitOrbitalfixing)

static	SCIP_DECL_PROPEXIT (propExitOrbitalfixing)

static	SCIP_DECL_PROPINITPRE (propInitpreOrbitalfixing)

static	SCIP_DECL_PROPPRESOL (propPresolOrbitalFixing)

static	SCIP_DECL_PROPEXEC (propExecOrbitalfixing)

static	SCIP_DECL_PROPRESPROP (propRespropOrbitalfixing)

SCIP_RETCODE	SCIPincludePropOrbitalfixing (SCIP *scip)

Macro Definition Documentation

◆ PROP_NAME

#define PROP_NAME "orbitalfixing"

Definition at line 44 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_DESC

#define PROP_DESC "propagator for orbital fixing"

Definition at line 45 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_BEFORELP

propagation timing mask

Definition at line 46 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_PRIORITY

#define PROP_PRIORITY -1000000

propagator priority

Definition at line 47 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_FREQ

#define PROP_FREQ 1

propagator frequency

Definition at line 48 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_DELAY

#define PROP_DELAY FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 49 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_PRESOL_PRIORITY

#define PROP_PRESOL_PRIORITY -1000000

priority of the presolving method (>= 0: before, < 0: after constraint handlers)

Definition at line 51 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_PRESOLTIMING

#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */

Definition at line 52 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_PRESOL_MAXROUNDS

#define PROP_PRESOL_MAXROUNDS -1

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 53 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ DEFAULT_SYMCOMPTIMING

#define DEFAULT_SYMCOMPTIMING 2

timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)

Definition at line 56 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ DEFAULT_PERFORMPRESOLVING

#define DEFAULT_PERFORMPRESOLVING FALSE

Run orbital fixing during presolving?

Definition at line 59 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ DEFAULT_ENABLEDAFTERRESTARTS

#define DEFAULT_ENABLEDAFTERRESTARTS FALSE

Run orbital fixing after a restart has occured?

Definition at line 60 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ TABLE_NAME_ORBITALFIXING

#define TABLE_NAME_ORBITALFIXING "orbitalfixing"

Definition at line 64 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ TABLE_DESC_ORBITALFIXING

#define TABLE_DESC_ORBITALFIXING "orbital fixing statistics"

Definition at line 65 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ TABLE_POSITION_ORBITALFIXING

#define TABLE_POSITION_ORBITALFIXING 7001

the position of the statistics table

Definition at line 66 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ TABLE_EARLIEST_ORBITALFIXING

#define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING

output of the statistics table is only printed from this stage onwards

Definition at line 67 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

Function Documentation

◆ SCIP_DECL_TABLEOUTPUT()

static SCIP_DECL_TABLEOUTPUT ( tableOutputOrbitalfixing )

static

output method of orbital fixing propagator statistics table to output file stream 'file'

Definition at line 108 of file prop_orbitalfixing.c.

References NULL, SCIP_DECL_TABLEFREE(), SCIP_OKAY, SCIP_VERBLEVEL_MINIMAL, SCIPtableGetData(), and SCIPverbMessage().

◆ SCIP_DECL_TABLEFREE()

static SCIP_DECL_TABLEFREE ( tableFreeOrbitalfixing )

static

destructor of statistics table to free user data (called when SCIP is exiting)

Definition at line 132 of file prop_orbitalfixing.c.

References getSymmetries(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPtableGetData().

Referenced by SCIP_DECL_TABLEOUTPUT().

◆ getSymmetries()

static SCIP_RETCODE getSymmetries	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata
	)

static

possibly get symmetries

Parameters

scip	SCIP pointer
propdata	propagator data

Definition at line 150 of file prop_orbitalfixing.c.

References FALSE, NULL, performOrbitalFixing(), SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPgetGeneratorsSymmetry(), SCIPgetNRuns(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, and TRUE.

Referenced by propagateOrbitalFixing(), SCIP_DECL_PROPINITPRE(), SCIP_DECL_PROPPRESOL(), and SCIP_DECL_TABLEFREE().

◆ performOrbitalFixing()

static SCIP_RETCODE performOrbitalFixing	(	SCIP *	scip,
		SCIP_VAR **	permvars,
		int	npermvars,
		int *	orbits,
		int *	orbitbegins,
		int	norbits,
		SCIP_Bool *	infeasible,
		int *	nfixedzero,
		int *	nfixedone
	)

static

perform orbital fixing

Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be fixed.

Parameters

scip	SCIP pointer
permvars	variables
npermvars	number of variables
orbits	array of non-trivial orbits
orbitbegins	array containing begin positions of new orbits in orbits array
norbits	number of orbits
infeasible	pointer to store whether problem is infeasible
nfixedzero	pointer to store number of variables fixed to 0
nfixedone	pointer to store number of variables fixed to 1

Definition at line 213 of file prop_orbitalfixing.c.

References computeBranchingVariables(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), and TRUE.

Referenced by getSymmetries(), and propagateOrbitalFixing().

◆ computeBranchingVariables()

static SCIP_RETCODE computeBranchingVariables	(	SCIP *	scip,
		int	nvars,
		SCIP_HASHMAP *	varmap,
		SCIP_Shortbool *	b1,
		SCIP_Bool *	success
	)

static

Get branching variables on the path to root

Parameters

scip	SCIP pointer
nvars	number of variables
varmap	map of variables to indices in vars array
b1	bitset marking the variables branched to 1
success	pointer to store whether branching variables were computed successfully

Definition at line 349 of file prop_orbitalfixing.c.

References FALSE, NULL, propagateOrbitalFixing(), SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPboundchgGetBoundchgtype(), SCIPboundchgGetVar(), SCIPdomchgGetBoundchg(), SCIPdomchgGetNBoundchgs(), SCIPgetCurrentNode(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPnodeGetDepth(), SCIPnodeGetDomchg(), SCIPnodeGetParent(), SCIPprintNodeRootPath(), SCIPvarGetLbLocal(), SCIPvarGetType(), and TRUE.

Referenced by performOrbitalFixing(), and propagateOrbitalFixing().

◆ propagateOrbitalFixing()

static SCIP_RETCODE propagateOrbitalFixing	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_Bool *	infeasible,
		int *	nprop
	)

static

propagate orbital fixing

Parameters

scip	SCIP pointer
propdata	propagator data
infeasible	pointer to store whether the node is detected to be infeasible
nprop	pointer to store the number of propagations

Definition at line 432 of file prop_orbitalfixing.c.

References computeBranchingVariables(), FALSE, getSymmetries(), NULL, performOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_DECL_PROPFREE(), SCIP_OKAY, SCIP_Real, SCIP_Shortbool, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPallocBufferArray, SCIPcomputeGroupOrbitsSymbreak(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetPermvarsObjSymmetry(), SCIPisEQ(), SCIPvarGetLbGlobal(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and TRUE.

Referenced by computeBranchingVariables(), SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPPRESOL().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeOrbitalfixing )

static

destructor of propagator to free user data (called when SCIP is exiting)

Definition at line 591 of file prop_orbitalfixing.c.

References NULL, SCIP_DECL_PROPINIT(), SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropGetName().

Referenced by propagateOrbitalFixing().

◆ SCIP_DECL_PROPINIT()

static SCIP_DECL_PROPINIT ( propInitOrbitalfixing )

static

initialization method of propagator (called after problem was transformed)

Definition at line 610 of file prop_orbitalfixing.c.

References FALSE, NULL, SCIP_CALL, SCIP_DECL_PROPEXIT(), SCIP_OKAY, SCIPdebugMsg, SCIPgetIntParam(), SCIPpropGetData(), SCIPpropGetName(), SYM_HANDLETYPE_ORBITALFIXING, and TRUE.

Referenced by SCIP_DECL_PROPFREE().

◆ SCIP_DECL_PROPEXIT()

static SCIP_DECL_PROPEXIT ( propExitOrbitalfixing )

static

deinitialization method of propagator (called before transformed problem is freed)

Definition at line 637 of file prop_orbitalfixing.c.

References NULL, SCIP_DECL_PROPINITPRE(), SCIP_OKAY, SCIPhashmapFree(), and SCIPpropGetData().

Referenced by SCIP_DECL_PROPINIT().

◆ SCIP_DECL_PROPINITPRE()

static SCIP_DECL_PROPINITPRE ( propInitpreOrbitalfixing )

static

presolving initialization method of propagator (called when presolving is about to begin)

Definition at line 669 of file prop_orbitalfixing.c.

References getSymmetries(), NULL, SCIP_CALL, SCIP_DECL_PROPPRESOL(), SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPgetStatus(), SCIPisTransformed(), and SCIPpropGetData().

Referenced by SCIP_DECL_PROPEXIT().

◆ SCIP_DECL_PROPPRESOL()

static SCIP_DECL_PROPPRESOL ( propPresolOrbitalFixing )

static

presolving method of propagator

Definition at line 704 of file prop_orbitalfixing.c.

References FALSE, getSymmetries(), NULL, propagateOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_PROPEXEC(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPdebugMsg, SCIPgetNRuns(), SCIPpropGetData(), and SCIPpropGetName().

Referenced by SCIP_DECL_PROPINITPRE().

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecOrbitalfixing )

static

execution method of propagator

Definition at line 761 of file prop_orbitalfixing.c.

References FALSE, NULL, propagateOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_PROPRESPROP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetNRuns(), SCIPgetStage(), SCIPinProbing(), SCIPnodeGetNumber(), SCIPpropGetData(), and SCIPpropGetName().

Referenced by SCIP_DECL_PROPPRESOL().

◆ SCIP_DECL_PROPRESPROP()

static SCIP_DECL_PROPRESPROP ( propRespropOrbitalfixing )

static

propagation conflict resolving method of propagator

Note that this is relatively difficult to obtain: One needs to include all bounds of variables to would lead to a different orbit in which the variables that was propagated lies. This includes all variables that are moved by the permutations which are involved in creating the orbit.

Definition at line 826 of file prop_orbitalfixing.c.

References NULL, SCIP_DIDNOTFIND, SCIP_OKAY, and SCIPincludePropOrbitalfixing().

Referenced by SCIP_DECL_PROPEXEC().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PROP_NAME

◆ PROP_DESC

◆ PROP_TIMING

◆ PROP_PRIORITY

◆ PROP_FREQ

◆ PROP_DELAY

◆ PROP_PRESOL_PRIORITY

◆ PROP_PRESOLTIMING

◆ PROP_PRESOL_MAXROUNDS

◆ DEFAULT_SYMCOMPTIMING

◆ DEFAULT_PERFORMPRESOLVING

◆ DEFAULT_ENABLEDAFTERRESTARTS

◆ TABLE_NAME_ORBITALFIXING

◆ TABLE_DESC_ORBITALFIXING

◆ TABLE_POSITION_ORBITALFIXING

◆ TABLE_EARLIEST_ORBITALFIXING

Function Documentation

◆ SCIP_DECL_TABLEOUTPUT()

◆ SCIP_DECL_TABLEFREE()

◆ getSymmetries()

◆ performOrbitalFixing()

◆ computeBranchingVariables()

◆ propagateOrbitalFixing()

◆ SCIP_DECL_PROPFREE()

◆ SCIP_DECL_PROPINIT()

◆ SCIP_DECL_PROPEXIT()

◆ SCIP_DECL_PROPINITPRE()

◆ SCIP_DECL_PROPPRESOL()

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPRESPROP()