Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

gauge separator

Author
Felipe Serrano

Definition in file sepa_gauge.c.

#include <assert.h>
#include <string.h>
#include "blockmemshell/memory.h"
#include "nlpi/exprinterpret.h"
#include "nlpi/nlpi.h"
#include "nlpi/nlpi_ipopt.h"
#include "nlpi/nlpioracle.h"
#include "nlpi/pub_expr.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_nlp.h"
#include "scip/pub_sepa.h"
#include "scip/scip_cut.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_nonlinear.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_timing.h"
#include "scip/sepa_gauge.h"

Go to the source code of this file.

Macros

#define SEPA_NAME   "gauge"
 
#define SEPA_DESC   "gauge separator"
 
#define SEPA_PRIORITY   0
 
#define SEPA_FREQ   -1
 
#define SEPA_MAXBOUNDDIST   1.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   FALSE
 
#define VIOLATIONFAC   100 /* constraints regarded as violated when violation > VIOLATIONFAC*SCIPfeastol */
 
#define MAX_ITER   75 /* maximum number of iterations for the line search */
 
#define DEFAULT_NLPTIMELIMIT   0.0
 
#define DEFAULT_NLPITERLIM   1000
 
#define NLPFEASFAC   1e-1
 
#define NLPVERBOSITY   0
 
#define INTERIOROBJVARLB   -100
 

Typedefs

typedef enum ConvexSide CONVEXSIDE
 
typedef enum Position POSITION
 

Enumerations

enum  ConvexSide {
  LHS = 0,
  RHS = 1,
  LHS = 0,
  RHS = 1
}
 
enum  Position {
  INTERIOR = 0,
  BOUNDARY = 1,
  EXTERIOR = 2
}
 

Functions

static SCIP_RETCODE storeNonlinearConvexNlrows (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROW **nlrows, int nnlrows)
 
static SCIP_RETCODE computeInteriorPoint (SCIP *scip, SCIP_SEPADATA *sepadata)
 
static SCIP_RETCODE findPointPosition (SCIP *scip, SCIP_NLROW **nlrows, int *nlrowsidx, int nnlrowsidx, CONVEXSIDE *convexsides, SCIP_SOL *point, POSITION *position)
 
static SCIP_RETCODE buildConvexCombination (SCIP *scip, SCIP_Real lambda, SCIP_SOL *startpoint, SCIP_SOL *endpoint, SCIP_SOL *convexcomb)
 
static SCIP_RETCODE findBoundaryPoint (SCIP *scip, SCIP_NLROW **nlrows, int *nlrowsidx, int nnlrowsidx, CONVEXSIDE *convexsides, SCIP_SOL *intsol, SCIP_SOL *tosepasol, SCIP_SOL *sol, POSITION *position)
 
static SCIP_RETCODE computeGradient (SCIP *scip, SCIP_EXPRINT *exprint, SCIP_SOL *sol, SCIP_EXPRTREE *exprtree, SCIP_Real *grad)
 
static SCIP_RETCODE generateCut (SCIP *scip, SCIP_SOL *sol, SCIP_EXPRINT *exprint, SCIP_NLROW *nlrow, CONVEXSIDE convexside, SCIP_ROW *row, SCIP_Bool *success)
 
static SCIP_RETCODE separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *tosepasol, SCIP_RESULT *result)
 
static SCIP_DECL_SEPAFREE (sepaFreeGauge)
 
static SCIP_DECL_SEPAEXITSOL (sepaExitsolGauge)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpGauge)
 
SCIP_RETCODE SCIPincludeSepaGauge (SCIP *scip)
 

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME   "gauge"

Definition at line 59 of file sepa_gauge.c.

Referenced by SCIP_DECL_SEPAFREE(), and SCIPincludeSepaGauge().

◆ SEPA_DESC

#define SEPA_DESC   "gauge separator"

Definition at line 60 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   0

Definition at line 61 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_FREQ

#define SEPA_FREQ   -1

Definition at line 62 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 63 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 64 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

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

