Detailed Description

constraint handler for linear ordering constraints

Author: Marc Pfetsch

We handle the following system of linear constraints:

\( x_{ij} + x_{ji} = 1 \) for \(i < j\) (symmetry equations - added initially)
\( x_{ij} + x_{jk} + x_{ki} \leq 2 \) for \(i < j, i < k, j \neq k\) (triangle inequalities - separated)

Definition in file cons_lop.c.

#include "cons_lop.h"
#include <assert.h>
#include <string.h>

Macros
#define	CONSHDLR_NAME "lop"
#define	CONSHDLR_DESC "linear ordering constraint handler"
#define	CONSHDLR_SEPAPRIORITY 100
#define	CONSHDLR_ENFOPRIORITY -100
#define	CONSHDLR_CHECKPRIORITY -100
#define	CONSHDLR_SEPAFREQ 1
#define	CONSHDLR_PROPFREQ 1
#define	CONSHDLR_EAGERFREQ 100
#define	CONSHDLR_DELAYSEPA FALSE
#define	CONSHDLR_DELAYPROP FALSE
#define	CONSHDLR_NEEDSCONS TRUE
#define	CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Functions
static SCIP_RETCODE	LOPseparate (SCIP scip, SCIP_CONSHDLR conshdlr, int n, SCIP_VAR **vars, SCIP_SOL sol, int ngen, SCIP_Bool cutoff)
static	SCIP_DECL_CONSHDLRCOPY (conshdlrCopyLOP)
static	SCIP_DECL_CONSDELETE (consDeleteLOP)
static	SCIP_DECL_CONSEXIT (consExitLOP)
static	SCIP_DECL_CONSTRANS (consTransLOP)
static	SCIP_DECL_CONSINITLP (consInitlpLOP)
static	SCIP_DECL_CONSSEPALP (consSepalpLOP)
static	SCIP_DECL_CONSSEPASOL (consSepasolLOP)
static	SCIP_DECL_CONSENFOLP (consEnfolpLOP)
static	SCIP_DECL_CONSENFOPS (consEnfopsLOP)
static	SCIP_DECL_CONSCHECK (consCheckLOP)
static	SCIP_DECL_CONSPROP (consPropLOP)
static	SCIP_DECL_CONSRESPROP (consRespropLOP)
static	SCIP_DECL_CONSLOCK (consLockLOP)
static	SCIP_DECL_CONSPRINT (consPrintLOP)
static	SCIP_DECL_CONSCOPY (consCopyLOP)
SCIP_RETCODE	SCIPincludeConshdlrLOP (SCIP *scip)
SCIP_RETCODE	SCIPcreateConsLOP (SCIP scip, SCIP_CONS cons, const char name, int n, SCIP_VAR ***vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)

Macro Definition Documentation

◆ CONSHDLR_NAME

#define CONSHDLR_NAME "lop"

Definition at line 46 of file cons_lop.c.

◆ CONSHDLR_DESC

#define CONSHDLR_DESC "linear ordering constraint handler"

Definition at line 47 of file cons_lop.c.

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY 100

priority of the constraint handler for separation

Definition at line 48 of file cons_lop.c.

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY -100

priority of the constraint handler for constraint enforcing

Definition at line 49 of file cons_lop.c.

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY -100

priority of the constraint handler for checking feasibility

Definition at line 50 of file cons_lop.c.

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ 1

frequency for separating cuts; zero means to separate only in the root node

Definition at line 51 of file cons_lop.c.

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ 1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 52 of file cons_lop.c.

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ 100

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 53 of file cons_lop.c.

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 55 of file cons_lop.c.

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP FALSE

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

Definition at line 56 of file cons_lop.c.

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 57 of file cons_lop.c.

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 59 of file cons_lop.c.

Function Documentation

◆ LOPseparate()

SCIP_RETCODE LOPseparate	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr,
		int	n,
		SCIP_VAR ***	vars,
		SCIP_SOL *	sol,
		int *	ngen,
		SCIP_Bool *	cutoff )

static

separate symmetry equations and triangle inequalities

Parameters

scip	SCIP pointer
conshdlr	constraint handler
n	number of elements
vars	n x n matrix of variables
sol	solution to be separated
ngen	output: pointer to store number of added rows
cutoff	output: pointer to store whether we detected a cutoff

Definition at line 72 of file cons_lop.c.

