Robust Network Design: Formulations, Valid Inequalities, and Computations

Categories Cutting Plane Approaches, Polyhedra, Robust Optimization Tags , , , ,

Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. In this paper we consider telecommunication network design under traffic uncertainty, adapting the robust optimization approach of Bertsimas and Sim (2004). We present three different mathematical formulations for this problem, provide valid inequalities, … Read more

Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming

Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , ,

In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (2008). By analyzing $n$-dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the … Read more

A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation

Categories Cutting Plane Approaches, Semi-infinite Programming Tags , , ,

We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornu\’ejols and Molinaro for k=2. ArticleDownload View PDF

Unbounded Convex Sets for Non-Convex Mixed-Integer Quadratic Programming

Categories (Mixed) Integer Nonlinear Programming, Polyhedra, Quadratic Programming Tags , , ,

This paper introduces a fundamental family of unbounded convex sets that arises in the context of non-convex mixed-integer quadratic programming. It is shown that any mixed-integer quadratic program with linear constraints can be reduced to the minimisation of a linear function over a set in the family. Some fundamental properties of the convex sets are … Read more

Complexity and Exact Solution Approaches to the Minimum Changeover Cost Arborescence Problem

Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , , , ,

We are given a digraph G = (N, A), where each arc is colored with one among k given colors. We look for a spanning arborescence T of G rooted at a given node and having minimum changeover cost. We call this the Minimum Changeover Cost Arborescence problem. To the authors’ knowledge, it is a … Read more

Improving Robust Rolling Stock Circulation in Rapid Transit Networks

Categories Civil and Environmental Engineering, Robust Optimization, Transportation Tags , ,

The routing of the rolling stock depends strongly on the rolling stock assignment to di erent opera- tions and the shunting schedule. Therefore, the integration of these decision making is justi ed and is appropriate to introduce robustness in the model. We propose a new approach to obtain better circula- tions of the rolling stock material, solving … Read more

Stochastic approaches for solving Rapid Transit Network Design models with random demand

Categories Civil and Environmental Engineering, Stochastic Programming, Transportation Tags , , ,

We address rapid transit network design problems characterized by uncertainty in the input data. Network design has a determinant impact on the future e ective- ness of the system. Design decisions are made with a great degree of uncertainty about the conditions under which the system will be required to operate. The de- mand is one … Read more

A copula-based heuristic for scenario generation

Categories Stochastic Programming Tags , ,

This paper presents a new heuristic for generating scenarios for two-stage stochastic programs. The method uses copulas to describe the dependence between the marginal distributions, instead of the more common correlations. The heuristic is then tested on a simple portfolio-selection model, and compared to two other scenario-generation methods. CitationPublished in Computational Management Science, 11 (4), … Read more

A smooth perceptron algorithm

Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , ,

The perceptron algorithm, introduced in the late fifties in the machine learning community, is a simple greedy algorithm for finding a solution to a finite set of linear inequalities. The algorithm’s main advantages are its simplicity and noise tolerance. The algorithm’s main disadvantage is its slow convergence rate. We propose a modified version of the … Read more

Exploiting structure of autoregressive processes in risk-averse multistage stochastic linear programs

Categories Stochastic Programming

We consider a multivariate interstage dependent stochastic process whose components follow a generalized autoregressive model with time varying order. At a given time step, we give some recursive formulae linking future values of the process with past values and noises. We then consider multistage stochastic linear programs with uncertain polyhedral sets depending affinely on such … Read more