Reusable components and solver driver API

This section highlights the major library components, ranging from basic building blocks necessary for any AMPL driver, to more advanced utilities. The choice of API for a driver may depend on Solver driver setups.

NL and SOL files

Any AMPL solver driver currenlty needs to input an NL file and report results in a SOL file. AMPL might add in-memory model communication for efficiency, which would be provided via the recommended driver setup. However, a minimal driver setup might address the corresponding APIs directly, as described below.

NL file reader

MP provides a high-performance nl file reader which is up to 6x faster than the one provided by the traditional AMPL Solver Library (ASL).

This section describes the C++ API of an NL reader which is

  • Reusable: the reader can be used to process NL files in different ways and not limited to a single problem representation

  • High performance: fast mmap-based reader with SAX-like API and no dynamic memory allocations in the common case

  • Easy to use: clean, modern code base and simple API

  • Complete: supports all NL constructs including extensions implemented in AMPL Solver Library

  • Reliable: extensively and continuously tested on a variety of platforms

NL format

NL is a format for representing optimization problems in discrete or continuous variables. The format provides linear constraints, as well as non-linear expression trees. It is described in the technical report Writing .nl Files.

The NL format supports a wide range of problem types including but not limited to the following areas of optimization:

Easy-to-use functions

The mp/nl.h header only contains declarations of mp::ReadNLFile() and mp::ReadNLString(), and can be used to read the standard optimization problem object of class mp::Problem, for example:

#include "mp/nl.h"
#include "mp/problem.h"

mp::Problem p;
ReadNLFile("diet.nl", p);

Full NL-reader API

If you want to provide a custom NL handler, include mp/nl-reader.h instead. Class mp::NLHandler can be customized for most efficient translation of NL format into solver API using the ProblemBuilder concept.

Note that mp/nl.h is a much smaller header than mp/nl-reader.h so prefer it unless you need access to the full NL reader API, described below.

SOL file writer

Writing solution/results output is easiest as part of the general workflow, see Model manager.

A standalone .sol file writer could be implemented by parameterizing the mp::internal::AppSolutionHandlerImpl (or mp::internal::SolutionWriterImpl) templates by minimal implementations of the mp::BasicSolver and mp::ProblemBuilder interfaces.

Model/solution I/O and reformulations

The tools presented in this section standardize model/solution I/O (currently relying on NL file input and SOL file output) and conversion for a particular solver.

Overview

While the components can be theoretically used in isolation, for example just the Model manager, in the Recommended setup the model handling is implemented according to the following scheme:

Model manager –>

Problem builder –> Problem converter / flattener –> Flat Converter –> Flat model API –> Solver.

To give an example, consider the following model:

var x >=0, <=7;
var y >=0, <=4, integer;

s.t. Con01: x + log(y) <= 5;
s.t. Con02: numberof 2 in (x, y) <= 1;

The nonlinear expressions log and numberof are received from AMPL in expression trees which are input from an NL file by a problem builder. At the next step, problem flattener replaces nonlinear expressions by auxiliary variables:

var t1 = log(y);
var t2 = numberof 2 in (x, y);

s.t. Con01_: x + t1 <= 5;
s.t. Con02_: t2 <= 1;

Then, the defining constraints of t1 and t2 are either passed to the solver which accepts them via the model API, or become reformulated into more simple entities by Flat Converter. If the solver natively accepts a nonlinear constraint, it is possible to still apply automatic reformulation via a solver option, for example acc:log for logarithm. Run the driver with -= or -c for a list of natively accepted constraints and options.

An in-depth treatment of some automatic reformulations is given in [CLModernArch], [SOCTransform], [MOI], and [CP2MIP]. Customization for a new solver driver is sketched in Configure automatic model reformulations.

CP2MIP

G. Belov, P. J. Stuckey, G. Tack, M. Wallace. Improved Linearization of Constraint Programming Models. In: Rueher, M. (eds) Principles and Practice of Constraint Programming. CP 2016. LNCS, vol 9892. Springer, Cham. https://doi.org/10.1007/978-3-319-44953-1_4.

CLModernArch

J. J. Dekker. A Modern Architecture for Constraint Modelling Languages. PhD thesis. Monash University, 2021.

SOCTransform

R. Fourer and J. Erickson. Detection and Transformation of Second-Order Cone Programming Problems in a General-Purpose Algebraic Modeling Language. Optimization Online, 2019.

MOI

B. Legat, O. Dowson, J. D. Garcia, M. Lubin. MathOptInterface: A Data Structure for Mathematical Optimization Problems. INFORMS Journal on Computing 34 (2), 2021. https://doi.org/10.1287/ijoc.2021.1067.

Model manager

Class mp::BasicModelManager standardizes the interface for model input and results output. This interface is used by the Backend classes.

