A Computational Perspective
… I set out to the exciting world of optimization!
From SCIP 2.0 to 7.0…
… from SoPlex 1.5 to 5.0!
\[ \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} \]
Simplex algorithm:
Barrier method:
\[ \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} \]
Branch-and-bound:
\[ \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} \]
Branch-and-bound:
Cutting plane separation:
📑 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
A:
Basis:
column rep | row rep | |
---|---|---|
entering type | primal simplex | dual simplex |
leaving type | dual simplex | primal simplex |
A:
Basis:
column rep | row rep | |
---|---|---|
entering type | primal simplex | dual simplex |
leaving type | dual simplex | primal simplex |
Not to be confused with [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
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} \]
->
The result depends on the chosen Simplex basis!
Definition of condition number \(\kappa\) of a square matrix \(A\)
\(\kappa(A) = \|A\|\cdot\|A^{-1}\|\) provides upper bound on input error amplification in the solution of a linear system \(Ax=b\). It is the normed reciprocal of the distance to singularity and applicable to LP/MILP because of their reliance on solving linear systems with the Simplex basis matrix.
\(\kappa\):
\(\;1 \dots 10^7\)
fine
\(\;10^7 \dots 10^{10}\)
suspicious
\(\;10^{10} \dots 10^{14}\)
unstable
\(\;>10^{14}\)
ill-posed
Thank you!
Simplex
Solution polishing
Figure 1.5: Size distribution of LP test set, including solving time colorization for SoPlex with default settings. Sparsity is computed as nonzeros/\((n*m)\)
Figure 1.6: Number of iterations and time to optimality (using a time limit of one hour) with respect to the number of nonzero elements in the problem matrices
Figure 3.1: Minimum solving times for row and column representation depending on row to column ratio on the allLP test set.
Figure 3.4: Pricing statistics
Figure 3.6: Distribution of variability scores > \(10^{−6}\) for solving time and iterations of SoPlex 4.0.2 across three different seeds; allLP test set
Figure 4.2: Fraction of time spent solving LPs during MILP solving; MIPLIB 2017 benchmark
Figure 4.3: Comparison of root LP performance with SCIP/MOSEK; MIPLIB 2017 benchmark
Figure 4.4: Histogram of fraction of time spent solving LPs during MILP solving; MIPLIB 2017 benchmark
Figure 4.5: Distribution of different LP types to be solved during MILP optimization; MIPLIB 2017 benchmark
Figure 4.9: Illustrative example of MDS transformation and associated Shepard error plot
Figure 4.10: TreeD visualization of MIPLIB3 instance lseu (89 binary variables, 28 constraints)
Figure 4.11: Shepard plot of original and transformed pairwise distances of all encountered node LP solutions after applying the MDS transformation
Figure 4.12: Overall performance comparison of different LP solvers in SCIP 6.0.2 with default settings on MIPLIB 2017 benchmark.
Figure 4.13: Distribution of solving time and iteration ratios for different LP solvers in SCIP to solve the root LPs on MIPLIB 2017 benchmark.
Figure 4.14: Development of node LP solving times and simplex iterations in the tree, relative to the root LP. MIPLIB 2017 instances solved within one hour by all solvers (54 instances)
Figure 4.15: Comparison of the gap after root node processing. Node limit of one, time limit of one hour on MIPLIB 2017 benchmark (117 instances).
Figure 4.16: Comparison of the node throughput, time limit of one hour MIPLIB 2017 benchmark. No cuts, no primal heuristics. Results are restricted to instances with a tree size of at least 100.
Figure 5.2: Effect of LP solution polishing on the condition numbers of the optimal basis matrix of first LP relaxations of the MIPLIB 2017 benchmark instances. Condition number changes are differences in log10 with and w/o polishing.
Figure 5.3: Effect of solution polishing on the fractionality of the first LP solution for the MIPLIB 2017 benchmark instances. 3 seeds with SCIP 7
Figure 5.4: Effect of solution polishing on the total solving time for the MIPLIB 2017 benchmark instances. Factors below 1 indicate a speedup. 3 seeds with SCIP 7.
Figure 6.3: Condition number development (vertical axis, in log scale) for every simplex iteration in the root node (horizontal axis) including re-optimizations after adding cutting planes in multiple rounds (vertical lines). A plot of objective values at each iteration is overlaid as a dashed gray line with the scales given to the right of each plot.
Figure 6.4: Root node comparison of condition numbers of the original LP and after including cutting planes. Most instances show a higher condition number during the cutting stage and when this process is completed
Figure 6.5: Aggregated condition numbers (in log10 scale) for different tree depths. MMM test set; solved in 1 hour and min tree depth of 10. Mean value of condition numbers and the respective 95% confidence interval. Breadth-first search with different cutting plane separation strategies.
Figure 6.6: Expected developments of condition numbers (in log10 scale): aggressive separation (sepaaggr) leads to an increased condition number across the entire tree while disabled cutting plane separation generates a larger tree but has smaller condition numbers.
Figure 6.7: Unexpected developments of condition numbers (in log10 scale): Disabling cutting plane generation (sepaoff) leads to worse condition numbers. The left instance exhibits decreasing condition numbers going down the tree while for the right instance, the numbers are growing.
Figure 6.8: Statistics of the κ\(_\text{LP}\) values and the tree condition numbers for various MILPs. Note that the κ\(_\text{LP}\) values are in each case the lower bounds from the estimation. The lower right subplot shows the κ\(_\text{LP}\) distribution which is independent of the solver.
The Python interface to SCIP
conda install pyscipopt
also installs the SCIP Opt SuiteMathematical 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*}\]