Skip to content

About

Umbrella project that can be used to fetch and build all the SMS++ modules at once. | mirror of https://gitlab.com/smspp/smspp-project

Resources

Contributing

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

3,434 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

The SMS++ Project

Pipeline Release Doxygen Sphinx Manual C++ Standard License: LGPL v3 Platforms

To boldly model (and solve) what no one has modeled (and solved) before

This is the splash page of the SMS++ Project, an "umbrella project" meant to provide a quick way to download and install all the projects related to the SMS++ framework. It also allows to produce a unified documentation and to track issues that involve all the modules or the project in general.

SMS++ is a set of C++ classes intended to provide a system for modeling complex, block-structured mathematical models (in particular, but not exclusively, single-real-objective optimization problems), and solving them via sophisticated, structure-exploiting algorithms (in particular, but not exclusively, decomposition approaches and structured Interior-Point methods).

At any given time, this project will point to the latest releases of all the submodules.

Note: If you are looking for the SMS++ core library, you will find it here.

Success stories

The SMS++ framework is written in advanced C++, and its use entails climbing a significant learning curve. Yet, mastering it may be worth especially for the solution of very-large-scale, demanding optimization problems arising in applications. Indeed, the SMS++ Project has already been instrumental in several complex projects, such as:

Watch this space for more details and news as they become available.

Documentation

  • The SMS++ API reference contains the documentation for the classes and methods of the SMS++ core library and all its modules.

  • The SMS++ Project Wiki contains detailed installation instructions, troubleshooting information and additional guides for developers and maintainers.

User Manual

A complete user manual for SMS++ lives in manual/, in two forms:

Both forms are generated from the same Markdown sources in manual/chapters.

