A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming

In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions make use of Integer Linear Programming (ILP) modeling and rely on state of the art solvers, to be able to find optimal solutions for large instances in a matter of minutes. In this work, … Read more

Finding Diverse Solutions of High Quality to Binary Integer Programs

Typical output from an optimization solver is a single optimal solution. At the same time, a set of high-quality and diverse solutions could be beneficial in a variety of contexts, for example problems involving imperfect information, or those for which the structure of high-quality solution vectors can reveal meaningful insights. In view of this, we … Read more

A Regularized SQP Method with Convergence to Second-Order Optimal Points

Regularized and stabilized sequential quadratic programming methods are two classes of sequential quadratic programming (SQP) methods designed to resolve the numerical and theoretical difficulties associated with ill-posed or degenerate nonlinear optimization problems. Recently, a regularized SQP method has been proposed that provides a strong connection between augmented Lagrangian methods and stabilized SQP methods. The method … Read more

Accelerating block-decomposition first-order methods for solving composite saddle-point and two-player Nash equilibrium problems

This article considers the two-player composite Nash equilibrium (CNE) problem with a separable non-smooth part, which is known to include the composite saddle-point (CSP) problem as a special case. Due to its two-block structure, this problem can be solved by any algorithm belonging to the block-decomposition hybrid proximal-extragradient (BD-HPE) framework. The framework consists of a … Read more

Robust Data-Driven Dynamic Programming

In stochastic optimal control the distribution of the exogenous noise is typically unknown and must be inferred from limited data before dynamic programming (DP)-based solution schemes can be applied. If the conditional expectations in the DP recursions are estimated via kernel regression, however, the historical sample paths enter the solution procedure directly as they determine … Read more

An efficient gradient method using the Yuan steplength

We propose a new gradient method for quadratic programming, named SDC, which alternates some SD iterates with some gradient iterates that use a constant steplength computed through the Yuan formula. The SDC method exploits the asymptotic spectral behaviour of the Yuan steplength to foster a selective elimination of the components of the gradient along the … Read more

Fast implementation for semidefinite programs with positive matrix completion

Solving semidefinite programs (SDP) in a short time is the key to managing various mathematical optimization problems in practical time. The matrix-completion primal-dual interior-point method (MC-PDIPM) extracts a structural sparsity of input SDP by factorizing the variable matrices, and it shrinks the computation time. In this paper, we propose a new factorization based on the … Read more

On the Convergence of Decentralized Gradient Descent

Consider the consensus problem of minimizing $f(x)=\sum_{i=1}^n f_i(x)$ where each $f_i$ is only known to one individual agent $i$ out of a connected network of $n$ agents. All the agents shall collaboratively solve this problem and obtain the solution subject to data exchanges restricted to between neighboring agents. Such algorithms avoid the need of a … Read more

Bin Packing and Related Problems: General Arc-flow Formulation with Graph Compression

We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems — including multi-constraint variants — by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without … Read more

A feasible active set method for strictly convex problems with simple bounds

A primal-dual active set method for quadratic problems with bound constraints is presented which extends the infeasible active set approach of [K. Kunisch and F. Rendl. An infeasible active set method for convex problems with simple bounds. SIAM Journal on Optimization, 14(1):35-52, 2003]. Based on a guess of the active set, a primal-dual pair (x,α) … Read more