Problem builders

Basic Model/solution I/O and model managers rely on a mp::ProblemBuilder concept.

mp::Problem converters

Given a problem instance in the standard format mp::Problem, several tools can be adapted to convert the instance for a particular solver.

Flat model converters

mp::FlatConverter and mp::MIPFlatConverter represent and convert flat models (i.e., models without expression trees). Typically, a flat model is produced from an NL model by Problem Flattener. As a next step, constraints which are not natively accepted by a solver, are transformed into simpler forms. This behavior can be flexibly parameterized for a particular solver, preferably via the solver’s modeling API wrapper:

Flat model API

mp::BasicFlatModelAPI is the interface via which Flat model converters address the underlying solver.

Constraint acceptance

A subclassed wrapper, such as mp::GurobiModelAPI, signals its accepted constraints and which model reformulations are preferable. For example, GurobiModelAPI declares the following in order to natively receive the logical OR constraint:

ACCEPT_CONSTRAINT(OrConstraint,
  Recommended,                       // Driver recommends native form
  CG_General)                        // Constraint group for suffix exchange
void AddConstraint(const OrConstraint& );

By default, if the driver does not mark a constraint as acceptable, mp::FlatConverter and its descendants attempt to simplify it. See Configure automatic model reformulations for further details.

Model query API

To obtain a summary information on the flat model, for example the number of constraints of a particular type or group, use the helper object of type mp::FlatModelInfo obtainable by mp::BasicFlatModelAPI::GetFlatModelInfo().

To preallocate memory for a class of constraints, the implementation can redefine method mp::BasicFlatModelAPI::InitProblemModificationPhase():

void MosekModelAPI::InitProblemModificationPhase(const FlatModelInfo* info) {
  /// Preallocate linear and quadratic constraints.
  /// CG_Linear, CG_Quadratic, etc. are the constraint group indexes
  /// provided in ACCEPT_CONSTRAINT macros.
  MOSEK_CCALL(MSK_appendcons(lp(),
                         info->GetNumberOfConstraintsOfGroup(CG_Linear) +
                         info->GetNumberOfConstraintsOfGroup(CG_Quadratic)));
}

Value presolver

Class mp::pre::ValuePresolver manages transformations of solutions and suffixes between the original NL model and the converted model. For driver architectures with Model manager, the value presolver object must be shared between the model converter and the Backend to enable solution/suffix transformations corresponding to those on the model, see mp::CreateGurobiModelMgr as an example.

Invocation API

To use the ValuePresolver API, the following classes are needed:

  • mp::pre::BasicValuePresolver defines an interface for mp::pre::ValuePresolver.

  • mp::pre::ValueNode temporarily stores values corresponding to a single type of model item (variables, constraints, objectives).

  • mp::pre::ValueMap is a map of node values, where the key usually corresponds to an item subcategory. For example, Gurobi distinguishes attributes for the following constraint categories: linear, quadratic, SOS, general. Thus, the reformulation graph needs to have these four types of target nodes for constraint values:

    pre::ValueMapInt GurobiBackend::ConsIIS() {
  ......
  return {{{ CG_Linear, iis_lincon },
    { CG_Quadratic, iis_qc },
    { CG_SOS, iis_soscon },
    { CG_General, iis_gencon }}};
}

  • mp::pre::ModelValues is a class joining value maps for variables, constraints, and objectives. It is useful when the conversions connect items of different types: for example, when converting an algebraic range constraint to an equality constraint with a bounded slack variable, the constraint’s basis status is mapped to that of the slack. Similarly, the range constraint should be reported infeasible if either the slack’s bounds or the equality are:

    IIS GurobiBackend::GetIIS() {
  pre::ModelValuesInt mv = GetValuePresolver().
    PostsolveIIS( pre::ModelValuesInt{ VarsIIS(), ConsIIS() } );
  return { mv.GetVarValues()(), mv.GetConValues()() };
}

Implementation API

To implement value pre- / postsolving, the following API is used:

Reformulation graph

The flattening and reformulation graph can be exported by the cvt:writegraph option (WIP).

At the moment only arcs are exported. Terminal nodes (variables, constraints, objectives) can be seen in the NL model (ampl: expand) and the final flat model (gurobi: option writeprob).

C++ ASL adapter

An efficient type-safe C++ adapter for the traditional ASL library for connecting solvers to AMPL and other systems. ASL has many additional functions, such as writing NL files and automatic differentiation.

More details

This section overviews some more details of the API.

For a complete API reference, see the index.

Problem representation

A standard representation of a model, convenient for intermediate storage.

Expression forest walkers

Typesafe expression walkers for models stored in memory.

Solution status

Suffixes

previous

HOWTO hook your solver to AMPL MP

next

Testing