References assert(), cutoff, FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPdebug, SCIPflushRowExtensions(), SCIPgetSolVal(), SCIPinfinity(), SCIPisEfficacious(), SCIPisFeasEQ(), SCIPprintRow(), SCIPreleaseRow(), SCIPsnprintf(), sol, TRUE, and vars.

Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSHDLRCOPY()

SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyLOP )

static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 169 of file cons_lop.c.

References assert(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrLOP(), TRUE, and valid.

◆ SCIP_DECL_CONSDELETE()

SCIP_DECL_CONSDELETE ( consDeleteLOP )

static

frees specific constraint data

Definition at line 186 of file cons_lop.c.

References assert(), CONSHDLR_NAME, i, NULL, SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.

◆ SCIP_DECL_CONSEXIT()

SCIP_DECL_CONSEXIT ( consExitLOP )

static

deinitialization method of constraint handler (called before transformed problem is freed)

We output the final linear ordering.

Definition at line 215 of file cons_lop.c.

References assert(), c, CONSHDLR_NAME, i, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetSubscipDepth(), SCIPinfoMessage(), SCIPisFeasIntegral(), SCIPsortIntInt(), sol, and vars.

◆ SCIP_DECL_CONSTRANS()

SCIP_DECL_CONSTRANS ( consTransLOP )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 297 of file cons_lop.c.

References assert(), CONSHDLR_NAME, i, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateCons(), SCIPdebugMsg, SCIPgetTransformedVar(), and SCIPsnprintf().

◆ SCIP_DECL_CONSINITLP()

SCIP_DECL_CONSINITLP ( consInitlpLOP )

static

LP initialization method of constraint handler

Definition at line 354 of file cons_lop.c.

References assert(), c, CONSHDLR_NAME, FALSE, i, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateEmptyRowConshdlr(), SCIPdebug, SCIPdebugMsg, SCIPflushRowExtensions(), SCIPprintRow(), SCIPreleaseRow(), SCIPsnprintf(), and vars.

◆ SCIP_DECL_CONSSEPALP()

SCIP_DECL_CONSSEPALP ( consSepalpLOP )

static

separation method of constraint handler for LP solutions

Definition at line 419 of file cons_lop.c.

References assert(), c, CONSHDLR_NAME, cutoff, LOPseparate(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), and SCIPdebugMsg.

◆ SCIP_DECL_CONSSEPASOL()

SCIP_DECL_CONSSEPASOL ( consSepasolLOP )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 463 of file cons_lop.c.

References assert(), c, CONSHDLR_NAME, cutoff, LOPseparate(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, and sol.

◆ SCIP_DECL_CONSENFOLP()

SCIP_DECL_CONSENFOLP ( consEnfolpLOP )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 506 of file cons_lop.c.

References assert(), c, CONSHDLR_NAME, FALSE, i, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateEmptyRowConshdlr(), SCIPdebug, SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPprintRow(), SCIPreleaseRow(), SCIPsnprintf(), TRUE, and vars.

◆ SCIP_DECL_CONSENFOPS()

SCIP_DECL_CONSENFOPS ( consEnfopsLOP )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 633 of file cons_lop.c.

References assert(), c, CONSHDLR_NAME, FALSE, i, NULL, result, SCIP_Bool, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPisFeasIntegral(), TRUE, and vars.

◆ SCIP_DECL_CONSCHECK()

SCIP_DECL_CONSCHECK ( consCheckLOP )

static

feasibility check method of constraint handler for integral solutions

Definition at line 719 of file cons_lop.c.

References assert(), c, CONSHDLR_NAME, FALSE, i, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasIntegral(), SCIPisGT(), SCIPprintCons(), SCIPvarGetName(), sol, TRUE, and vars.

◆ SCIP_DECL_CONSPROP()

SCIP_DECL_CONSPROP ( consPropLOP )

static

domain propagation method of constraint handler

Definition at line 822 of file cons_lop.c.

References assert(), c, CONSHDLR_NAME, FALSE, i, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPaddConflictBinvar(), SCIPanalyzeConflictCons(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPinferBinvarCons(), SCIPinitConflictAnalysis(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and vars.

◆ SCIP_DECL_CONSRESPROP()

SCIP_DECL_CONSRESPROP ( consRespropLOP )

static

propagation conflict resolving method of constraint handler

Definition at line 985 of file cons_lop.c.

References assert(), CONSHDLR_NAME, FALSE, NULL, result, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPABORT, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), TRUE, and vars.

◆ SCIP_DECL_CONSLOCK()

SCIP_DECL_CONSLOCK ( consLockLOP )

static

variable rounding lock method of constraint handler

Definition at line 1108 of file cons_lop.c.

References assert(), CONSHDLR_NAME, i, NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, and vars.

◆ SCIP_DECL_CONSPRINT()

SCIP_DECL_CONSPRINT ( consPrintLOP )

static

constraint display method of constraint handler

Definition at line 1147 of file cons_lop.c.

References assert(), CONSHDLR_NAME, i, NULL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPinfoMessage(), SCIPvarGetName(), and vars.

◆ SCIP_DECL_CONSCOPY()

SCIP_DECL_CONSCOPY ( consCopyLOP )

static

constraint copying method of constraint handler

Definition at line 1190 of file cons_lop.c.

References assert(), BMSclearMemoryArray, CONSHDLR_NAME, i, NULL, propagate, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateConsLOP(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetVarCopy(), separate(), TRUE, valid, and vars.

◆ SCIPincludeConshdlrLOP()

SCIP_RETCODE SCIPincludeConshdlrLOP ( SCIP * scip )

creates the handler for linear ordering constraints and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1255 of file cons_lop.c.

References assert(), CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYPROP, CONSHDLR_DELAYSEPA, CONSHDLR_DESC, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PROP_TIMING, CONSHDLR_PROPFREQ, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeConshdlrBasic(), SCIPsetConshdlrCopy(), SCIPsetConshdlrDelete(), SCIPsetConshdlrExit(), SCIPsetConshdlrInitlp(), SCIPsetConshdlrPrint(), SCIPsetConshdlrProp(), SCIPsetConshdlrResprop(), SCIPsetConshdlrSepa(), and SCIPsetConshdlrTrans().

Referenced by main(), and SCIP_DECL_CONSHDLRCOPY().

◆ SCIPcreateConsLOP()

SCIP_RETCODE SCIPcreateConsLOP	(	SCIP *	scip,
		SCIP_CONS **	cons,
		const char *	name,
		int	n,
		SCIP_VAR ***	vars,
		SCIP_Bool	initial,
		SCIP_Bool	separate,
		SCIP_Bool	enforce,
		SCIP_Bool	check,
		SCIP_Bool	propagate,
		SCIP_Bool	local,
		SCIP_Bool	modifiable,
		SCIP_Bool	dynamic,
		SCIP_Bool	removable,
		SCIP_Bool	stickingatnode )

creates and captures a linear ordering constraint

Parameters

scip	SCIP data structure
cons	pointer to hold the created constraint
name	name of constraint
n	number of elements
vars	n x n matrix of binary variables
initial	should the LP relaxation of constraint be in the initial LP?
separate	should the constraint be separated during LP processing?
enforce	should the constraint be enforced during node processing?
check	should the constraint be checked for feasibility?
propagate	should the constraint be propagated during node processing?
local	is constraint only valid locally?
modifiable	is constraint modifiable (subject to column generation)?
dynamic	is constraint subject to aging?
removable	should the relaxation be removed from the LP due to aging or cleanup?
stickingatnode	should the constraint always be kept at the node where it was added, even if it may be moved to a more global node?

Definition at line 1283 of file cons_lop.c.

References assert(), CONSHDLR_NAME, i, NULL, propagate, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPcreateCons(), SCIPerrorMessage, SCIPfindConshdlr(), separate(), and vars.

Referenced by SCIP_DECL_CONSCOPY(), and SCIP_DECL_READERREAD().

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_SEPAPRIORITY

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_SEPAFREQ

◆ CONSHDLR_PROPFREQ

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_DELAYSEPA

◆ CONSHDLR_DELAYPROP

◆ CONSHDLR_NEEDSCONS

◆ CONSHDLR_PROP_TIMING

Function Documentation

◆ LOPseparate()

◆ SCIP_DECL_CONSHDLRCOPY()

◆ SCIP_DECL_CONSDELETE()

◆ SCIP_DECL_CONSEXIT()

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSINITLP()

◆ SCIP_DECL_CONSSEPALP()

◆ SCIP_DECL_CONSSEPASOL()

◆ SCIP_DECL_CONSENFOLP()

◆ SCIP_DECL_CONSENFOPS()

◆ SCIP_DECL_CONSCHECK()

◆ SCIP_DECL_CONSPROP()

◆ SCIP_DECL_CONSRESPROP()

◆ SCIP_DECL_CONSLOCK()

◆ SCIP_DECL_CONSPRINT()

◆ SCIP_DECL_CONSCOPY()

◆ SCIPincludeConshdlrLOP()

◆ SCIPcreateConsLOP()