Detailed Description

convexproj separator

Author: Felipe Serrano

#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/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 > VIOLATIONFACSCIPfeastol /

#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 56 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 57 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY 0

Definition at line 58 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_FREQ

#define SEPA_FREQ -1

Definition at line 59 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 60 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 61 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 62 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 64 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 65 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ DEFAULT_NLPITERLIM

#define DEFAULT_NLPITERLIM 250

default NLP iteration limit

Definition at line 66 of file sepa_convexproj.c.

Referenced by SCIPincludeSepaConvexproj().

◆ VIOLATIONFAC

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

Definition at line 68 of file sepa_convexproj.c.

Referenced by SCIP_DECL_SEPAEXECLP().

◆ NLPVERBOSITY

#define NLPVERBOSITY 0

NLP solver verbosity

Definition at line 70 of file sepa_convexproj.c.

Referenced by separateCuts().

Typedef Documentation

◆ CONVEXSIDE

typedef enum ConvexSide CONVEXSIDE

Definition at line 82 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 77 of file sepa_convexproj.c.

Function Documentation

◆ sepadataClear()

static SCIP_RETCODE sepadataClear	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata
	)

static

clears the sepadata data

Parameters

scip	SCIP data structure
sepadata	separator data

Definition at line 121 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

scip	SCIP data structure
exprint	expressions interpreter
projection	point where we compute gradient
exprtree	exprtree for which we compute the gradient
grad	buffer to store the gradient

Definition at line 161 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

scip	SCIP data structure
sepa	the cut separator itself
exprint	expression interpreter
projection	point where we compute gradient cut
nlrow	constraint for which we generate gradient cut
convexside	which side makes the nlrow convex
activity	activity of constraint at projection
row	storage for cut

Definition at line 207 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

scip	SCIP data structure
sepadata	the cut separator data

Definition at line 327 of file sepa_convexproj.c.

References SCIP_QuadElement::coef, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImage(), 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

scip	SCIP data structure
sepa	the cut separator itself
sol	solution that should be separated
result	pointer to store the result of the separation call

Definition at line 371 of file sepa_convexproj.c.

References BMSclearMemoryArray, FALSE, generateCut(), LHS, MAX, MIN, 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(), SCIPhashmapGetImage(), SCIPisCutEfficacious(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisHugeValue(), SCIPisInfinity(), SCIPnlpiChgLinearCoefs(), SCIPnlpiGetSolstat(), SCIPnlpiGetSolution(), SCIPnlpiSetIntPar(), SCIPnlpiSetRealPar(), SCIPnlpiSolve(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPprintNlRow(), SCIPprintRow(), SCIPprintSol(), SCIPreleaseRow(), SCIPsepaGetData(), SCIPsetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetNLPSol(), SCIPvarGetUbLocal(), SQR, 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

scip	SCIP data structure
sepadata	separator data
sol	solution that should be separated
maxviolation	buffer to store maximum violation

Definition at line 624 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

scip	SCIP data structure
sepadata	separator data
nlrows	nlrows from which to store convex ones
nnlrows	number of nlrows

Definition at line 682 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 741 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 762 of file sepa_convexproj.c.

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

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpConvexproj )

static

LP solution separation method of separator

Definition at line 780 of file sepa_convexproj.c.

References computeMaxViolation(), FALSE, NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPaddNlpiProbRows(), SCIPblkmem(), SCIPcreateCurrentSol(), SCIPcreateNlpiProb(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPexprintCreate(), SCIPfeastol(), SCIPfreeSol(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPRows(), SCIPgetLPSolstat(), SCIPgetNlpis(), SCIPgetNLPNlRows(), SCIPgetNLPRows(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPisLE(), SCIPisNLPConstructed(), SCIPisStopped(), SCIPnlpiCreateProblem(), SCIPsepaGetData(), SCIPupdateNlpiProb(), sepadataClear(), separateCuts(), setQuadraticObj(), storeNonlinearConvexNlrows(), TRUE, and VIOLATIONFAC.

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_MAXDEPTH

◆ DEFAULT_NLPTIMELIMIT

◆ DEFAULT_NLPITERLIM

◆ VIOLATIONFAC

◆ NLPVERBOSITY

Typedef Documentation

◆ CONVEXSIDE

Enumeration Type Documentation

◆ ConvexSide

Function Documentation

◆ sepadataClear()

◆ computeGradient()

◆ generateCut()

◆ setQuadraticObj()

◆ separateCuts()

◆ computeMaxViolation()

◆ storeNonlinearConvexNlrows()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()