A Computational Perspective

Matthias Miltenberger

… I set out to the exciting world of optimization!

From SCIP 2.0 to 7.0…

… from SoPlex 1.5 to 5.0!

**SoPlex:**- bound flipping ratio test
- LP solution polishing
- improved row representation
- better sparsity exploitation
- increased numerical stability

**SCIP:**- new LP interface to SoPlex
- persistent scaling
- TreeD visualization tool
- PySCIPOpt Python interface

\[ \begin{align} \max && c^Tx & \\ \text{subject to} && Ax & \leq b \\ && x &\geq 0 \\ && \phantom{x_j} & \phantom{\in \mathbb{Z}, \forall j \in \mathcal{I}} \end{align} \]

- \(A\in\mathbb{R}^{m,n},\; b\in\mathbb{R}^m,\; c\in\mathbb{R}^n\)
- LP in canonical form
- two common ways to solve:

Simplex algorithm:

📑 Dantzig, 1947

Barrier method:

📑 Kamarkar, 1984

\[ \begin{align} \max && c^Tx & \\ \text{subject to} && Ax & \leq b \\ && x & \geq 0 \\ && \color{blue}{x_j} & \color{blue}{\in \mathbb{Z}, \forall j \in \mathcal{I}} \end{align} \]

- additional integrality constraints
- common way to solve: branch-and-cut

Branch-and-bound:

📑 Land and Doig, 1960

\[ \begin{align} \max && c^Tx & \\ \text{subject to} && Ax & \leq b \\ && x & \geq 0 \\ && \color{RoyalBlue}{x_j} & \color{RoyalBlue}{\in \mathbb{Z}, \forall j \in \mathcal{I}} \end{align} \]

- additional integrality constraints
- common way to solve: branch-and-cut

Branch-and-bound:

📑 Land and Doig, 1960

Cutting plane separation:

📑 Gomory, 1958

- Netlib benchmark set

http://www.netlib.org/lp/ - Csaba Mészáros’s LP collection

http://www.sztaki.hu/~meszaros/public_ftp/lptestset/ - COR@L w/o integrality

http://coral.ie.lehigh.edu/data-sets/mixed-integer-instances/ - MIPLIB
^{1}, MIPLIB 3^{2}, MIPLIB 2003^{3}, MIPLIB 2010^{4}, and MIPLIB 2017^{5}w/o integrality

- MIPLIB 2017 benchmark set

https://miplib.zib.de/

📑 1: Bixby, Boyd, and Indovina, 1992

📑 2: Bixby, Ceria, et al., 1998

📑 3: Achterberg, Koch, and Martin, 2006

📑 4: Koch, Achterberg, et al., 2011

📑 5: Gleixner, Hendel, et al., 2021

Spotlight on some selected features

- define the Simplex basis not as subset of columns but of rows
- basic rows are active constraints defining the current vertex

A:

Basis:

column rep | row rep | |
---|---|---|

entering type |
primal simplex | dual simplex |

leaving type |
dual simplex | primal simplex |

- new features often need to be implemented twice

- define the Simplex basis not as subset of columns but of rows
- basic rows are active constraints defining the current vertex

A:

Basis:

column rep | row rep | |
---|---|---|

entering type |
primal simplex | dual simplex |

leaving type |
dual simplex | primal simplex |

- new features often need to be implemented twice

- always column representation:

8% slowdown - always row representation:

43% slowdown - automatic switch to row when row/column ratio > 1.2

- also known as
*long step rule* - allows increasing the progress made in a single iteration in the dual simplex
- combine several iterations into one

- impact on LP benchmark:
- 17% fewer iterations
- 7% speedup

