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 "nlpi/exprinterpret.h"
#include "nlpi/nlpi.h"
#include "nlpi/pub_expr.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_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/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 /* maximum depth at which the separator is applied; -1 means no limit */
 
#define DEFAULT_NLPTIMELIMIT   0.0
 
#define DEFAULT_NLPITERLIM   250
 
#define VIOLATIONFAC   100 /* points regarded violated if max violation > VIOLATIONFAC*SCIPfeastol */
 
#define NLPVERBOSITY   0
 

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 computeGradient (SCIP *scip, SCIP_EXPRINT *exprint, SCIP_SOL *projection, SCIP_EXPRTREE *exprtree, SCIP_Real *grad)
 
static SCIP_RETCODE generateCut (SCIP *scip, SCIP_SEPA *sepa, SCIP_EXPRINT *exprint, SCIP_SOL *projection, SCIP_NLROW *nlrow, CONVEXSIDE convexside, SCIP_Real activity, 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 58 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 59 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   0

Definition at line 60 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_FREQ

#define SEPA_FREQ   -1

Definition at line 61 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   1.0

Definition at line 62 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 63 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 64 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 66 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ DEFAULT_NLPTIMELIMIT

#define DEFAULT_NLPTIMELIMIT   0.0

default time limit of NLP solver; 0.0 for no limit

Definition at line 67 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ DEFAULT_NLPITERLIM

#define DEFAULT_NLPITERLIM   250

default NLP iteration limit

Definition at line 68 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ VIOLATIONFAC

#define VIOLATIONFAC   100 /* points regarded violated if max violation > VIOLATIONFAC*SCIPfeastol */

Definition at line 70 of file sepa_convexproj.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ NLPVERBOSITY

#define NLPVERBOSITY   0

NLP solver verbosity

Definition at line 72 of file sepa_convexproj.c.

Referenced by separateCuts().

Typedef Documentation

◆ CONVEXSIDE

typedef enum ConvexSide CONVEXSIDE

Definition at line 84 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 79 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 123 of file sepa_convexproj.c.

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

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

◆ computeGradient()

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

computes gradient of exprtree at projection

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

Definition at line 163 of file sepa_convexproj.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_SEPA sepa,
SCIP_EXPRINT exprint,
SCIP_SOL projection,
SCIP_NLROW nlrow,
CONVEXSIDE  convexside,
SCIP_Real  activity,
SCIP_ROW **  row 
)
static

computes gradient cut (linearization) of nlrow at projection

Parameters
scipSCIP data structure
sepathe cut separator itself
exprintexpression interpreter
projectionpoint where we compute gradient cut
nlrowconstraint for which we generate gradient cut
convexsidewhich side makes the nlrow convex
activityactivity of constraint at projection
rowstorage for cut

Definition at line 209 of file sepa_convexproj.c.

References SCIP_QuadElement::coef, computeGradient(), FALSE, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, LHS, NULL, RHS, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPchgRowLhs(), SCIPchgRowRhs(), SCIPcreateEmptyRowSepa(), SCIPdebug, SCIPdebugPrintf, SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPinfinity(), SCIPisInfinity(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetName(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), 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 329 of file sepa_convexproj.c.

References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImageInt(), and SCIPnlpiSetObjective().

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

References BMSclearMemoryArray, FALSE, generateCut(), LHS, MAX, NLPVERBOSITY, NULL, REALABS, RHS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_NLPPAR_FEASTOL, SCIP_NLPPAR_ITLIM, SCIP_NLPPAR_RELOBJTOL, SCIP_NLPPAR_TILIM, SCIP_NLPPAR_VERBLEVEL, 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, SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPdualfeastol(), SCIPerrorMessage, SCIPfeastol(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetCutEfficacy(), SCIPgetNLPObjval(), SCIPgetNLPVars(), SCIPgetNlRowSolActivity(), SCIPgetNNLPVars(), SCIPgetRealParam(), SCIPgetSolVal(), SCIPgetSolvingTime(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisCutEfficacious(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisHugeValue(), SCIPisInfinity(), SCIPnlpiChgLinearCoefs(), SCIPnlpiGetSolstat(), SCIPnlpiGetSolution(), SCIPnlpiSetIntPar(), SCIPnlpiSetRealPar(), SCIPnlpiSolve(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPprintNlRow(), SCIPprintRow(), SCIPprintSol(), SCIPreleaseRow(), SCIPsepaGetData(), SCIPsetSolVal(), 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 626 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 684 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(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetNQuadElems(), 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 743 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 764 of file sepa_convexproj.c.

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

◆ SCIP_DECL_SEPAEXECLP()