The SMS++ Project

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:

• The plan4res H2020 project that funded the first major expansion of SMS++ capabilities.

• The openENTRANCE H2020 project, where SMS++ contributed to the open modelling platform developed by the project.

• The OpenMod4Africa project, in which SMS++ has been one of the main modelling tools for solving complex electricity system optimization and simulation problems in Africa, training many researchers, modellers and stakeholders from both western and eastern Africa on how to use the tools to develop case studies at the level of the two regions.

• The CETPartnership "RESILIENT - Resilient Energy System Infrastructure Layouts for Industry, E-fuels and Network Transition", where SMS++ is being interfaced with the open-source, widely-used, multi-vector energy planning tool PyPSA-Eur to provide solution methods for the more demanding energy models

Furthermore, the use of SMS++ is planned for several other projects; a recently accepted one is

• The CETPartnership "Manoeuvre", where a methodology will be developed for linking SMS++ with the global energy model GENeSYS-Mod to conduct case studies, where SMS++ will be run on a technologies mix calculated by GENeSYS-Mod and will send back some indicators that will allow to refine the previous solution.

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:

• PDF - single, print-ready file: SMS++ - A User Manual (PDF)

• Web: https://smspp.gitlab.io/smspp-project/manual/

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 Binary Knapsack Problem and the corresponding Solver based on a straightforward implementation of the Dynamic Programming approach (for integer weights).

• 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 is also used as the support for scenario reduction techniques in StochasticBlock (see below).

• BundleSolver, a Solver for optimization problems involving (several) nondifferentiable objective function(s) based on the (generalized) "bundle method". It currently uses some modules from the NDOSolver / FiOracle project, although the dependency will be hopefully removed in time.

• 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 from the LEMON project. It is not a single solver but a whole family of Solver variants, obtained by instantiating LEMON's 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 Linear Program (ColVariable, FRowConstraint and FRealObjective with LinearFunction inside, OneVarConstraint), together with derived classes that actually interface with existing MILP solvers. 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

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

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

• SDDPBlock, defining the SDDPBlock for multi-stage stochastic optimization problems solvable by the Stochastic Dual Dynamic Programming approach, and the SDDPSolver that interfaces with the SDDP solver in the StOpt project.

• 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 via integration with the CapacitatedFacilityLocationBlock (and solvers therein).

• 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".

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

Getting started

These instructions will let you build the projects on your local machine.

Requirements

If you are new to SMS++ and you are looking for a zero-waste way to install all dependencies in the default locations, we suggest using the ad-hoc INSTALL files.

If you have not yet cloned the SMS++ repository, you can launch the script directly:

# Windows (from a PowerShell as administrator)
Set-ExecutionPolicy -Scope Process -ExecutionPolicy Bypass -Force
& ([scriptblock]::Create((New-Object System.Net.WebClient).DownloadString('https://gitlab.com/smspp/smspp-project/-/raw/develop/INSTALL.ps1')))

or:

# Linux
# using curl
curl -s https://gitlab.com/smspp/smspp-project/-/raw/develop/INSTALL.sh | sudo bash -s -- --install-root=<your-custom-path>
# using  wget
wget -qO- https://gitlab.com/smspp/smspp-project/-/raw/develop/INSTALL.sh | sudo bash -s -- --install-root=<your-custom-path>

# macOS
# using curl
curl -s https://gitlab.com/smspp/smspp-project/-/raw/develop/INSTALL.sh | bash -s -- --install-root=<your-custom-path>
# using  wget
wget -qO- https://gitlab.com/smspp/smspp-project/-/raw/develop/INSTALL.sh | bash -s -- --install-root=<your-custom-path>

The sudo option in the Linux script assumes that the current user is a sudoer, in which case the default installation root path is /opt. If the user is not a sudoer, sudo should not be added and the default installation root path is $HOME. For macOS, sudo should never be used and the default installation root path is /Library.

If you do not want to install some SMS++ dependency, you can run:

# Windows (from a PowerShell as administrator)
Set-ExecutionPolicy -Scope Process -ExecutionPolicy Bypass -Force
& ([scriptblock]::Create((New-Object System.Net.WebClient).DownloadString('https://gitlab.com/smspp/smspp-project/-/raw/develop/INSTALL.ps1'))) -without<some-dependency>

or:

# Linux
# using curl
curl -s https://gitlab.com/smspp/smspp-project/-/raw/develop/INSTALL.sh | sudo bash -s -- --install-root=<your-custom-path> --without-<some-dependency>
# using  wget
wget -qO- https://gitlab.com/smspp/smspp-project/-/raw/develop/INSTALL.sh | sudo bash -s -- --install-root=<your-custom-path> --without-<some-dependency>

# macOS
# using curl
curl -s https://gitlab.com/smspp/smspp-project/-/raw/develop/INSTALL.sh | bash -s -- --install-root=<your-custom-path> --without-<some-dependency>
# using  wget
wget -qO- https://gitlab.com/smspp/smspp-project/-/raw/develop/INSTALL.sh | bash -s -- --install-root=<your-custom-path> --without-<some-dependency>

according to the following options table:

Unix	Windows	Description
--without-cplex	-withoutCplex	skip CPLEX installation
--without-gurobi	-withoutGurobi	skip Gurobi installation
--without-scip	-withoutSCIP	skip SCIP installation
--without-highs	(via vcpkg)	skip HiGHS installation
--without-stopt	(via vcpkg)	skip StOpt installation
--without-torch	-withoutTorch	skip Torch installation
--without-lemon	(via vcpkg)	skip LEMON installation
--without-coinor	(via vcpkg)	skip COIN-OR installation
--without-smspp	-withoutSMSpp	skip SMS++ build and installation
(n/a)	-updatevcpkg	refresh builtin-baseline in vcpkg.json

