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

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

◆ TABLE_NAME_ORBITALFIXING

#define TABLE_NAME_ORBITALFIXING "orbitalfixing"

Definition at line 52 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ TABLE_DESC_ORBITALFIXING

#define TABLE_DESC_ORBITALFIXING "orbital fixing statistics"

Definition at line 53 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 54 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 55 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 91 of file prop_orbitalfixing.c.

References 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 115 of file prop_orbitalfixing.c.

References SCIP_OKAY, SCIPfreeBlockMemory, and SCIPtableGetData().

◆ 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 139 of file prop_orbitalfixing.c.

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

Referenced by 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 275 of file prop_orbitalfixing.c.

References FALSE, 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 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 359 of file prop_orbitalfixing.c.

References computeBranchingVariables(), FALSE, performOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_Shortbool, SCIPallocBufferArray, SCIPcomputeGroupOrbitsSymbreak(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetPermvarsObjSymmetry(), SCIPisEQ(), SCIPvarGetType(), and TRUE.

Referenced by SCIP_DECL_PROPEXEC().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeOrbitalfixing )

static

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

Definition at line 489 of file prop_orbitalfixing.c.

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

◆ SCIP_DECL_PROPINIT()

static SCIP_DECL_PROPINIT ( propInitOrbitalfixing )

static

initialization method of propagator (called after problem was transformed)

Definition at line 508 of file prop_orbitalfixing.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetIntParam(), SCIPpropGetData(), SCIPpropGetName(), SCIPregisterSymmetry(), SYM_HANDLETYPE_ORBITALFIXING, SYM_SPEC_BINARY, SYM_SPEC_INTEGER, and TRUE.

◆ SCIP_DECL_PROPEXIT()

static SCIP_DECL_PROPEXIT ( propExitOrbitalfixing )

static

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

Definition at line 541 of file prop_orbitalfixing.c.

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

◆ SCIP_DECL_PROPINITSOL()

static SCIP_DECL_PROPINITSOL ( propInitsolOrbitalfixing )

static

solving process initialization method of propagator (called when branch and bound process is about to begin)

Definition at line 570 of file prop_orbitalfixing.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPblkmem(), SCIPgetGeneratorsSymmetry(), SCIPgetStatus(), SCIPhashmapCreate(), SCIPhashmapInsert(), SCIPisStopped(), SCIPisTransformed(), and SCIPpropGetData().

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecOrbitalfixing )

static

execution method of propagator

Definition at line 626 of file prop_orbitalfixing.c.

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

◆ 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 692 of file prop_orbitalfixing.c.

References SCIP_DIDNOTFIND, and SCIP_OKAY.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PROP_NAME

◆ PROP_DESC

◆ PROP_TIMING

◆ PROP_PRIORITY

◆ PROP_FREQ

◆ PROP_DELAY

◆ TABLE_NAME_ORBITALFIXING

◆ TABLE_DESC_ORBITALFIXING

◆ TABLE_POSITION_ORBITALFIXING

◆ TABLE_EARLIEST_ORBITALFIXING

Function Documentation

◆ SCIP_DECL_TABLEOUTPUT()

◆ SCIP_DECL_TABLEFREE()

◆ performOrbitalFixing()

◆ computeBranchingVariables()

◆ propagateOrbitalFixing()

◆ SCIP_DECL_PROPFREE()

◆ SCIP_DECL_PROPINIT()

◆ SCIP_DECL_PROPEXIT()

◆ SCIP_DECL_PROPINITSOL()

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPRESPROP()