A Warm-Start Approach for Large-Scale Stochastic Linear Programs

We describe a method of generating a warm-start point for interior point methods in the context of stochastic programming. Our approach exploits the structural information of the stochastic problem so that it can be seen as a structure-exploiting initial point generator. We solve a small-scale version of the problem corresponding to a reduced event tree … Read more

On Handling Free Variables in Interior-Point Methods for Conic Linear Optimization

We revisit a regularization technique of Meszaros for handling free variables within interior-point methods for conic linear optimization. We propose a simple computational strategy, supported by a global convergence analysis, for handling the regularization. Using test problems from benchmark suites and recent applications, we demonstrate that the modern code SDPT3 modified to incorporate the proposed … Read more

Combinatorial optimization problems in wireless switch design

The purpose of this paper is to illustrate the diversity of combinatorial problems encountered in the design of wireless switching systems. This is done via a representative selection of examples of real problems along with their associated resolution methods. It should be emphasized that all the resolution methods presented in this paper are successfully operating … Read more

A polyhedral approach to reroute sequence planning in MPLS networks

This paper is devoted to the study of the reroute sequence planning problem in multi-protocol label switching networks from the polyhedral viewpoint. The reroute sequence plan polytope, defined as the convex hull of the incidence vectors of the reroute sequences which do not violate the network link capacities, is introduced and some of its properties … Read more

A New Stochastic Algorithm for Engineering Optimization Problems

This paper proposes a new stochastic algorithm, Search via Probability (SP) algorithm, for single-objective optimization problems. The SP algorithm uses probabilities to control the process of searching for optimal solutions. We calculate probabilities of the appearance of a better solution than the current one on each iteration, and on the performance of SP algorithm we … Read more

Central path curvature and iteration-complexity for redundant Klee-Minty cubes

We consider a family of linear optimization problems over the n-dimensional Klee-Minty cube and show that the central path may visit all of its vertices in the same order as simplex methods do. This is achieved by carefully adding an exponential number of redundant constraints that forces the central path to take at least 2^n-2 … Read more

Local versus Global Profit Maximization: The Case of Discrete Concave Production Functions

In this paper we show that for discrete concave functions, a local maximum need not be a global maximum. We also provide examples of discrete concave functions where this coincidence holds. As a direct consequence of this, we can establish the equivalence of local and global profit maximizers for an equivalent well-behaved production function that … Read more

New upper bounds for kissing numbers from semidefinite programming

Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases n = 3, 4, 8, … Read more

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary … Read more

Geometric Dual Formulation for First-derivative-based Univariate Cubic $ Splines

With the objective of generating “shape-preserving” smooth interpolating curves that represent data with abrupt changes in magnitude and/or knot spacing, we study a class of first-derivative-based ${\cal C}^1$-smooth univariate cubic $L_1$ splines. An $L_1$ spline minimizes the $L_1$ norm of the difference between the first-order derivative of the spline and the local divided difference of … Read more