Note that CPLEX is not redistributable, so the scripts do not download it. To install it, point the script to your own installer via --cplex-installer=<path> on Unix or -cplexInstaller <path> on Windows. If no installer is provided, CPLEX is skipped and the build proceeds with the other solvers.

Otherwise, if you are already inside the cloned repository, you can run the script via:

# Windows (from a PowerShell as administrator)
.\INSTALL.ps1

or:

# Linux
sudo ./INSTALL.sh

# macOS
./INSTALL.sh

using the same flag options according to the OS, if needed.

If you need more detailed instructions on how to install the project's requirements, please refer to the SMS++ requirements installation guide.

Centralised path repository

You can either use CMake or plain makefiles to build the library, your choice. CMake compiles off-source, and it is therefore perhaps better suited to one-off, compile-and-forget installations, whereby the provided makefiles compile on-source, and we find that they are better suited while developing and testing new code (please do, this is a community project).

In both cases, all external dependencies should be automatically dealt with if they are installed in their default paths. These are specified in the *_ROOT values that are defined in the four files extlib/makefile-default-paths-linux, extlib/makefile-default-paths-macos, and extlib/makefile-default-paths-win for the three major OS families; the one that gets used is automatically selected by the build process (both with CMake and the makefiles). If not, the suggested way to change them is to copy the (right one of these) file(s) into extlib/makefile-paths and edit it. This file, if present, is automatically read and the values found there replace the corresponding non-default definitions. The rationale for not directly changing the makefile-default-paths-* is that extlib/makefile-paths file is .gitignore-d. Hence, it should not be necessary to re-change the makefiles (or stash/restore the changes) each time the project is pulled, or manually ignore the changes when it is pushed, which is very convenient for anyone who actually develops new SMS++ components (which you know you should, so please do).

Build and install with CMake

If you need more detailed instructions on how to install the project with CMake, please refer to the SMS++ installation guide.

The CMakeLists.txt file also provides a quick reference on requirements and dependencies between modules.

Several CMake configuration options are available, see here.

Build and install with makefiles

All modules, starting with the "core" SMS++ classes, also come with carefully hand-crafted makefiles. Using them may require dabbling with some makefile editing, but it is independent on CMake and may be more suited for anyone who is developing SMS++ components.

In principle makefiles may work right out of the bat if all dependencies are installed at their OS-specific default locations; see the extlib/makefile-default-paths-* discussion above. If any of the libraries is in a nonstandard location, it should be possible to still have the make process to run easily by copying extlib/makefile-default-paths-* into extlib/makefile-paths (the file is not there because it is .gitignore-d, precisely so that local settings are never accidentally made public and are not overwritten when pulling the repository again), and properly setting the corresponding *-ROOT values.

See the SMS++ installation wiki for further details.

The "core" SMS++ classes have a makefile for building the corresponding library in

SMS++/lib/makefile-lib

The makefile allow to choose the compiler name and the optimization/debug settings. This builds the lib/libSMS++.a that can be linked upon. Also, the

SMS++/lib/makefile-inc

file is provided for allowing external makefiles to ensure that the library is up-to-date (useful in case one is actually developing it). The simplest way to learn how to use it is to check the makefiles for testers, such as those in

MCFClassSolver/test
MILPSolver/test_*
tests/CapacitatedFacilityLocationBlock 
tests/LagBFunction 
tests/LagrangianDualSolver_MMCF
tests/LagrangianDualSolver_UC
tests/PolyhedralFunction
tests/PolyhedralFunctionBlock

and many others. Note that the makefile-lib and makefile-inc "listen" to the general macros CC and SW controlling the C++ compiler and its main options; these can therefore be set in the "main" makefile and will be used throughout the whole compilation. This may be useful to set system-specific values.

An example of this is the macro

CLANG_1200_0_32_27_PATCH

which activates a patch for a weird glitch of clang++ (from 1200.0.32.27 to at least 1200.0.32.29) that cause some boost::any magic to stop working. Other settings may be needed (see, for instance, the comments about --force_link in the makefile of tests/BoxSolver).

First steps

Although sadly a proper User Manual is still missing, the tests repository can be useful to get a first look at possible ways of using SMS++. In particular the three tests LagrangianDualSolver_Box, LagrangianDualSolver_MMCF and LagrangianDualSolver_UC all build, or load from file, a :Block amenable to Lagrangian relaxation, register two Solver (a :MILPSolver and a LagrangianDualSolver) to it, properly configure them if needed (mostly, but not exclusively, using Configuration files) and run the two Solver 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/LagBFunction and tests/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 LagrangianDualSolver_MMCF and LagrangianDualSolver_UC 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.

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

• "Consistent Dual Signals and Optimal Primal Solutions", funded by the Gaspard Monge program for Optimization and Operations Research.

• plan4res, grant agreement No 773897 within European Union's Horizon 2020 research and innovation programme.

• "Multilevel Heterogeneous Distributed Decomposition for Energy Planning with SMS++", funded by the Gaspard Monge program for Optimization and Operations Research.

• "Optimization under Uncertainty with SMS++", funded by the Gaspard Monge program for Optimization and Operations Research.