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 37 of file cons_lop.c.

Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSEXIT(), SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_CONSINITLP(), SCIP_DECL_CONSLOCK(), SCIP_DECL_CONSPRINT(), SCIP_DECL_CONSPROP(), SCIP_DECL_CONSRESPROP(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), SCIP_DECL_CONSTRANS(), SCIPcreateConsLOP(), and SCIPincludeConshdlrLOP().

◆ CONSHDLR_DESC

#define CONSHDLR_DESC "linear ordering constraint handler"

Definition at line 38 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY 100

priority of the constraint handler for separation

Definition at line 39 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY -100

priority of the constraint handler for constraint enforcing

Definition at line 40 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY -100

priority of the constraint handler for checking feasibility

Definition at line 41 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ 1

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

Definition at line 42 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ 1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 43 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

◆ 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 44 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA FALSE

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

Definition at line 47 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP FALSE

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

Definition at line 48 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS TRUE

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

Definition at line 49 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 51 of file cons_lop.c.

Referenced by SCIPincludeConshdlrLOP().

Function Documentation

◆ LOPseparate()

static 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 64 of file cons_lop.c.

References FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowConshdlr(), SCIPdebug, SCIPflushRowExtensions(), SCIPgetSolVal(), SCIPinfinity(), SCIPisEfficacious(), SCIPisFeasEQ(), SCIPprintRow(), SCIPreleaseRow(), SCIPsnprintf(), and TRUE.

Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyLOP )

static

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

Definition at line 159 of file cons_lop.c.

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

Referenced by LOPseparate().

◆ SCIP_DECL_CONSDELETE()

static SCIP_DECL_CONSDELETE ( consDeleteLOP )

static

frees specific constraint data

Definition at line 176 of file cons_lop.c.

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

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSEXIT()

static 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 205 of file cons_lop.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSTRANS(), SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetSubscipDepth(), SCIPinfoMessage(), SCIPisFeasIntegral(), and SCIPsortIntInt().

Referenced by SCIP_DECL_CONSDELETE().

◆ SCIP_DECL_CONSTRANS()

static SCIP_DECL_CONSTRANS ( consTransLOP )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 287 of file cons_lop.c.

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

Referenced by SCIP_DECL_CONSEXIT().

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpLOP )

static

LP initialization method of constraint handler

Definition at line 344 of file cons_lop.c.

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

Referenced by SCIP_DECL_CONSTRANS().

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpLOP )

static

separation method of constraint handler for LP solutions

Definition at line 409 of file cons_lop.c.

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

Referenced by SCIP_DECL_CONSINITLP().

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolLOP )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 453 of file cons_lop.c.

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

Referenced by SCIP_DECL_CONSSEPALP().

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpLOP )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 496 of file cons_lop.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFOPS(), 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(), and TRUE.

Referenced by SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsLOP )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 623 of file cons_lop.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_DECL_CONSCHECK(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPisFeasIntegral(), and TRUE.

Referenced by SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSCHECK()

static SCIP_DECL_CONSCHECK ( consCheckLOP )

static

feasibility check method of constraint handler for integral solutions

Definition at line 709 of file cons_lop.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasIntegral(), SCIPisGT(), SCIPprintCons(), SCIPvarGetName(), and TRUE.

Referenced by SCIP_DECL_CONSENFOPS().

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropLOP )

static

domain propagation method of constraint handler

Definition at line 812 of file cons_lop.c.

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

Referenced by SCIP_DECL_CONSCHECK().

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropLOP )

static

propagation conflict resolving method of constraint handler

Definition at line 931 of file cons_lop.c.

References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSLOCK(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPvarGetLbAtIndex(), SCIPvarGetUbAtIndex(), and TRUE.

Referenced by SCIP_DECL_CONSPROP().

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockLOP )

static

variable rounding lock method of constraint handler

Definition at line 1021 of file cons_lop.c.

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

Referenced by SCIP_DECL_CONSRESPROP().

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintLOP )

static

constraint display method of constraint handler

Definition at line 1060 of file cons_lop.c.

References CONSHDLR_NAME, NULL, SCIP_DECL_CONSCOPY(), SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPinfoMessage(), and SCIPvarGetName().

Referenced by SCIP_DECL_CONSLOCK().

◆ SCIP_DECL_CONSCOPY()

static SCIP_DECL_CONSCOPY ( consCopyLOP )

static

constraint copying method of constraint handler

Definition at line 1103 of file cons_lop.c.

References BMSclearMemoryArray, CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateConsLOP(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetVarCopy(), SCIPincludeConshdlrLOP(), and TRUE.

Referenced by SCIP_DECL_CONSPRINT().

◆ 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 1168 of file cons_lop.c.

References 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, SCIPcreateConsLOP(), SCIPincludeConshdlrBasic(), SCIPsetConshdlrCopy(), SCIPsetConshdlrDelete(), SCIPsetConshdlrExit(), SCIPsetConshdlrInitlp(), SCIPsetConshdlrPrint(), SCIPsetConshdlrProp(), SCIPsetConshdlrResprop(), SCIPsetConshdlrSepa(), and SCIPsetConshdlrTrans().

Referenced by main(), SCIP_DECL_CONSCOPY(), 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 1196 of file cons_lop.c.

References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocBlockMemory(), SCIPallocBlockMemoryArray, SCIPcreateCons(), SCIPerrorMessage, and SCIPfindConshdlr().

Referenced by SCIP_DECL_CONSCOPY(), SCIP_DECL_READERREAD(), and SCIPincludeConshdlrLOP().

SCIP

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