\(\) We present two first-order primal-dual algorithms for solving saddle point formulations of linear programs, namely FWLP (Frank-Wolfe Linear Programming) and FWLP-P. The former iteratively applies the Frank-Wolfe algorithm to both the primal and dual of the saddle point formulation of a standard-form LP. The latter is a modification of FWLP in which regularizing perturbations … Read more
The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a … Read more
Distributionally robust optimization is used to solve decision making problems under adversarial uncertainty where the distribution of the uncertainty is itself ambiguous. In this paper, we identify a class of these instances that is solvable in polynomial time by viewing it through the lens of submodularity. We show that the sharpest upper bound on the … Read more
This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: … Read more
Presolving has become an essential component of modern MIP solvers both in terms of computational performance and numerical robustness. In this paper we present PaPILO (https://github.com/scipopt/papilo), a new C++ header-only library that provides a large set of presolving routines for MIP and LP problems from the literature. The creation of \papilo was motivated by the … Read more
The price of natural gas at wholesale markets in Northwest Europe is influenced by numerous parameters. The USD to EUR exchange rate is one of these parameters. Using the LP-based gas market model WEGA, this paper will examine the impact of USD exchange rates on wholesale natural gas prices in Northwest Europe from 2025 to … Read more
An arc-search interior-point method is a type of interior-point method that approximates the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and the computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov’s … Read more
Symmetry in optimization has been known to wreak havoc in optimization algorithms. Often, some of the hardest instances are highly symmetric. This is not the case in linear programming, as symmetry allows one to reduce the size of the problem, possibly dramatically, while still maintaining the same optimal objective value. This is done by aggregating … Read more
\(\) We consider two-stage robust linear programs with uncertain righthand side. We develop a General Polyhedral Approximation (GPA), in which the uncertainty set $\mathcal{U}$ is substituted by a finite set of polytopes derived from the vertex set of an arbitrary polytope that dominates $\mathcal{U}$. The union of the polytopes need not contain $\mathcal{U}$. We analyse … Read more
In this paper, we provide a characterization of the expected value of monotone submodular set functions with $n$ pairwise independent random inputs. Inspired by the notion of “correlation gap”, we study the ratio of the maximum expected value of a function with arbitrary dependence among the random inputs with given marginal probabilities to the maximum … Read more