We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight di ffers from the expected one. For this problem, we provide a dynamic programming algorithm … Read more
We consider bounded integer knapsacks where the weights and variable upper bounds together form a superincreasing sequence. The elements of this superincreasing knapsack are exactly those vectors that are lexicographically smaller than the greedy solution to optimizing over this knapsack. We describe the convex hull of this n-dimensional set with O(n) facets. We also establish … Read more
In this paper we propose two different primal-dual splitting algorithms for solving inclusions involving mixtures of composite and parallel-sum type monotone operators which rely on an inexact Douglas-Rachford splitting method, however applied in different underlying Hilbert spaces. Most importantly, the algorithms allow to process the bounded linear operators and the set-valued operators occurring in the … Read more
Airline recovery presents very large and difficult problems requiring high quality solutions within very short time limits. To improve computational performance, the complete airline recovery problem is generally formulated as a series of sequential stages. While the sequential approach greatly simplifies the complete recovery problem, there is no guarantee of global optimality or solution quality. … Read more
Interior-point methods in semidefinite programming (SDP) require the solution of a sequence of linear systems which are used to derive the search directions. Safeguards are typically required in order to handle rank-deficient Jacobians and free variables. We generalize the primal-dual regularization of \cite{friedlander-orban-2012} to SDP and show that it is possible to recover an optimal … Read more
We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the minimum cut problem. Our new semide finite programming relaxation of the minimum cut problem is obtained by strengthening the well-known semide nite programming relaxation for the quadratic assignment problem by fixing two vertices in the … Read more
A MATLAB implementation of the More’-Sorensen sequential (MSS) method is presented. The MSS method computes the minimizer of a quadratic function defined by a limited-memory BFGS matrix subject to a two-norm trust-region constraint. This solver is an adaptation of the More’-Sorensen direct method into an L-BFGS setting for large-scale optimization. The MSS method makes use … Read more
Many optimal decision problems in scientific, engineering, and public sector applications involve both discrete decisions and nonlinear system dynamics that affect the quality of the final design or plan. These decision problems lead to mixed-integer nonlinear programming (MINLP) problems that combine the combinatorial difficulty of optimizing over discrete variable sets with the challenges of handling … Read more
A stable symmetrization of the linear systems arising in interior-point methods for solving linear programs is introduced. A comparison of the condition numbers of the resulting interior-point linear systems with other commonly used approaches indicates that the new approach may be best suitable for an iterative solution. It is shown that there is a natural … Read more
In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements … Read more