Definition at line 65 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ VIOLATIONFAC

#define VIOLATIONFAC   100 /* constraints regarded as violated when violation > VIOLATIONFAC*SCIPfeastol */

Definition at line 67 of file sepa_gauge.c.

Referenced by SCIP_DECL_SEPAEXECLP(), and separateCuts().

◆ MAX_ITER

#define MAX_ITER   75 /* maximum number of iterations for the line search */

Definition at line 68 of file sepa_gauge.c.

Referenced by findBoundaryPoint().

◆ DEFAULT_NLPTIMELIMIT

#define DEFAULT_NLPTIMELIMIT   0.0

default time limit of NLP solver; 0.0 for no limit

Definition at line 70 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ DEFAULT_NLPITERLIM

#define DEFAULT_NLPITERLIM   1000

default NLP iteration limit

Definition at line 71 of file sepa_gauge.c.

Referenced by SCIPincludeSepaGauge().

◆ NLPFEASFAC

#define NLPFEASFAC   1e-1

NLP feasibility tolerance = NLPFEASFAC * SCIP's feasibility tolerance

Definition at line 73 of file sepa_gauge.c.

Referenced by computeInteriorPoint().

◆ NLPVERBOSITY

#define NLPVERBOSITY   0

NLP solver verbosity

Definition at line 74 of file sepa_gauge.c.

Referenced by computeInteriorPoint().

◆ INTERIOROBJVARLB

#define INTERIOROBJVARLB   -100

lower bound of the objective variable when computing interior point

Definition at line 76 of file sepa_gauge.c.

Referenced by computeInteriorPoint().

Typedef Documentation

◆ CONVEXSIDE

typedef enum ConvexSide CONVEXSIDE

Definition at line 87 of file sepa_gauge.c.

◆ POSITION

typedef enum Position POSITION

Definition at line 96 of file sepa_gauge.c.

Enumeration Type Documentation

◆ ConvexSide

enum ConvexSide

side that makes a nlrow convex

Enumerator
LHS 

left hand side

RHS 

right hand side

LHS 

left hand side

RHS 

right hand side

Definition at line 82 of file sepa_gauge.c.

◆ Position

enum Position

position of a point

Enumerator
INTERIOR 

point is in the interior of the region

BOUNDARY 

point is in the boundary of the region

EXTERIOR 

point is in the exterior of the region

Definition at line 90 of file sepa_gauge.c.

Function Documentation

◆ storeNonlinearConvexNlrows()

static SCIP_RETCODE storeNonlinearConvexNlrows ( SCIP scip,
SCIP_SEPADATA sepadata,
SCIP_NLROW **  nlrows,
int  nnlrows 
)
static

stores, from the constraints represented by nlrows, the nonlinear convex ones in sepadata

Parameters
scipSCIP data structure
sepadataseparator data
nlrowsnlrows from which to store convex ones
nnlrowsnumber of nlrows

Definition at line 127 of file sepa_gauge.c.

References LHS, NULL, RHS, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetNQuadElems(), and SCIPnlrowGetRhs().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ computeInteriorPoint()

static SCIP_RETCODE computeInteriorPoint ( SCIP scip,
SCIP_SEPADATA sepadata 
)
static

computes an interior point of a convex NLP relaxation; builds the convex relaxation, modifies it to find an interior point, solves it and frees it; more details in sepa_gauge.h

Note
the method also counts the number of nonlinear convex constraints and if there are < 2, then the convex relaxation is not interesting and the separator will not run again
Parameters
scipSCIP data structure
sepadataseparator data

Definition at line 186 of file sepa_gauge.c.