Current projects

  • SMS++ core library, the repository defining the general SMS++ framework features.

  • BinaryKnapsackBlock, a Block implementing the (Mixed) Binary Knapsack Problem, together with a family of Solver for it: the full-table Dynamic Programming one, an exact core one in the MINKNAP / COMBO / RECORD line that is orders of magnitude faster, those handing the core to the external COMBO and RECORD solvers, and the greedy one for the continuous relaxation; all of them can reuse the previous solution after a change of the data.

  • BendersDecompositionSolver, a "generic" Benders-based Solver for Block with appropriate structure, that keeps the complicating (first-stage) Variable in a master problem and projects out each sub-Block into its value function, represented by a BendersBFunction producing the Benders cuts; the master can be solved either as a convex problem by a bundle-type Solver or as a MILP with the cuts added as lazy constraints.

  • BranchAndXSolver, a Solver implementing a Relaxation-Agnostic Branch-and-X (RABaX) approach, i.e., a generic enumerative Solver where "X" stands for Bound / Cut / Price. It supports depth-first, breadth-first and best-first exploration, cut separation, reoptimization of the enumeration tree and parallel exploration, building on the ChangeSolver and RelaxationSolver abstractions in the SMS++ core.

  • CapacitatedFacilityLocationBlock, an implementation of the Block concept for a "pretty basic version" the Capacitated Facility Location (CFL) problem, a.k.a. the Capacitated Warehouse Location (CWL) problem, primarily intended as a "didactic" implementation for showing some of the features of SMS++. However, it can also play, at run time, the role of the sub-problem of the scenario reduction techniques (see below), which build it through the SMS++ factory and therefore do not require this module at build time.

  • BundleSolver, a Solver for the minimization of a sum of convex nondifferentiable functions known through an oracle (e.g., the Lagrangian dual of a Block, or the master of a Benders' decomposition) by the "generalized bundle" method. Its master problem is a MasterProblemBlock, solved by any :MILPSolver, with the proximal, level, doubly stabilized or trust-region stabilization; the components can enter it as cutting-plane models or, when they are "easy", with their exact description. ParallelBundleSolver evaluates the components in parallel, and BundleSolverML predicts the proximal parameter with a neural network.

  • BDMinQuadSolver, a Solver for the primal MasterProblemBlock of the bundle methods, which solves it with BDMinQuad, an active-set method for the disaggregated master problem with a box on the variables, a lower bound on each component and a level, which updates the factorization of the active set as the items enter and leave the bundle. It handles the proximal and the doubly stabilized master.

  • SubGradSolver, a Solver for the same problems as BundleSolver by the deflected and projected subgradient methods, whose stepsize and deflection rules (Polyak, ColorTV, FumeroTV, Volume and the primal-dual one) are chosen by name in its configuration; as the inner Solver of LagrangianDualSolver, it also recovers primal solutions from the convex combinations of the subgradients.

  • InvestmentBlock, a Block designed to model the investment in different assets defined in UCBlock. The corresponding problem can be either deterministic or stochastic, in which case the module also uses SDDPBlock and therefore StochasticBlock.

  • LagrangianDualSolver, a "generic" Lagrangian-based Solver for Block with appropriate structure, also used to provide an implementation of the Primal Proximal Heuristic Lagrangian-based math-heuristic.

  • FrankWolfeSolver, a Solver implementing Frank-Wolfe (conditional gradient) algorithms (ported from the Julia package FrankWolfe.jl) for problems whose feasible region is the product of the convex hulls of a number of sub-Block, each acting as a Linear Minimization Oracle; it can also solve the corresponding Dantzig-Wolfe relaxation.

  • LukFiBlock, a simple Block defining several test functions from the literature for NonDifferentiable Optimization solvers (such as BundleSolver).

  • MCFBlock, defining the MCFBlock class for the (continuous, linear) Min-Cost Flow problem.

  • MCFClassSolver, defining MCFSolver, a Solver for MCFBlock that is basically a wrapper for solvers from the MCFClass project.

  • MCFLemonSolver, a Solver for MCFBlock based on interfacing the min-cost flow algorithms of abLEMON 1.9.0 or later, the maintained fork of the LEMON project. It is not a single solver but a whole family of Solver variants, obtained by instantiating its NetworkSimplex, CostScaling, CycleCanceling and CapacityScaling algorithms on different graph types and on different (int, long, double) cost/capacity numeric types.

  • MILPSolver, defining the general MILPSolver Solver that aims at being able to solve any Block whose abstract representation encodes for a Mixed-Integer Quadratically-Constrained Quadratic Program (ColVariable, OneVarConstraint, FRowConstraint and FRealObjective with LinearFunction, DQuadFunction or QuadFunction inside), together with derived classes that actually interface with existing solvers; not all of them handle all the quadratic cases, in particular the non-convex ones. Currently, available derived classes are:

    • CPXMILPSolver, providing the interface with the commercial IBM ILOG CPLEX Studio

    • SCIPMILPSolver, providing the interface with the open-source SCIP (note that since version 8.0.3 SCIP is "truly" FOSS by dint of being distributed under the Apache 2.0 License as opposed to the previous academic license preventing royalty-free commercial use)

    • GRBMILPSolver, providing the interface with the commercial GUROBI Optimizer

    • MOSEKMILPSolver, providing the interface with the commercial MOSEK Optimizer (version 11.0.1 or later), which needs a license of its own, free for academic use (academic licenses); it is built when CMake finds MOSEK (MILPSolver_USE_MOSEK, with MOSEK_ROOT as hint)

    • HiGHSMILPSolver, providing the interface with the open-source HiGHS

    • PIPSMILPSolver, providing the interface with the open-source parallel interior-point solver PIPS-IPM++ (LP problems only, currently supported on Linux only)

    • DAQPMILPSolver, providing the interface with the open-source dual active-set solver DAQP (convex QP and LP problems with linear constraints, dense, no integer variables)

    • QPOASESMILPSolver, providing the interface with the open-source online active-set solver qpOASES (convex QP and LP problems with linear constraints, dense, no integer variables, the Hessian possibly singular, hot starts between similar problems)

    • ClarabelMILPSolver, providing the interface with the open-source interior-point solver Clarabel (convex QP and LP problems with linear constraints, sparse, no integer variables), whose C interface INSTALL.sh builds with the Rust toolchain (cargo)

    • ProxQPMILPSolver, providing the interface with the open-source proximal augmented Lagrangian solver ProxQP of ProxSuite (convex QP and LP problems with linear constraints, dense or sparse, no integer variables)

    • PIQPMILPSolver, providing the interface with the open-source proximal interior point solver PIQP (convex QP and LP problems with linear constraints, dense or sparse, no integer variables)

    • OSQPMILPSolver, providing the interface with the open-source operator splitting solver OSQP (convex QP and LP problems with linear constraints, sparse, no integer variables)

    • QPMADMILPSolver, providing the interface with the open-source dual active-set solver qpmad, of Goldfarb and Idnani (strictly convex QP problems with linear constraints, dense, the Hessian positive definite, no integer variables)

    • QuadProgMILPSolver, providing the interface with the open-source dual active-set solver quadprog, the original implementation of the method of Goldfarb and Idnani (same problems as QPMADMILPSolver); quadprog is under the GPL, hence a MILPSolver built with it is too, and it is in no package

    • HPIPMMILPSolver, providing the interface with the open-source interior-point solver HPIPM, built on the linear algebra of BLASFEO for the small and dense problems of Model Predictive Control (convex QP and LP problems with linear constraints, dense, no integer variables); it is in no package

    • PERMONMILPSolver, providing the interface with PermonQP, the solvers of PERMON on PETSc for large sparse convex QPs, e.g., the duals of Support Vector Machines (convex QP problems with linear constraints whose Hessian is positive definite on the equalities, sparse, no integer variables); PETSc is large, hence INSTALL.sh installs them only if asked (--with-permon), and they are in no package

  • MMCFBlock, defining the MMCFBlock for representing Multicommodity Min-Cost Flow problems (MMCF). The current version is rather crude and in desperate need of some love.

  • ScenarioReductionSolver, defining Solver classes for the discrete scenario reduction problem: given the finite set of scenarios carried by a ScenarioReductionBlock (through its DiscreteScenarioSet), they select a smaller representative subset that stays close to the full distribution in the (weighted) Wasserstein sense. It provides ScenarioReductionSolver, with four heuristics (Baseline, Dupacova forward selection, BestFit and FirstFit local searches), and CSSCScenarioReductionSolver, implementing Cost-Space Scenario Clustering.

  • SDDPBlock, defining the SDDPBlock for multi-stage stochastic optimization problems solvable by the Stochastic Dual Dynamic Programming approach, the SDDPSolver that interfaces with the SDDP solver in the StOpt project, and the SDDPGreedySolver that solves the stages of one scenario one after the other, each with the approximation of the future cost the SDDPBlock holds, giving feasible solutions that evaluate (and bound from above) the decisions of SDDPSolver.

  • StochasticBlock, defining the StochasticBlock "meta-Block" that takes any "deterministic" Block and "makes it stochastic" by allowing to change some of its data in a very general and abstract way (using the SMS++ "methods factory"). It also defines a ScenarioGenerator module that provides a general interface for generating scenario data (in the form that StochasticBlock uses) and its DiscreteScenarioSet implementation for the special case of discrete distributions (finite sets of scenarios). The latter also implements a general support for scenario reduction techniques, whose sub-problem is built through the SMS++ factory, so that a CapacitatedFacilityLocationBlock (and the Solvers therein) can serve as such without the module being required to build this one.

  • tests, defining (complex) testers for several components of the project that require elements (Block and/or Solver) from different subprojects and that therefore are better not included in any specific subproject.

  • tools, defining some tools that can be useful for users (such as "main files" that take instances of problems and solve them) and that require elements (Block and/or Solver) from different subprojects so that they are better not included in any specific subproject.

  • TwoStageStochasticBlock, a :Block that represents a two-stage stochastic programming problem contained in its inner Block. It currently supports the "Lagrangian version" of the formulation by building the explicit form of the two-stage stochastic problem by with N copies of the inner deterministic Block (one per scenario) and adding non-anticipativity constraints to ensure first-stage variables are the same across all scenarios, but it will eventually be extended to the "Benders' version".

  • MultiStageStochasticBlock, a :Block that represents a multi-stage stochastic programming problem as an aggregation of TwoStageStochasticBlock, holding one of them per outer-stage scenario and tying the first-stage here-and-now variables across them with an outer layer of non-anticipativity constraints.

  • SVMBlock, defining the Block for the training problem of a Support Vector Machine, both the classifier and the regressor, together with the ad hoc SMOSolver and with LIBSVMSolver and LIBLINEARSolver, which hand the problem over to LIBSVM and to LIBLINEAR. The abstract representation encodes either the training problem itself or its Wolfe dual, and the samples can be dealt out to chunks tied by consensus constraints, which is the structure a Lagrangian, or equivalently a Dantzig-Wolfe, decomposition attacks.

  • SATBlock, defining the Block for the satisfiability problems of the propositional logic and for their weighted partial MaxSAT version, whose abstract representation is the MILP formulation, so that the :MILPSolver and the decompositions of SMS++ work on it as they are, together with SATSolver, the base of the Solver that hand the clauses to a SAT solver (CaDiCaLSATSolver for CaDiCaL and MiniSATSolver for MiniSat), which also solves the weighted MaxSAT by the core-guided algorithm OLL.

  • SatellitesBlock, defining the Block for the Satellite Constellation Design Problem, i.e., choosing the orbits of a constellation of satellites so as to minimize either their number or the sum over the targets of the maximum revisit times: SatelliteBlock, SingleTargetBlock, MultiTargetBlock and the ConstellationBlock that aggregates them for the continuous version of the problem, DiscreteSatelliteBlock and DiscreteConstellationBlock for the version where the observability threshold of each satellite takes one of finitely many levels, together with the heuristics SatelliteSolver and DiscreteSatelliteSolver.

  • MultiKnapsackAssignBlock, defining the Block for the Multiple Knapsack Assignment Problem, i.e., placing items partitioned into classes in knapsacks, each of which is given at most one class and holds items of that class within its capacity, so as to maximize the total profit: its sub-Block are the BinaryKnapsackBlock of the pairs of a knapsack and a class, linked by the constraints that assign each item to at most one knapsack and each knapsack at most one class.

  • HQPBlock, defining the Block for hierarchical (lexicographic) quadratic programs, i.e., a sequence of levels each of which minimizes the violation of its tasks, equalities and inequalities, while keeping those of the levels above at their optimum, as in the hierarchical Model Predictive Control of robots: HQPBlock writes them as one model in the original variables, which goes from a level to the next one, and from a step of the control to the next one, by Modification, so that an active-set :MILPSolver restarts from the previous solution, and HQPSolver solves its levels one after the other with an inner Solver taken from a BlockSolverConfig.

  • SingleFlowDCRBlock, defining the Block for Delay-Constrained Routing problems, i.e., routing flows on a network at minimum cost so that the worst-case end-to-end delay of each of them, as given by a network-calculus formula, meets its deadline: SingleFlowDCRBlock for one flow, MultiFlowDCRBlock for several of them sharing the arc capacities, together with the SingleFlowDCRBendersSolver that solves the single-flow problem by a Benders scheme with a nested Lagrangian relaxation.

  • UCBlock, defining several Block for Unit Commitment problems: the general UCBlock "root" class, several Block for specific generating units (UnitBlock) and interconnect networks (NetworkBlock), with some specialized Solver.

  • pySMSpp, the Python interface of SMS++, which builds the netCDF files of SMS++ models, runs the SMS++ tools on them and reads their results back.

  • pypsa2smspp, which translates a PyPSA energy-system network into the corresponding SMS++ model (a UCBlock, possibly within an InvestmentBlock for capacity expansion, or within a TwoStageStochasticBlock or a MultiStageStochasticBlock for its stochastic versions), solves it through pySMSpp, which it requires, and maps the solution back onto the network.

    Both are Python packages (pip install pysmspp pypsa2smspp) that CMake does not build, and their submodules are only initialized on request, e.g., git submodule update --init pySMSpp pypsa2smspp.

Getting started

The installation guide of the wiki describes every way of installing SMS++: the ready-made packages (the PPA of the project for Ubuntu, conda-forge, the Homebrew tap and the vcpkg registry of SMS++, and the recipes of the AUR, Conan, Spack, Nix, MSYS2 and xmake), the INSTALL.sh and INSTALL.ps1 scripts, which install the dependencies and build SMS++ in one go, and the build of the sources by CMake, inside a CMake project and by the makefiles, on Linux, macOS and Windows. The options of the build, and the location of the external libraries, are in Customize the Configuration, and the CMakeLists.txt of the umbrella is a quick reference on the requirements of each module and on the dependencies among the modules.

First steps

Besides the User Manual, the tests repository can be useful to get a first look at possible ways of using SMS++. In particular the three tests LagrangianDualSolver_Box (in tests/SMS++/AbstractBlock), MMCFBlock and UCBlock all build, or load from file, a :Block amenable to Lagrangian relaxation, register the Solver (such as a :MILPSolver and a LagrangianDualSolver) to it, properly configure them if needed (mostly, but not exclusively, using Configuration files) and run them to verify that they give the same answer. The LagrangianDualSolver_Box test also shows how one can use SMS++ to build "normal" models a-la algebraic modelling language using AbstractBlock, as opposed to programming a whole Block from scratch, more of which can be found, e.g., in tests/SMS++/LagBFunction and tests/SMS++/PolyhedralFunction. Furthermore, provides an example on how to (randomly) modify the :Block and re-solve it many times (still checking that the results agree), showcasing the crucial Modification SMS++ concept whereby changes in the :Block are automatically forwarded to all concerned Solver. Other similar examples can be found in basically all the other tests.

The MMCFBlock and UCBlock versions rather provides examples about using full-featured "pre-built" :Block, each of which is "structured" and therefore has sub-Block inside of possibly different types that can possibly be solved by specialised :Solver; c.f., e.g., the MMCFBlock, MCFBlock and the UCBlock repo, respectively.

Getting help

If you need support, you want to submit bugs or propose a new feature for an individual module, see the Getting help section for that module.

If you need support on the project installation, you can check out the installation guide or the troubleshooting page in our Wiki.

If your issue is not covered by our guides, or you want to propose a new module, you can open a new issue.

Contributing

Please read CONTRIBUTING.md for details on our code of conduct, and the process for submitting merge requests to us. To contribute to the individual projects, see the Contribute section for those. The code and the configurations follow a style that the pipeline of every merge request checks, and scripts/smspp-format applies with the formatters of the submodule scripts/code-style (see CONTRIBUTING.md and the page Code style of the wiki, which also says how to install the hook of git that checks a commit of SMS++ before it is made).

Contributing entirely new subprojects, i.e., either new :Block for your favourite class of optimization models and/or new :Solver implementing your favourite solution method (very general or specialised to a very narrow class, everything is useful) is extremely welcome. The SMS++ Project maintainers will bend backwards to help you develop them and will be happy to host them in the umbrella repository and integrate them with the rest of the SMS++ Project. This being open source, of course it is your choice whether you do it, if you will release your code and which license will it be released under. However, SMS++ is a community project, and we humbly suggest you to consider participating in it with the rules we have been setting.

The easiest way to start a new module is the ModuleTemplate repository (in the private smspp-develop group of the SMS++ developers), a ready-to-use skeleton of a SMS++ module in the standard layout (CMake and makefiles builds, GitLab and GitHub CI, a factory-registered stub class, a smoke test wired into CTest, and all the standard boilerplate). Its init.sh script renames everything after your module, wires the declared dependencies and registers the module as a submodule of the umbrella project, so that you only have to put your classes in include/ and src/; see its README for the details.

Constructive criticisms and proposals about changing these rules (the umbrella repository organisation and whatnot) are very welcome. In fact, we believe that the SMS++ Project underlines the need for a software distribution mechanism for projects that are at the same time tightly-knit together and composed of largely independent units that we don't seem to see around, but if we have missed it we'd be happy for a tip.

Authors

These authors are for the umbrella project alone. Check the individual projects for their respective authors.

Current Lead authors

  • Antonio Frangioni
    Dipartimento di Informatica
    Università di Pisa

  • Donato Meoli
    Dipartimento di Informatica
    Università di Pisa

Main past contributors

  • Niccolò Iardella
    Dipartimento di Informatica
    Università di Pisa

  • Rafael Durbano Lobato
    Dipartimento di Informatica
    Università di Pisa

License

This code is provided free of charge under the GNU Lesser General Public License version 3.0 - see the LICENSE file for details.

Disclaimer

The code is currently provided free of charge under an open-source license. As such, it is provided "as is", without any explicit or implicit warranty that it will properly behave, or it will suit your needs. The Authors of the code cannot be considered liable, either directly or indirectly, for any damage or loss that anybody could suffer for having used it. More details about the non-warranty attached to this code are available in the license description file.

Acknowledgements

The development of SMS++ has greatly benefited from the contributions of the following projects:

About

Umbrella project that can be used to fetch and build all the SMS++ modules at once. | mirror of https://gitlab.com/smspp/smspp-project

Resources

Contributing

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages