Home

Scen-Opt

A Scenario Optimization Toolbox for Data-Driven Convex Programming

Scen-Opt is an open-source tool for data-driven convex optimization with the scenario approach of Campi and Garatti. It solves linear programs (LP), quadratic programs (QP) and semidefinite programs (SDP) whose constraints depend on an uncertain parameter $\delta$, when all you have is a list of sampled values $\delta_1,\ldots,\delta_N$ (the scenarios). It also gives a risk certificate for the solution.

For each problem Scen-Opt:

1. imposes one constraint per scenario and solves the convex program with a solver from CVXPY;
2. finds a support list of the solution, that is, the scenarios that determine it. Its size is the complexity $k$;
3. computes bounds $[\varepsilon_L, \varepsilon_U]$ on the risk, which is the probability that a new, unseen scenario violates the solution's constraint. The bounds hold with confidence at least $1-\beta$ for any distribution of $\delta$. You do not need to know or estimate the distribution.

The upper bound $\varepsilon_U$ always holds. The lower bound $\varepsilon_L$ also needs a non-degeneracy condition, which Scen-Opt checks and reports. See Scenario Theory for details.

• Web app: https://scen-opt.woodingben.com
• Repository: https://github.com/Kiguli/Scen-Opt
• Python API reference: https://kiguli.github.io/Scen-Opt/
• Docker image: ghcr.io/kiguli/scen-opt

Supported programs

Each program class has four formulations. They are all special cases of the general (relaxed and regularized) form. For an LP this form is

$$\min_{x,\ \zeta_i \ge 0}\quad c^\top x + \tau \Vert x - \bar{x} \Vert_p + \rho \sum_{i=1}^{N} \zeta_i$$

subject to $A(\delta_i)\ x + b(\delta_i) \le \zeta_i$ for $i = 1,\ldots,N$ (scenario constraints) and $Gx + h \le 0$ (hard constraints, which have no uncertainty).

Formulation (name in the web interface)	Objective	Scenario constraints
Robust	$c^\top x$	$A(\delta_i)\ x + b(\delta_i) \le 0$
Regularization	$c^\top x + \tau \Vert x - \bar{x} \Vert_p$	$A(\delta_i)\ x + b(\delta_i) \le 0$
Relaxation	$c^\top x + \rho \sum_i \zeta_i$	$A(\delta_i)\ x + b(\delta_i) \le \zeta_i,\ \zeta_i \ge 0$
Regularization + Relaxation	$c^\top x + \tau \Vert x - \bar{x} \Vert_p + \rho \sum_i \zeta_i$	$A(\delta_i)\ x + b(\delta_i) \le \zeta_i,\ \zeta_i \ge 0$

• QP adds $\tfrac{1}{2} x^\top Q x$ with $Q \succeq 0$ to the objective. See Quadratic Programs.
• SDP uses linear matrix inequalities. The scenario constraints are $F_0(\delta_i) + \sum_{j=1}^{d} x_j F_j(\delta_i) \preceq 0$ (or $\preceq \zeta_i I$ when relaxed), and the hard constraint is $E_0 + \sum_{j=1}^{d} x_j E_j \preceq 0$. See Semidefinite Programs.
• LP details are in Linear Programs.

Relaxation lets the solution violate some scenarios at a cost of $\rho$ per unit of violation. Regularization pulls the solution towards a reference point $\bar{x}$ with weight $\tau$, using the vector norm of order $p$ (any number $p \ge 1$, inf, or fro, which is the same as $p = 2$).

Features

• Risk certificates. Scen-Opt finds the support list by screening the dual variables and then pruning: it re-solves the problem and checks whether the optimal value changes. Hard constraints are always enforced and never counted in $k$. A degeneracy flag tells you when the lower risk bound is not certified; the results table then shows that bound as N/A.
• Parameter sweeps. You can enter comma-separated lists of $\rho$ and $\tau$. Scen-Opt solves one program for each $(\tau, \rho)$ pair. The reported overall confidence is $1 - \beta\ n_\tau n_\rho$ (a union bound over the $n_\tau n_\rho$ solves). Risk-and-cost graphs are drawn against $\rho$ or $\tau$. See In-built Graphics.
• Two input modes.
  • Symbolic: you enter the scenario-dependent matrices as expressions in delta[0], delta[1], … (for example sin(delta[0]) or delta[1]^2), and the scenario file holds the values of $\delta$.
  • Numeric: each row of the scenario file holds the already-evaluated matrices of one scenario.
• One-shot program upload. You can load a whole problem from a JSON or MAT file with Upload Program. After solving, you can download the same JSON again to reproduce the run later.
• File formats for scenario data: CSV, TXT, JSON, NPY/NPZ, MAT, Excel and Parquet.
• Result downloads as .json or .mat. These include the solve time and the risk-computation time.
• Solvers. Any CVXPY solver installed on the host can be used (e.g. MOSEK, CLARABEL, SCS, OSQP). The solver list is filtered to those that fit the active program type. MOSEK is recommended: it is the most stable solver for these problems and was used for all published results (academic licences are free). On the web app you upload your own MOSEK licence; it is used for that solve only and is not kept on the server.
• Three ways to run: the hosted web app, a local Python install, or a Docker image.
• Python API: solve_lp, solve_qp, solve_sdp and quantify_risk. You can use them from your own scripts. See First Example: Python Calls.
• Twelve benchmark case studies across LP, QP and SDP. Each comes with its data, ready-to-upload program files and solver scripts. They are in benchmarks/.

Getting started

1. Try it without installing anything. Open the web app and follow First Example: Web Interface. The example solves a small robust LP from a 100-point data set and explains every number in the results.
2. Run it on your own machine. Use Local Install, with Python or Docker. Do this for long-running problems, private data, or solvers that are not on the server.
3. Call it from Python. See First Example: Python Calls.
4. Learn the details:
   • formulations and inputs for each program class: Linear Programs, Quadratic Programs and Semidefinite Programs;
   • result graphs: In-built Graphics;
   • theory behind the risk bounds: Scenario Theory;
   • implementation notes for each module: LP.py, QP.py, SDP.py, Risk.py and Miscellaneous.py.

Licence

Scen-Opt is released under the MIT License. See LICENSE in the repository.

Authors

Ben Wooding, Simone Garatti, Marco C. Campi and Abolfazl Lavaei.

This work was supported in part by an EPSRC Doctoral Prize Research Fellowship at Newcastle University.