The problem of routing and wavelength assignment (RWA) in wavelength division multiplexing (WDM) optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned different wavelengths. This problem was shown to be NP-hard when the objective is to … Read more
We prove that the subdifferential of any semi-algebraic extended-real-valued function on $\R^n$ has $n$-dimensional graph. We discuss consequences for generic semi-algebraic optimization problems. CitationCornell University, School of Operations Research and Information Engineering, 206 Rhodes Hall Cornell University Ithaca, NY 14853. April 2010.ArticleDownload View PDF
Inferences need to be drawn in biological systems using experimental multivariate data. The number of samples collected in many such experiments is small, and the data is noisy. We present and study the performance of a robust optimization (RO) model for such situations. We adapt this model to generate a minimum and a maximum estimation … Read more
In this paper we propose a warm-start technique for interior point methods applicable to multi-stage stochastic programming problems. The main idea is to generate an initial point for the interior point solver by decomposing the barrier problem associated with the deterministic equivalent at the sec- ond stage and using a concatenation of the solutions of … Read more
Path-relinking is major enhancement to heuristic search methods for solving combinatorial optimization problems, leading to significant improvements in both solution quality and running times. We review its fundamentals and implementation strategies, as well as advanced hybridizations with more elaborate metaheuristic schemes such as genetic algorithms and scatter search. Numerical examples are discussed and algorithms compared … Read more
The Single Row Facility Layout Problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [Discrete Applied Mathematics 157(1)(2009)183-190]. For any number … Read more
In this paper, we study the relationship between {\em 2D lattice-free cuts}, the family of cuts obtained by taking two-row relaxations of a mixed-integer program (MIP) and applying intersection cuts based on maximal lattice-free sets in $\R^2$, and various types of disjunctions. Recently, Li and Richard (2007) studied disjunctive cuts obtained from $t$-branch split disjunctions … Read more
The matrix completion problem is to recover a low-rank matrix from a subset of its entries. The main solution strategy for this problem has been based on nuclear-norm minimization which requires computing singular value decompositions — a task that is increasingly costly as matrix sizes and ranks increase. To improve the capacity of solving large-scale … Read more
To retain a degree of tractability, the airline scheduling problem has traditionally been sequentially decomposed into various stages (eg. schedule generation, fleet assignment, aircraft routing, and crew pairing), with the decisions from one stage imposed upon the decision making process in subsequent stages. Whilst this approach greatly simpli es the solution process, it unfortunately fails to … Read more
In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck – tabu search (SB-TS) algorithm by replacing the reoptimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed … Read more