mld_software.qmd

---
title: "Software"
bibliography: 
    - ref_hybrid.bib
    - ref_mpc.bib
    - ref_integer_and_mixed_integer.bib
csl: ieee-control-systems.csl
format:
    html:
        html-math-method: katex
engine: julia
---

## HYSDEL

The concepts and procedures introduced in this lecture are straightforward but rather tedious to implement (just think of writing down all these transition rules for the finite state machine using binary variables). The authors of the MLD framework also developed a modelling language HYSDEL for entering a discrete hybrid automaton and subsequently converting it to the MLD description. Several links on the internet and in publications refer to the page [https://control.ee.ethz.ch/~hybrid/hysdel](https://control.ee.ethz.ch/~hybrid/hysdel), which is no longer available (as of December 2024). However, implementation of the HYSDEL parser/compiler is shipped together with [Hybrid Toolbox](https://cse.lab.imtlucca.it/~bemporad/hybrid/toolbox/) created by the Alberto Bemporad, one of original HYSDEL authors. 

Alternatively, [Multiparametric Toolbox 3](https://www.mpt3.org/) is a general framework for control-oriented modeling, simulation and optimization, which also contains HYSDEL among the dependencies.

A [new(er) version 3 of HYSDEL](https://www.uiam.sk/~kvasnica/hysdel3/) has been developed by Michal Kvasnica, but both Hybrid Toolbox and Multiparametric Toolbox are still based on HYSDEL 2.

## Support for indicator constraints in optimization modelling languages and optimization solvers

The key trick for the MLD framework was that of reformulating the *indicator constraint*
$$
[\delta = 1] \leftrightarrow [f(\bm x) \leq 0]
$$ 
using the *Big-M method* as two inequalities
$$
\begin{aligned}
f(\bm x) &\leq (1-\delta) M,\\
f(\bm x) &\geq \epsilon + (m-\epsilon)\delta
\end{aligned}
$$
using a sufficiently large constant $M$ and a sufficiently small constant $m$. But some solvers for mixed integer programming/optimization support the indicator constraints directly, without the need to come up with $M$ and $m$. As a matter of fact, the support is only provided for one of the two implications, namely
$$
[\delta = 1] \rightarrow [f(\bm x) \leq 0].
$$ 

Gurobi does provide such [support for indicator constraints](https://docs.gurobi.com/projects/optimizer/en/current/concepts/modeling/constraints.html#simple-constraints), the increasingly popular free&open-source [HiGHS](https://highs.dev) does not, ... 

The key idea behind such support is that mixed integer programming solvers can allow inserting (activating) a linear constraint based on the value of a given binary variable.

When it comes to "modelling" the optimization problems, in Julia's [JuMP package, indicators constraint](https://jump.dev/JuMP.jl/stable/manual/constraints/#Indicator-constraints) can be written as follows

``` {julia}
#| code-fold: show
using JuMP
model = Model();
@variable(model, x)
@variable(model, y)
@variable(model, δ, Bin)
@constraint(model, δ --> {x + y <= 1})
```

With Python API of Gurobi, the indicator constraints can be added using [addGenContstrIndicator](https://docs.gurobi.com/projects/optimizer/en/current/reference/python/model.html#Model.addGenConstrIndicator) function. One possible syntax is 
```
model.addConstr((delta == 1) >> (x + y - 1.0 <= 0.0))
```

The other direction of implication is not supported by optimization solvers. Therefore it has no support in optimization modellers such as JuMP either. In order to handle it, besides resorting to the Big-M method, we can also use the equivalent formulation
$$
[\delta = 0] \rightarrow [f(\bm x) \geq \epsilon], 
$$
where some small $\epsilon \geq 0$ had to be added to turn the strict inequality into a non-strict one.

Note, however, that it is not universally recommendable to rely on the support of the mixed integer solver for the indicator constraints. The reason is that sometimes the solvers may decide to reformulate the indicator constraints using the Big-M method by themselves, in which case we have no direct control over the choice of $M$.