Scippy

SCIP

Solving Constraint Integer Programs

cons_lop.c File Reference

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>

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 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
scipSCIP pointer
conshdlrconstraint handler
nnumber of elements
varsn x n matrix of variables
solsolution to be separated
nGenoutput: pointer to store number of added rows
cutoffoutput: 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 SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyLOP  )
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 SCIP_DECL_CONSDELETE ( consDeleteLOP  )
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 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 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()

◆ SCIP_DECL_CONSINITLP()

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpLOP  )
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 SCIP_DECL_CONSSEPASOL ( consSepasolLOP  )
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()

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsLOP  )
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 SCIP_DECL_CONSCHECK ( consCheckLOP  )
static

◆ SCIP_DECL_CONSPROP()

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropLOP  )
static

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockLOP  )
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 SCIP_DECL_CONSPRINT ( consPrintLOP  )
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 SCIP_DECL_CONSCOPY ( consCopyLOP  )
static

◆ SCIPincludeConshdlrLOP()

◆ 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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nnumber of elements
varsn x n matrix of binary variables
initialshould the LP relaxation of constraint be in the initial LP?
separateshould the constraint be separated during LP processing?
enforceshould the constraint be enforced during node processing?
checkshould the constraint be checked for feasibility?
propagateshould the constraint be propagated during node processing?
localis constraint only valid locally?
modifiableis constraint modifiable (subject to column generation)?
dynamicis constraint subject to aging?
removableshould the relaxation be removed from the LP due to aging or cleanup?
stickingatnodeshould 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().