References FALSE, INTERIOROBJVARLB, MAX, NLPFEASFAC, NLPVERBOSITY, NULL, SCIP_CALL, SCIP_NLPPAR_FEASTOL, SCIP_NLPPAR_ITLIM, SCIP_NLPPAR_RELOBJTOL, SCIP_NLPPAR_TILIM, SCIP_NLPPAR_VERBLEVEL, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_OKAY, SCIP_Real, SCIPaddNlpiProbRows(), SCIPblkmem(), SCIPcreateNlpiProb(), SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPdualfeastol(), SCIPfeastol(), SCIPgetCutoffbound(), SCIPgetLPRows(), SCIPgetMessagehdlr(), SCIPgetNlpiOracleIpopt(), SCIPgetNlpis(), SCIPgetNLPNlRows(), SCIPgetNLPRows(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNVars(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPnlpiAddVars(), SCIPnlpiChgLinearCoefs(), SCIPnlpiCreateProblem(), SCIPnlpiFreeProblem(), SCIPnlpiGetName(), SCIPnlpiGetSolstat(), SCIPnlpiGetSolution(), SCIPnlpiGetStatistics(), SCIPnlpiOracleGetConstraintDegree(), SCIPnlpiOracleGetNConstraints(), SCIPnlpiOracleGetNVars(), SCIPnlpiOraclePrintProblem(), SCIPnlpiSetIntPar(), SCIPnlpiSetObjective(), SCIPnlpiSetRealPar(), SCIPnlpiSolve(), SCIPnlpStatisticsCreate(), SCIPnlpStatisticsFree(), SCIPnlpStatisticsGetNIterations(), SCIPnlpStatisticsGetTotalTime(), SCIPsetSolVal(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ findPointPosition()

static SCIP_RETCODE findPointPosition ( SCIP scip,
SCIP_NLROW **  nlrows,
int *  nlrowsidx,
int  nnlrowsidx,
CONVEXSIDE convexsides,
SCIP_SOL point,
POSITION position 
)
static

find whether point is in the interior, at the boundary or in the exterior of the region described by the intersection of nlrows[i] <= rhs if convexsides[i] = RHS or lhs <= nlrows[i] if convexsides[i] = LHS

Note
: point corresponds to a convex combination between the lp solution and the interior point
Parameters
scipSCIP data structure
nlrowsnlrows defining the region
nlrowsidxindices of nlrows defining the region
nnlrowsidxnumber of nlrows indices
convexsidessides of the nlrows involved in the region
pointpoint for which we want to know its position
positionbuffer to store position of sol

Definition at line 364 of file sepa_gauge.c.

References BOUNDARY, EXTERIOR, INTERIOR, LHS, NULL, RHS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMsg, SCIPgetNlRowSolActivity(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisInfinity(), SCIPnlrowGetLhs(), SCIPnlrowGetName(), SCIPnlrowGetRhs(), and SCIPprintNlRow().

Referenced by findBoundaryPoint(), and separateCuts().

◆ buildConvexCombination()

static SCIP_RETCODE buildConvexCombination ( SCIP scip,
SCIP_Real  lambda,
SCIP_SOL startpoint,
SCIP_SOL endpoint,
SCIP_SOL convexcomb 
)
static

returns, in convexcomb, the convex combination \( \lambda \) endpoint + (1 - \( lambda \)) startpoint = startpoint + \( \lambda \) (endpoint - tosepasol)

Parameters
scipSCIP data structure
lambdaconvex combination multiplier
startpointpoint corresponding to \( \lambda = 0 \)
endpointpoint corresponding to \( \lambda = 1 \)
convexcombsolution to store convex combination of intsol and tosepasol

Definition at line 440 of file sepa_gauge.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisZero(), and SCIPsetSolVal().

Referenced by findBoundaryPoint(), and separateCuts().

◆ findBoundaryPoint()

static SCIP_RETCODE findBoundaryPoint ( SCIP scip,
SCIP_NLROW **  nlrows,
int *  nlrowsidx,
int  nnlrowsidx,
CONVEXSIDE convexsides,
SCIP_SOL intsol,
SCIP_SOL tosepasol,
SCIP_SOL sol,
POSITION position 
)
static

performs binary search to find the point belonging to the segment [intsol, tosepasol] that intersects the boundary of the region described by the intersection of nlrows[i] <= rhs if convexsides[i] = RHS or lhs <= nlrows[i] if not, for i in nlrowsidx

Parameters
scipSCIP data structure
nlrowsnlrows defining the region
nlrowsidxindices of nlrows defining the region
nnlrowsidxnumber of nlrows indices
convexsidessides of the nlrows involved in the region
intsolpoint acting as 'interior point'
tosepasolsolution that should be separated
solconvex combination of intsol and lpsol
positionbuffer to store position of sol

Definition at line 487 of file sepa_gauge.c.

References BOUNDARY, buildConvexCombination(), EXTERIOR, findPointPosition(), INTERIOR, MAX_ITER, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPdebugMsg.

Referenced by separateCuts().

◆ computeGradient()

static SCIP_RETCODE computeGradient ( SCIP scip,
SCIP_EXPRINT exprint,
SCIP_SOL sol,
SCIP_EXPRTREE exprtree,
SCIP_Real grad 
)
static

computes gradient of exprtree at sol

Parameters
scipSCIP data structure
exprintexpressions interpreter
solpoint where we compute gradient
exprtreeexprtree for which we compute the gradient
gradbuffer to store the gradient

Definition at line 548 of file sepa_gauge.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPfreeBufferArray, SCIPgetSolVal(), TRUE, and x.

Referenced by generateCut().

◆ generateCut()

static SCIP_RETCODE generateCut ( SCIP scip,
SCIP_SOL sol,
SCIP_EXPRINT exprint,
SCIP_NLROW nlrow,
CONVEXSIDE  convexside,
SCIP_ROW row,
SCIP_Bool success 
)
static

computes gradient cut (linearization) of nlrow at sol

Parameters
scipSCIP data structure
solpoint used to construct gradient cut (x_0)
exprintexpression interpreter
nlrowconstraint
convexsidewhether we use rhs or lhs of nlrow
rowstorage for cut
successbuffer to store whether the gradient was finite

Definition at line 595 of file sepa_gauge.c.

References SCIP_QuadElement::coef, computeGradient(), FALSE, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, LHS, NULL, RHS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPdebug, SCIPdebugMsg, SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetNlRowSolActivity(), SCIPgetSolVal(), SCIPisFinite, SCIPisInfinity(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPnlrowGetRhs(), SCIPprintRow(), and TRUE.

Referenced by separateCuts().

◆ separateCuts()

static SCIP_RETCODE separateCuts ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SOL tosepasol,
SCIP_RESULT result 
)
static

tries to generate gradient cuts at the point on the segment [intsol, tosepasol] that intersecs the boundary of the convex relaxation

  1. checks that the relative interior of the segment actually intersects the boundary (this check is needed since intsol is not necessarily an interior point)
  2. finds point on the boundary
  3. generates gradient cut at point on the boundary
Parameters
scipSCIP data structure
sepathe cut separator itself
tosepasolsolution that should be separated
resultpointer to store the result of the separation call

Definition at line 727 of file sepa_gauge.c.

References BOUNDARY, buildConvexCombination(), EXTERIOR, FALSE, findBoundaryPoint(), findPointPosition(), generateCut(), INTERIOR, LHS, NULL, RHS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddRow(), SCIPcreateEmptyRowSepa(), SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPfeastol(), SCIPfreeSol(), SCIPgetCutEfficacy(), SCIPgetNlRowSolActivity(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasEQ(), SCIPnlrowGetLhs(), SCIPnlrowGetName(), SCIPnlrowGetRhs(), SCIPprintSol(), SCIPreleaseRow(), SCIProwGetName(), SCIPsepaGetData(), SCIPsnprintf(), TRUE, and VIOLATIONFAC.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeGauge  )
static

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

Definition at line 885 of file sepa_gauge.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolGauge  )
static

solving process deinitialization method of separator (called before branch and bound process data is freed)

Definition at line 905 of file sepa_gauge.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPexprintFree(), SCIPfreeBlockMemoryArray, SCIPfreeSol(), and SCIPsepaGetData().

◆ SCIP_DECL_SEPAEXECLP()