Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

filterSQP NLP interface

Author
Stefan Vigerske

Definition in file nlpi_filtersqp.c.

#include <string.h>
#include <sys/time.h>
#include "scip/nlpi_filtersqp.h"
#include "scip/nlpioracle.h"
#include "scip/scip_general.h"
#include "scip/scip_message.h"
#include "scip/scip_mem.h"
#include "scip/scip_numerics.h"
#include "scip/scip_nlpi.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_solve.h"
#include "scip/pub_misc.h"

Go to the source code of this file.

Data Structures

struct  SCIP_Time
 
struct  SCIP_NlpiProblem
 

Macros

#define NLPI_NAME   "filtersqp"
 
#define NLPI_DESC   "Sequential Quadratic Programming trust region solver by R. Fletcher and S. Leyffer"
 
#define NLPI_PRIORITY   -1000
 
#define RANDSEED   26051979
 
#define MAXPERTURB   0.01
 
#define MAXNRUNS   3
 
#define WORKSPACEGROWTHFACTOR   2
 
#define MINEPS   1e-14
 
#define OPTTOLFACTOR   0.5
 

Typedefs

typedef int fint
 
typedef double real
 
typedef long ftnlen
 
typedef struct SCIP_Time SCIP_TIME
 

Functions

void F77_FUNC (filtersqp, FILTERSQP)
 
 F77_FUNC (cpname, CPNAME)
 
struct {
   fint   phl
 
   fint   phr
 
   fint   phc
 
F77_FUNC (hessc, HESSC)
 
struct {
   real   ubd
 
   real   tt
 
F77_FUNC (ubdc, UBDC)
 
struct {
   real   infty
 
   real   eps
 
F77_FUNC (nlp_eps_inf, NLP_EPS_INF)
 
struct {
   fint   n_bqpd_calls
 
   fint   n_bqpd_prfint
 
F77_FUNC (bqpd_count, BQPD_COUNT)
 
struct {
   fint   scale_mode
 
   fint   phe
 
F77_FUNC (scalec, SCALEC)
 
static SCIP_TIME gettime (void)
 
static SCIP_Real timeelapsed (SCIP_NLPIDATA *nlpidata)
 
static SCIP_Bool timelimitreached (SCIP_NLPIDATA *nlpidata, SCIP_NLPIPROBLEM *nlpiproblem)
 
void F77_FUNC (objfun, OBJFUN)
 
void F77_FUNC (confun, CONFUN)
 
void F77_FUNC (gradient, GRADIENT)
 
void F77_FUNC (objgrad, OBJGRAD)
 
void F77_FUNC (hessian, HESSIAN)
 
static SCIP_RETCODE setupGradients (SCIP *scip, SCIP_NLPIORACLE *oracle, fint **la, int *lasize, real **a)
 
static SCIP_RETCODE setupHessian (SCIP *scip, SCIP_NLPIORACLE *oracle, fint **la, int *lasize)
 
static SCIP_RETCODE setupStart (SCIP_NLPIDATA *data, SCIP_NLPIPROBLEM *problem, real *x, SCIP_Bool *success)
 
static void invalidateSolution (SCIP_NLPIPROBLEM *problem)
 
static SCIP_RETCODE handleNlpParam (SCIP *scip, SCIP_NLPIPROBLEM *nlpiproblem, const SCIP_NLPPARAM param)
 
static SCIP_RETCODE processSolveOutcome (SCIP_NLPIDATA *nlpidata, SCIP_NLPIPROBLEM *problem, fint ifail, SCIP_Real feastol, SCIP_Real opttol, real *x, real *lam)
 
static SCIP_DECL_NLPICOPY (nlpiCopyFilterSQP)
 
static SCIP_DECL_NLPIFREE (nlpiFreeFilterSQP)
 
static SCIP_DECL_NLPICREATEPROBLEM (nlpiCreateProblemFilterSQP)
 
static SCIP_DECL_NLPIFREEPROBLEM (nlpiFreeProblemFilterSQP)
 
static SCIP_DECL_NLPIADDVARS (nlpiAddVarsFilterSQP)
 
static SCIP_DECL_NLPIADDCONSTRAINTS (nlpiAddConstraintsFilterSQP)
 
static SCIP_DECL_NLPISETOBJECTIVE (nlpiSetObjectiveFilterSQP)
 
static SCIP_DECL_NLPICHGVARBOUNDS (nlpiChgVarBoundsFilterSQP)
 
static SCIP_DECL_NLPICHGCONSSIDES (nlpiChgConsSidesFilterSQP)
 
static SCIP_DECL_NLPIDELVARSET (nlpiDelVarSetFilterSQP)
 
static SCIP_DECL_NLPIDELCONSSET (nlpiDelConstraintSetFilterSQP)
 
static SCIP_DECL_NLPICHGLINEARCOEFS (nlpiChgLinearCoefsFilterSQP)
 
static SCIP_DECL_NLPICHGEXPR (nlpiChgExprFilterSQP)
 
static SCIP_DECL_NLPICHGOBJCONSTANT (nlpiChgObjConstantFilterSQP)
 
static SCIP_DECL_NLPISETINITIALGUESS (nlpiSetInitialGuessFilterSQP)
 
static SCIP_DECL_NLPISOLVE (nlpiSolveFilterSQP)
 
static SCIP_DECL_NLPIGETSOLSTAT (nlpiGetSolstatFilterSQP)
 
static SCIP_DECL_NLPIGETTERMSTAT (nlpiGetTermstatFilterSQP)
 
static SCIP_DECL_NLPIGETSOLUTION (nlpiGetSolutionFilterSQP)
 
static SCIP_DECL_NLPIGETSTATISTICS (nlpiGetStatisticsFilterSQP)
 
SCIP_RETCODE SCIPincludeNlpSolverFilterSQP (SCIP *scip)
 
const char * SCIPgetSolverNameFilterSQP (void)
 
const char * SCIPgetSolverDescFilterSQP (void)
 
SCIP_Bool SCIPisFilterSQPAvailableFilterSQP (void)
 

Macro Definition Documentation

◆ NLPI_NAME

#define NLPI_NAME   "filtersqp"

short concise name of solver

Definition at line 53 of file nlpi_filtersqp.c.

Referenced by SCIPincludeNlpSolverFilterSQP().

◆ NLPI_DESC

#define NLPI_DESC   "Sequential Quadratic Programming trust region solver by R. Fletcher and S. Leyffer"

description of solver

Definition at line 54 of file nlpi_filtersqp.c.

Referenced by SCIPgetSolverDescFilterSQP(), and SCIPincludeNlpSolverFilterSQP().

◆ NLPI_PRIORITY

#define NLPI_PRIORITY   -1000

priority of NLP solver

Definition at line 55 of file nlpi_filtersqp.c.

Referenced by SCIPincludeNlpSolverFilterSQP().

◆ RANDSEED

#define RANDSEED   26051979

initial random seed

Definition at line 57 of file nlpi_filtersqp.c.

Referenced by setupStart().

◆ MAXPERTURB

#define MAXPERTURB   0.01

maximal perturbation of bounds in starting point heuristic

Definition at line 58 of file nlpi_filtersqp.c.

Referenced by setupStart().

◆ MAXNRUNS

#define MAXNRUNS   3

maximal number of FilterSQP calls per NLP solve (several calls if increasing workspace or decreasing eps)

Definition at line 59 of file nlpi_filtersqp.c.

Referenced by SCIP_DECL_NLPISOLVE().

◆ WORKSPACEGROWTHFACTOR

#define WORKSPACEGROWTHFACTOR   2

factor by which to increase workspace

Definition at line 60 of file nlpi_filtersqp.c.

Referenced by SCIP_DECL_NLPISOLVE().

◆ MINEPS

#define MINEPS   1e-14

minimal FilterSQP epsilon

Definition at line 61 of file nlpi_filtersqp.c.

Referenced by SCIP_DECL_NLPISOLVE().

◆ OPTTOLFACTOR

#define OPTTOLFACTOR   0.5

factor to apply to optimality tolerance, because FilterSQP do scaling

Definition at line 62 of file nlpi_filtersqp.c.

Referenced by SCIP_DECL_NLPISOLVE().

Typedef Documentation

◆ fint

typedef int fint

Definition at line 68 of file nlpi_filtersqp.c.

◆ real

typedef double real

Definition at line 69 of file nlpi_filtersqp.c.

◆ ftnlen

typedef long ftnlen

Definition at line 70 of file nlpi_filtersqp.c.

◆ SCIP_TIME

typedef struct SCIP_Time SCIP_TIME

Definition at line 77 of file nlpi_filtersqp.c.

Function Documentation

◆ F77_FUNC() [1/12]

void F77_FUNC ( filtersqp  ,
FILTERSQP   
)

FilterSQP main routine.

Array a has length nnza, which is the number of nonzeros in the gradient of the objective and the Jacobian. The first entries of a is the objective gradient, next are the gradients of the constraints.

Array la has length lamax, which is at least nnza+m+2. la contains the index information of a row-oriented sparse matrix storage. It stores the number of nonzeros, the column indices, and the row starts: la[0] must be set to nnza+1. la[1]..la[nnza] are indices of the variables corresponding to the entries in a (colidx). la[nnza+1]..la[nnza+1+m] contain the index where each row starts in a and la (rowstart).common block for problemname

Definition at line 160 of file nlpi_filtersqp.c.

Referenced by SCIP_DECL_NLPISOLVE(), and setupHessian().

◆ F77_FUNC() [2/12]

F77_FUNC ( cpname  ,
CPNAME   
)

◆ F77_FUNC() [3/12]

struct @6 F77_FUNC ( hessc  ,
HESSC   
)

common block for Hessian storage set to 0, i.e. NO Hessian

◆ F77_FUNC() [4/12]

struct @7 F77_FUNC ( ubdc  ,
UBDC   
)

common block for upper bound on filter

◆ F77_FUNC() [5/12]

struct @8 F77_FUNC ( nlp_eps_inf  ,
NLP_EPS_INF   
)

common block for infinity & epsilon

◆ F77_FUNC() [6/12]

struct @9 F77_FUNC ( bqpd_count  ,
BQPD_COUNT   
)

common block for printing from QP solver

◆ F77_FUNC() [7/12]

struct @10 F77_FUNC ( scalec  ,
SCALEC   
)

common for scaling: scale_mode = 0 (none), 1 (variables), 2 (vars+cons)

◆ gettime()

static SCIP_TIME gettime ( void  )
static

Definition at line 265 of file nlpi_filtersqp.c.

References NULL, SCIP_Time::sec, and SCIP_Time::usec.

Referenced by SCIP_DECL_NLPISOLVE(), and timeelapsed().

◆ timeelapsed()

static SCIP_Real timeelapsed ( SCIP_NLPIDATA nlpidata)
static
Parameters
nlpidataNLPI data

Definition at line 287 of file nlpi_filtersqp.c.

References gettime(), NULL, SCIP_Real, SCIP_Time::sec, and SCIP_Time::usec.

Referenced by processSolveOutcome(), and timelimitreached().

◆ timelimitreached()

static SCIP_Bool timelimitreached ( SCIP_NLPIDATA nlpidata,
SCIP_NLPIPROBLEM nlpiproblem 
)
static
Parameters
nlpidataNLPI data
nlpiproblemNLPI problem

Definition at line 305 of file nlpi_filtersqp.c.

References FALSE, SCIP_NlpiProblem::maxtime, SCIP_REAL_MAX, and timeelapsed().

Referenced by F77_FUNC(), and SCIP_DECL_NLPISOLVE().

◆ F77_FUNC() [8/12]

void F77_FUNC ( objfun  ,
OBJFUN   
)

Objective function evaluation set to 1 if arithmetic exception occurs, otherwise 0

Definition at line 317 of file nlpi_filtersqp.c.

References NULL, SCIP_NlpiProblem::oracle, SCIP_NlpiProblem::scip, SCIP_OKAY, SCIPdebugMsg, SCIPisFinite, SCIPisSolveInterrupted(), SCIPnlpiOracleEvalObjectiveValue(), timelimitreached(), and x.

◆ F77_FUNC() [9/12]

void F77_FUNC ( confun  ,
CONFUN   
)

Constraint functions evaluation set to 1 if arithmetic exception occurs, otherwise 0

Definition at line 352 of file nlpi_filtersqp.c.

References NULL, SCIP_NlpiProblem::oracle, SCIP_NlpiProblem::scip, SCIP_OKAY, SCIPdebugMsg, SCIPisFinite, SCIPnlpiOracleEvalConstraintValue(), and x.

◆ F77_FUNC() [10/12]

void F77_FUNC ( gradient  ,
GRADIENT   
)

Objective gradient and Jacobian evaluation

Note
If an arithmetic exception occurred, then the gradients must not be modified.set to 1 if arithmetic exception occurs, otherwise 0

Definition at line 389 of file nlpi_filtersqp.c.

References a, BMScopyMemoryArray, SCIP_NlpiProblem::evalbuffer, SCIP_NlpiProblem::evalbufsize, NULL, SCIP_NlpiProblem::oracle, SCIP_NlpiProblem::scip, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPnlpiOracleEvalJacobian(), SCIPnlpiOracleEvalObjectiveGradient(), TRUE, and x.

◆ F77_FUNC() [11/12]

void F77_FUNC ( objgrad  ,
OBJGRAD   
)

Definition at line 445 of file nlpi_filtersqp.c.

References SCIPerrorMessage.

◆ F77_FUNC() [12/12]

void F77_FUNC ( hessian  ,
HESSIAN   
)

Hessian of the Lagrangian evaluation

phase = 1 : Hessian of the Lagrangian without objective Hessian

phase = 2 : Hessian of the Lagrangian (including objective Hessian)

Note
If an arithmetic exception occurred, then the Hessian must not be modified.set to 1 if arithmetic exception occurs, otherwise 0

Definition at line 459 of file nlpi_filtersqp.c.

References BMSallocMemoryArray, BMScopyMemoryArray, BMSfreeMemoryArray, SCIP_NlpiProblem::evalbuffer, SCIP_NlpiProblem::evalbufsize, SCIP_NlpiProblem::hessiannz, NULL, SCIP_NlpiProblem::oracle, SCIP_NlpiProblem::scip, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPnlpiOracleEvalHessianLag(), TRUE, and x.

◆ setupGradients()

static SCIP_RETCODE setupGradients ( SCIP scip,
SCIP_NLPIORACLE oracle,
fint **  la,
int *  lasize,
real **  a 
)
static
Parameters
scipSCIP data structure
oracleNLPI oracle
labuffer to store pointer to sparsity structure
lasizebuffer to store length of *la array
abuffer to store pointer to value buffer

Definition at line 517 of file nlpi_filtersqp.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPnlpiOracleGetJacobianSparsity(), SCIPnlpiOracleGetNConstraints(), and SCIPnlpiOracleGetNVars().

Referenced by SCIP_DECL_NLPISOLVE().

◆ setupHessian()

static SCIP_RETCODE setupHessian ( SCIP scip,
SCIP_NLPIORACLE oracle,
fint **  la,
int *  lasize 
)
static
Parameters
scipSCIP data structure
oracleNLPI oracle
labuffer to store pointer to Hessian sparsity structure
lasizebuffer to store length of *la array

Definition at line 586 of file nlpi_filtersqp.c.

References F77_FUNC(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPnlpiOracleGetHessianLagSparsity(), and SCIPnlpiOracleGetNVars().

Referenced by SCIP_DECL_NLPISOLVE().

◆ setupStart()

◆ invalidateSolution()

◆ handleNlpParam()

static SCIP_RETCODE handleNlpParam ( SCIP scip,
SCIP_NLPIPROBLEM nlpiproblem,
const SCIP_NLPPARAM  param 
)
static

store NLP solve parameters in nlpiproblem

Parameters
scipSCIP data structure
nlpiproblemNLP
paramsolve parameters

Definition at line 737 of file nlpi_filtersqp.c.

References SCIP_NlpParam::fastfail, SCIP_NlpiProblem::fmin, SCIP_NlpParam::lobjlimit, SCIP_NlpiProblem::maxtime, NULL, SCIP_OKAY, SCIPdebugMsg, and SCIP_NlpParam::timelimit.

Referenced by SCIP_DECL_NLPISOLVE().

◆ processSolveOutcome()

static SCIP_RETCODE processSolveOutcome ( SCIP_NLPIDATA nlpidata,
SCIP_NLPIPROBLEM problem,
fint  ifail,
SCIP_Real  feastol,
SCIP_Real  opttol,
real x,
real lam 
)
static

◆ SCIP_DECL_NLPICOPY()

static SCIP_DECL_NLPICOPY ( nlpiCopyFilterSQP  )
static

copy method of NLP interface (called when SCIP copies plugins)

Definition at line 915 of file nlpi_filtersqp.c.

References SCIP_CALL, SCIP_OKAY, and SCIPincludeNlpSolverFilterSQP().

◆ SCIP_DECL_NLPIFREE()

static SCIP_DECL_NLPIFREE ( nlpiFreeFilterSQP  )
static

destructor of NLP interface to free nlpi data

Definition at line 924 of file nlpi_filtersqp.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeRandom().

◆ SCIP_DECL_NLPICREATEPROBLEM()

static SCIP_DECL_NLPICREATEPROBLEM ( nlpiCreateProblemFilterSQP  )
static

◆ SCIP_DECL_NLPIFREEPROBLEM()

static SCIP_DECL_NLPIFREEPROBLEM ( nlpiFreeProblemFilterSQP  )
static

free a problem instance

Definition at line 964 of file nlpi_filtersqp.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, and SCIPnlpiOracleFree().

◆ SCIP_DECL_NLPIADDVARS()

◆ SCIP_DECL_NLPIADDCONSTRAINTS()

◆ SCIP_DECL_NLPISETOBJECTIVE()

static SCIP_DECL_NLPISETOBJECTIVE ( nlpiSetObjectiveFilterSQP  )
static

sets or overwrites objective, a minimization problem is expected

Definition at line 1181 of file nlpi_filtersqp.c.

References invalidateSolution(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPnlpiOracleSetObjective().

◆ SCIP_DECL_NLPICHGVARBOUNDS()

static SCIP_DECL_NLPICHGVARBOUNDS ( nlpiChgVarBoundsFilterSQP  )
static

change variable bounds

Definition at line 1202 of file nlpi_filtersqp.c.

References invalidateSolution(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPnlpiOracleChgVarBounds().

◆ SCIP_DECL_NLPICHGCONSSIDES()

static SCIP_DECL_NLPICHGCONSSIDES ( nlpiChgConsSidesFilterSQP  )
static

change constraint bounds

Definition at line 1229 of file nlpi_filtersqp.c.

References invalidateSolution(), NULL, SCIP_CALL, SCIP_OKAY, SCIPnlpiOracleChgConsSides(), and SCIPnlpiOracleGetNVars().

◆ SCIP_DECL_NLPIDELVARSET()

static SCIP_DECL_NLPIDELVARSET ( nlpiDelVarSetFilterSQP  )
static

delete a set of variables

Definition at line 1259 of file nlpi_filtersqp.c.

References FALSE, invalidateSolution(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPnlpiOracleDelVarSet().

◆ SCIP_DECL_NLPIDELCONSSET()

static SCIP_DECL_NLPIDELCONSSET ( nlpiDelConstraintSetFilterSQP  )
static

delete a set of constraints

Definition at line 1289 of file nlpi_filtersqp.c.

References FALSE, invalidateSolution(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPnlpiOracleDelConsSet().

◆ SCIP_DECL_NLPICHGLINEARCOEFS()

static SCIP_DECL_NLPICHGLINEARCOEFS ( nlpiChgLinearCoefsFilterSQP  )
static

changes (or adds) linear coefficients in a constraint or objective

Definition at line 1316 of file nlpi_filtersqp.c.

References invalidateSolution(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPnlpiOracleChgLinearCoefs().

◆ SCIP_DECL_NLPICHGEXPR()

static SCIP_DECL_NLPICHGEXPR ( nlpiChgExprFilterSQP  )
static

replaces the expression of a constraint or objective

Definition at line 1340 of file nlpi_filtersqp.c.

References invalidateSolution(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPnlpiOracleChgExpr().

◆ SCIP_DECL_NLPICHGOBJCONSTANT()

static SCIP_DECL_NLPICHGOBJCONSTANT ( nlpiChgObjConstantFilterSQP  )
static

change the constant offset in the objective

Definition at line 1366 of file nlpi_filtersqp.c.

References invalidateSolution(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPnlpiOracleChgObjConstant().

◆ SCIP_DECL_NLPISETINITIALGUESS()

static SCIP_DECL_NLPISETINITIALGUESS ( nlpiSetInitialGuessFilterSQP  )
static

sets initial guess for primal variables

Definition at line 1381 of file nlpi_filtersqp.c.

References BMScopyMemoryArray, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, and SCIPnlpiOracleGetNVars().

◆ SCIP_DECL_NLPISOLVE()

◆ SCIP_DECL_NLPIGETSOLSTAT()

static SCIP_DECL_NLPIGETSOLSTAT ( nlpiGetSolstatFilterSQP  )
static

gives solution status

Definition at line 1708 of file nlpi_filtersqp.c.

References NULL.

◆ SCIP_DECL_NLPIGETTERMSTAT()

static SCIP_DECL_NLPIGETTERMSTAT ( nlpiGetTermstatFilterSQP  )
static

gives termination reason

Definition at line 1717 of file nlpi_filtersqp.c.

References NULL.

◆ SCIP_DECL_NLPIGETSOLUTION()

static SCIP_DECL_NLPIGETSOLUTION ( nlpiGetSolutionFilterSQP  )
static

gives primal and dual solution values

Definition at line 1726 of file nlpi_filtersqp.c.

References NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, and SCIPnlpiOracleEvalObjectiveValue().

◆ SCIP_DECL_NLPIGETSTATISTICS()

static SCIP_DECL_NLPIGETSTATISTICS ( nlpiGetStatisticsFilterSQP  )
static

gives solve statistics

Definition at line 1774 of file nlpi_filtersqp.c.

References NULL, SCIP_OKAY, and SCIPnlpiOracleGetEvalTime().

Variable Documentation

◆ phl

fint phl

Definition at line 227 of file nlpi_filtersqp.c.

◆ phr

fint phr

Definition at line 227 of file nlpi_filtersqp.c.

◆ phc

fint phc

Definition at line 227 of file nlpi_filtersqp.c.

◆ ubd

real ubd

Definition at line 234 of file nlpi_filtersqp.c.

◆ tt

real tt

Definition at line 234 of file nlpi_filtersqp.c.

◆ infty

real infty

Definition at line 240 of file nlpi_filtersqp.c.

◆ eps

◆ n_bqpd_calls

fint n_bqpd_calls

Definition at line 247 of file nlpi_filtersqp.c.

◆ n_bqpd_prfint

fint n_bqpd_prfint

Definition at line 247 of file nlpi_filtersqp.c.

◆ scale_mode

fint scale_mode

Definition at line 256 of file nlpi_filtersqp.c.

◆ phe

fint phe

Definition at line 256 of file nlpi_filtersqp.c.