Katana.jl Library

See the User Manual for an explanation of the motivation behind this class.

An implementation of AbstractKatanaSeparator for any first-order cutting algorithm.

A solver for convex NLPs that uses cutting-planes to approximate a convex feasible set.

KatanaSolver(lp_solver :: MathProgBase.AbstractMathProgSolver;
             separator = KatanaFirstOrderSeparator(),
             features = Vector{Symbol}(),
             f_tol :: Float64 = 1e-6,
             cut_coef_rng :: Float64 = 1e9,
             log_level :: Int = 10,
             iter_cap :: Int = 10000,
             obj_eps :: Float64 = -1.0)

Construct a KatanaSolver with feasibility tolerance f_tol, a maximum coefficient range per cut cut_coef_rng and an iteration cap specifying the maximum number of rounds of LP solves + cut generation in iter_cap. Print out solver progress every log_level number of iterations, or suppress output with log_level=0. Use obj_eps as a stopping criterion: when the objective function evaluated by the LP has changed by less than obj_eps relative to the previous iteration.

cut_coef_rng is used to round-off close-to-zero coefficients in generated cuts.

The separator is any implementing subtype of AbstractKatanaSeparator. It serves as the separation oracle used by the solver. The default is a first order separator that generates a single Newton cut per constraint.

The features vector is a list of optional features to enable in the solver. Currently supported are

• :VisData $-$ Internal model logs actions to be exported and visualised

getKatanaCuts(m :: KatanaNonlinearModel)

Returns a table of all linear cutting planes generated by Katana's separation oracle. If the model contains N variables (including an auxiliary variable) and m cutting planes were generated, the table will have size m x (N+2).

For every row: the first N columns represent the coefficients of model variables, the N+1th column a constant term, and the N+2th column an inequality direction (-1 for $\leq$ and 1 for $\geq$). Thus, for coefficients $a_1,\ldots,a_N$, constant $c$ and direction $-1$, re-construct the cutting plane as $a_{1}x_{1} + \ldots + a_{N}x_{N} \leq c$.

initialize!(sep::AbstractKatanaSeparator, linear_model, num_var, num_constr, oracle::MathProgBase.AbstractNLPEvaluator)

Initialise an instance of a subtype of AbstractKatanaSeparator with information about the KatanaNonlinearModel. This method is called by loadproblem! and MUST be overridden.

linear_model is the internal linear model of the KatanaNonlinearModel.

num_var is the number of solution variables, as passed by Katana. num_constr is the number of constraints in the problem, as passed by Katana. See solver implementation for details.

oracle can be queried for first- and second- derivative information and must be initialised in this method (see MathProgBase documentation on nonlinear models).

precompute!(sep::AbstractKatanaSeparator, xstar)

Implement this method for a subtype of AbstractKatanaSeparator if your separator might only need to evaluate certain information once for all constraints using a solution from the internal LP model.

xstar is the solution vector from the KatanaNonlinearModel's LP model

Wrapper for any MathProgBase.AbstractNLPEvaluator instance. Acts as an NLP evaluator for an NLP that has been transformed into epigraph form by treating the NL objective as if it were a constraint.

The MathProgBase non-linear model for Katana.

gencut!(sep::AbstractKatanaSeparator, xstar, i)

Generate a cut given an LP solution xstar for constraint i. bounds is a 2-tuple of (lb,ub). Since constraints are convex, one of the tuple bounds will be finite, and defines the level set of the constraint function. This method MUST be overridden for a subtype of AbstractKatanaSeparator. It is called by Katana as part of the solve routine.

Return a JuMP.AffExpr object.

isconstrsat(sep::AbstractKatanaSeparator, i, lb, ub, f_tol)

Returns true if the $i$th constraint is satisfied for the given bounds and tolerance. This method MUST be overriden for a subtype of AbstractKatanaSeparator as querying evaluated constraints is implementation-dependent.

numcuts(m::KatanaNonlinearModel)

Returns the number of linear cuts added to the model. Includes linear constraints initially present.

numiters(m::KatanaNonlinearModel)

Returns the number of iterations taken by the model.