Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

convexproj separator

Author
Felipe Serrano

Definition in file sepa_convexproj.c.

#include <assert.h>
#include <string.h>
#include "blockmemshell/memory.h"
#include "scip/scip_expr.h"
#include "scip/scip_nlpi.h"
#include "scip/expr_varidx.h"
#include "scip/expr_pow.h"
#include "scip/expr_sum.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_nlp.h"
#include "scip/pub_sepa.h"
#include "scip/pub_var.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.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/scip_tree.h"
#include "scip/sepa_convexproj.h"

Go to the source code of this file.

Macros

#define SEPA_NAME   "convexproj"
 
#define SEPA_DESC   "separate at projection of point onto convex region"
 
#define SEPA_PRIORITY   0
 
#define SEPA_FREQ   -1
 
#define SEPA_MAXBOUNDDIST   1.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   TRUE
 
#define DEFAULT_MAXDEPTH   -1
 
#define DEFAULT_NLPITERLIM   250
 
#define VIOLATIONFAC   100
 

Typedefs

typedef enum ConvexSide CONVEXSIDE
 

Enumerations

enum  ConvexSide {
  LHS = 0,
  RHS = 1,
  LHS = 0,
  RHS = 1
}
 

Functions

static SCIP_RETCODE sepadataClear (SCIP *scip, SCIP_SEPADATA *sepadata)
 
static SCIP_RETCODE generateCut (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *projection, SCIP_NLROW *nlrow, CONVEXSIDE convexside, SCIP_Real activity, SCIP_EXPRITER *exprit, SCIP_ROW **row)
 
static SCIP_RETCODE setQuadraticObj (SCIP *scip, SCIP_SEPADATA *sepadata)
 
static SCIP_RETCODE separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
 
static SCIP_RETCODE computeMaxViolation (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *maxviolation)
 
static SCIP_RETCODE storeNonlinearConvexNlrows (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_NLROW **nlrows, int nnlrows)
 
static SCIP_DECL_SEPAFREE (sepaFreeConvexproj)
 
static SCIP_DECL_SEPAEXITSOL (sepaExitsolConvexproj)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpConvexproj)
 
SCIP_RETCODE SCIPincludeSepaConvexproj (SCIP *scip)
 

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME   "convexproj"

Definition at line 68 of file sepa_convexproj.c.

Referenced by SCIP_DECL_SEPAFREE(), and SCIPincludeSepaConvexproj().

◆ SEPA_DESC

#define SEPA_DESC   "separate at projection of point onto convex region"

Definition at line 69 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   0

Definition at line 70 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_FREQ

#define SEPA_FREQ   -1

Definition at line 71 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 72 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 73 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_DELAY

#define SEPA_DELAY   TRUE

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

Definition at line 74 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ DEFAULT_MAXDEPTH

#define DEFAULT_MAXDEPTH   -1

maximum depth at which the separator is applied; -1 means no limit

Definition at line 76 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ DEFAULT_NLPITERLIM

#define DEFAULT_NLPITERLIM   250

default NLP iteration limit

Definition at line 77 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ VIOLATIONFAC

#define VIOLATIONFAC   100

points regarded violated if max violation > VIOLATIONFAC*SCIPfeastol()

Definition at line 79 of file sepa_convexproj.c.

Referenced by SCIP_DECL_SEPAEXECLP().

Typedef Documentation

◆ CONVEXSIDE

typedef enum ConvexSide CONVEXSIDE

Definition at line 91 of file sepa_convexproj.c.

Enumeration Type Documentation

◆ ConvexSide

enum ConvexSide

side that makes an nlrow convex

Enumerator
LHS 

left hand side

RHS 

right hand side

LHS 

left hand side

RHS 

right hand side

Definition at line 86 of file sepa_convexproj.c.

Function Documentation

◆ sepadataClear()

static SCIP_RETCODE sepadataClear ( SCIP scip,
SCIP_SEPADATA sepadata 
)
static

clears the sepadata data

Parameters
scipSCIP data structure
sepadataseparator data

Definition at line 127 of file sepa_convexproj.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, and SCIPhashmapFree().

Referenced by SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXITSOL(), and SCIP_DECL_SEPAFREE().

◆ generateCut()

static SCIP_RETCODE generateCut ( SCIP scip,
SCIP_SEPA sepa,
SCIP_SOL projection,
SCIP_NLROW nlrow,
CONVEXSIDE  convexside,
SCIP_Real  activity,
SCIP_EXPRITER exprit,
SCIP_ROW **  row 
)
static