- one scaling factor for every row and every column: \(A'=RAC,\; R,C\) diagonal
- keep LP scaling factors for the entire MILP solving process
- pass all LP modifications through scaling layer
- better numerics and performance for cuts and node LPs
- solves 9 more instances on MIPLIB 2017

- not all solutions are equal
- additional iterations to find less fractional solutions (more non-basic integer variables)
- performed internally by SoPlex
- SCIP provides integrality information

**[MIP] Solution Polishing** by Ed Rothberg, *An evolutionary algorithm for polishing mixed integer programming solutions*, INFORMS Journal on Computing (2007).

LP solver | wins |
---|---|

CPLEX | 79 |

SoPlex | 59 |

MOSEK | 55 |

Gurobi | 53 |

Xpress | 51 |

Clp | 48 |

177 instances finished root node after one hour

Branch & Bound & Cut

Joint work with Ted Ralphs and Dan Steffy

… is it Laurel or Yanny?

Consider this feasibility problem (no objective function):

\[ \begin{align} x + 10^{-8}y &= 10^{-7}\\ x, y &= 0 \end{align} \]

- mathematically infeasible (because \(0 + 0 \neq 10^{-7}\))

- using a feasibility tolerance of \(\epsilon=10^{-6}\):

- \(y=0\) non-basic
- \(x=10^{-7}\) basic
- feasible solution (within \(\epsilon\))

- \(x=0\) is non-basic
- \(y=10\) basic
- infeasible solution

`->`

**The result depends on the chosen Simplex basis!**

\(\kappa\):

\(\;1 \dots 10^7\)

fine

\(\;10^7 \dots 10^{10}\)

suspicious

\(\;10^{10} \dots 10^{14}\)

unstable

\(\;>10^{14}\)

ill-posed

- upper bound is typically not reached
- machine precision \(10^{-16}\) and tolerance \(10^{-6}\) to handle \(\kappa<10^{10}\)
- ideal: instance-specific, solver-independent metric for MILPs

- compute a \(\kappa_\text{LP}\) value that captures the entire problem data \(d=(A,b,c)\): \[ \begin{align} \kappa_\text{LP}(d) &:= \frac{\left\|d\right\|}{\min\left\{\rho_P(d), \rho_D(d)\right\}}, \\[1em] \|d\| &:= \max\left\{\|A\|_{\infty,1}, \|b\|_1, \|c\|_1\right\},\\[.5em] \rho_P(d) &:= \min_{i\in\left\{1,\dots,m\right\},\;j\in\left\{-1,1\right\}} \min_{y,s,v} \max\left\{\left\|A^T y+s-\right\|_1, \left|b^T y - v\right|\right\} \\[-1em] & \hspace{8.8em}\text{subject to}\quad y_i=j, \\[.5em] \rho_D(d) &:= \min_{i\in\left\{1,\dots,n\right\},\;j\in\left\{-1,1\right\}} \min_{x,p,g} \max\left\{\left\|Ax - p \right\|_1, \left|c^T x + g\right|\right\} \\[-1em] & \hspace{8.6em}\text{subject to}\quad x_i=j \end{align} \]

- both CPLEX and Xpress implement MIP-\(\kappa\)
- hard to make any reliable statements
- too many problems are “ill-conditioned” \((\kappa_\text{LP}\geq 10^{20})\)
- attention level learning appears to be a promising alternative

📑 Berthold, Numerics IV: Learning to pay attention, 2020

- interactive solver-by-solver comparisons
^{1} - largest publicly available benchmark dataset for linear, mixed-integer, nonlinear, and combinatorial problems by Hans Mittelmann
^{2} - published results are updated on a daily basis
- easier overview of latest ranking
- additional
*virtual best*or*portfolio solver*to reveal performance potential

- Simplex-oriented perspective on MILP solving
- performance and stability improvements for LP in MILP
- persistent scaling
- solution polishing

- impact of different LP solvers in SCIP
- pure LP performance is not decisive factor

- LP-based numerical study on MILP
- goal: find holistic measure to determine when to branch
- resulting in TreeD visualization

- PySCIPOpt extending the accessibility and usability of SCIP

*Thank you!*

1. Introduction

3. Implementational Aspects of the Simplex Algorithm

4. Impact of Linear Programming in MILP

5. LP Solution Polishing

6. Numerics in Branch & Bound & Cut

The Python interface to SCIP

- easy entryway to using and extending SCIP
- publicly developed on GitHub
^{1}under the MIT license since 2016 `conda install pyscipopt`

also installs the SCIP Opt Suite

Mathematical formulation \[\begin{align*} &\text{minimize} & x + 3y & \\ &\text{subject to} & 2x - y^2 & \geq 10 \\ & & x, y & \geq 0 \\ & & x & \in \mathbb{R} \\ & & y & \in \mathbb{Z} \\ \end{align*}\]

- allows natural and human-readable model formulations
- inspired by Gurobi’s Python interface