Detailed Description

convexproj separator

Author: Felipe Serrano

#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

scip	SCIP data structure
sepadata	separator 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

scip	SCIP data structure
sepa	the cut separator itself
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
exprit	expression iterator that can be used
row	storage 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

scip	SCIP data structure
sepadata	the 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

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 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

scip	SCIP data structure
sepadata	separator data
sol	solution that should be separated
maxviolation	buffer 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

scip	SCIP data structure
sepadata	separator data
nlrows	nlrows from which to store convex ones
nnlrows	number 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()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpConvexproj )

static

LP solution separation method of separator

Definition at line 712 of file sepa_convexproj.c.

References computeMaxViolation(), FALSE, NULL, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPaddNlpiProblemRows(), SCIPblkmem(), SCIPcreateCurrentSol(), SCIPcreateNlpiProblemFromNlRows(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPfeastol(), SCIPfreeSol(), SCIPgetCutoffbound(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetLPRows(), SCIPgetLPSolstat(), SCIPgetNlpis(), SCIPgetNLPNlRows(), SCIPgetNLPRows(), SCIPgetNNlpis(), SCIPgetNNLPNlRows(), SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPisLE(), SCIPisNLPConstructed(), SCIPisStopped(), SCIPsepaGetData(), SCIPupdateNlpiProblem(), 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_NLPITERLIM

◆ VIOLATIONFAC

Typedef Documentation

◆ CONVEXSIDE

Enumeration Type Documentation

◆ ConvexSide

Function Documentation

◆ sepadataClear()

◆ generateCut()

◆ setQuadraticObj()

◆ separateCuts()

◆ computeMaxViolation()

◆ storeNonlinearConvexNlrows()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAEXITSOL()

◆ SCIP_DECL_SEPAEXECLP()