computes gradient cut (linearization) of nlrow at projection

Parameters
scipSCIP data structure
sepathe cut separator itself
projectionpoint where we compute gradient cut
nlrowconstraint for which we generate gradient cut
convexsidewhich side makes the nlrow convex
activityactivity of constraint at projection
expritexpression iterator that can be used
rowstorage for cut

Definition at line 166 of file sepa_convexproj.c.

References FALSE, LHS, NULL, RHS, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPcreateEmptyRowSepa(), SCIPdebug, SCIPdebugPrintf, SCIPevalExprGradient(), SCIPexprGetDerivative(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPflushRowExtensions(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPinfinity(), SCIPisExprVar(), SCIPisInfinity(), SCIPnlrowGetExpr(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetName(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetRhs(), SCIPprintRow(), SCIPsepaGetData(), SCIPsnprintf(), and TRUE.

Referenced by separateCuts().

◆ setQuadraticObj()

static SCIP_RETCODE setQuadraticObj ( SCIP scip,
SCIP_SEPADATA sepadata 
)
static

set quadratic part of objective function: \( \sum_i x_i^2 \)

the objective function is \( ||x - x_0||^2 \), where \( x_0 \) is the point to separate; the only part that changes is the term \( -2 \langle x_0, x \rangle \) which is linear and is set every time we want to separate a point, see separateCuts()

Parameters
scipSCIP data structure
sepadatathe cut separator data

Definition at line 268 of file sepa_convexproj.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcreateExprPow(), SCIPcreateExprSum(), SCIPcreateExprVaridx(), SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and SCIPreleaseExpr().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ separateCuts()

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

projects sol onto convex relaxation (stored in sepadata) and tries to generate gradient cuts at the projection

it generates cuts only for the constraints that were violated by the LP solution and are now active or still violated (in case we don't solve to optimality).

Parameters
scipSCIP data structure
sepathe cut separator itself
solsolution that should be separated
resultpointer to store the result of the separation call

Definition at line 321 of file sepa_convexproj.c.

References BMSclearMemoryArray, FALSE, generateCut(), LHS, MAX, NULL, REALABS, RHS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_NLPSOLSTAT_FEASIBLE, SCIP_NLPSOLSTAT_GLOBINFEASIBLE, SCIP_NLPSOLSTAT_GLOBOPT, SCIP_NLPSOLSTAT_LOCINFEASIBLE, SCIP_NLPSOLSTAT_LOCOPT, SCIP_NLPSOLSTAT_UNBOUNDED, SCIP_NLPSOLSTAT_UNKNOWN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPABORT, SCIPaddRow(), SCIPallocBufferArray, SCIPcreateExpriter(), SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPdualfeastol(), SCIPerrorMessage, SCIPfeastol(), SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPfreeSol(), SCIPgetCutEfficacy(), SCIPgetNLPObjval(), SCIPgetNLPVars(), SCIPgetNlRowSolActivity(), SCIPgetNNLPVars(), SCIPgetSolVal(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisCutEfficacious(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisHugeValue(), SCIPisInfinity(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPprintNlRow(), SCIPprintRow(), SCIPprintSol(), SCIPreleaseRow(), SCIPsepaGetData(), SCIPsetSolVal(), SCIPsolveNlpi, SCIPvarGetLbLocal(), SCIPvarGetNLPSol(), SCIPvarGetUbLocal(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ computeMaxViolation()

static SCIP_RETCODE computeMaxViolation ( SCIP scip,
SCIP_SEPADATA sepadata,
SCIP_SOL sol,
SCIP_Real maxviolation 
)
static

computes the violation and maximum violation of the convex nlrows stored in sepadata wrt sol

Parameters
scipSCIP data structure
sepadataseparator data
solsolution that should be separated
maxviolationbuffer to store maximum violation

Definition at line 557 of file sepa_convexproj.c.

References LHS, MAX, NULL, RHS, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetNlRowSolActivity(), SCIPisInfinity(), SCIPnlrowGetCurvature(), SCIPnlrowGetLhs(), and SCIPnlrowGetRhs().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ 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 615 of file sepa_convexproj.c.

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

Referenced by SCIP_DECL_SEPAEXECLP().

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeConvexproj  )
static

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

Definition at line 673 of file sepa_convexproj.c.

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

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolConvexproj  )
static

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

Definition at line 694 of file sepa_convexproj.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPsepaGetData(), and sepadataClear().

◆ SCIP_DECL_SEPAEXECLP()