Detailed Description
constraint handler for linear ordering constraints
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.
Go to the source code of this file.
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 54 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()
|
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 FALSE, NULL, SCIP_CALL, 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 |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 167 of file cons_lop.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrLOP(), and TRUE.
◆ SCIP_DECL_CONSDELETE()
|
static |
frees specific constraint data
Definition at line 184 of file cons_lop.c.
References CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
◆ SCIP_DECL_CONSEXIT()
|
static |
deinitialization method of constraint handler (called before transformed problem is freed)
We output the final linear ordering.
Definition at line 213 of file cons_lop.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetSolVal(), SCIPgetSubscipDepth(), SCIPinfoMessage(), SCIPisFeasIntegral(), and SCIPsortIntInt().
◆ SCIP_DECL_CONSTRANS()
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 295 of file cons_lop.c.
References CONSHDLR_NAME, 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()
|
static |
LP initialization method of constraint handler
Definition at line 352 of file cons_lop.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateEmptyRowConshdlr(), SCIPdebug, SCIPdebugMsg, SCIPflushRowExtensions(), SCIPprintRow(), SCIPreleaseRow(), and SCIPsnprintf().
◆ SCIP_DECL_CONSSEPALP()
|
static |
separation method of constraint handler for LP solutions
Definition at line 417 of file cons_lop.c.
References CONSHDLR_NAME, LOPseparate(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), and SCIPdebugMsg.
◆ SCIP_DECL_CONSSEPASOL()
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 461 of file cons_lop.c.
References CONSHDLR_NAME, LOPseparate(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), and SCIPdebugMsg.
◆ SCIP_DECL_CONSENFOLP()
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 504 of file cons_lop.c.
References CONSHDLR_NAME, FALSE, NULL, 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(), and TRUE.
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 631 of file cons_lop.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPisFeasIntegral(), and TRUE.
◆ SCIP_DECL_CONSCHECK()
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 717 of file cons_lop.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasIntegral(), SCIPisGT(), SCIPprintCons(), SCIPvarGetName(), and TRUE.
◆ SCIP_DECL_CONSPROP()
|
static |
domain propagation method of constraint handler
Definition at line 820 of file cons_lop.c.
References CONSHDLR_NAME, FALSE, NULL, 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(), and TRUE.
◆ SCIP_DECL_CONSRESPROP()
|
static |
propagation conflict resolving method of constraint handler
Definition at line 939 of file cons_lop.c.
References CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPvarGetLbAtIndex(), SCIPvarGetUbAtIndex(), and TRUE.
◆ SCIP_DECL_CONSLOCK()
|
static |
variable rounding lock method of constraint handler
Definition at line 1029 of file cons_lop.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), and SCIPdebugMsg.
◆ SCIP_DECL_CONSPRINT()
|
static |
constraint display method of constraint handler
Definition at line 1068 of file cons_lop.c.
References CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetName(), SCIPinfoMessage(), and SCIPvarGetName().
◆ SCIP_DECL_CONSCOPY()
|
static |
constraint copying method of constraint handler
Definition at line 1111 of file cons_lop.c.
References BMSclearMemoryArray, CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPcreateConsLOP(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetVarCopy(), and TRUE.
◆ 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 1176 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, 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 1204 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(), and SCIP_DECL_READERREAD().