Based on the recent approach of Bertsimas and Sim \cite{bs1, bs2} to robust optimization in the presence of data uncertainty, we prove a bound on the probability that the robust solution gives an objective function value worse than the robust objective function value, under the assumption that only cost coefficients are subject to uncertainty. A … Read more
We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lov\’asz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures’ performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations … Read more
We survey how semidefinite programming can be used for finding good approximative solutions to hard combinatorial optimization problems. CitationPreliminary version appeared as Report PNA-R0210, CWI, Amsterdam, April 2002. To appear as Chapter in the Handbook on Discrete Optimization, K. Aardal, G. Nemhauser, R. Weismantel, eds., Elsevier Publishers.ArticleDownload View PDF
Dantzig-Wolfe decomposition and column generation, devised for linear programs, is a success story in large scale integer programming. We outline and relate the approaches, and survey mainly recent contributions, not found in textbooks, yet. We emphasize on the growing understanding of the dual point of view, which brought considerable progress to the column generation theory … Read more
This paper develops a new mathematical model that integrates layout design and production planning to prescribe efficient multi-bay manufacturing facilities. The model addresses the need to distribute department replicas throughout the facility and extends the use of product and process requirements as problem parameters in order to increase process routing flexibility. In addition, the model … Read more
We present two capacity choice scenarios for the socially optimal location of facilities with fixed servers, stochastic demand and congestion. Walk-in health clinics, motor vehicle inspection stations, automobile emissions testing stations, and internal service systems are motivating examples of such facilities. The choice of locations for such facilities influences not only distances for users traveling … Read more
We consider the design of transparent optical networks from a practical perspective. Network operators aim at satisfying the communication demands at minimum cost. Such an optimization involves three interdependent planning issues: the dimensioning of the physical topology, the routing of lightpaths, and the wavelength assignment. Further topics include the reliability of the configuration and sparse … Read more
We consider the following integer feasibility problem: “Given positive integer numbers $a_0,a_1,\dots,a_n,$ with $\gcd(a_1,\dots,a_n)=1$ and $\va=(a_1,\dots,a_n)$, does there exist a vector $\vx\in\bbbz^n_{\ge \zero}$ satisfying $\va\vx = a_0$?” Some instances of this type have been found to be extremely hard to solve by standard methods such as branch-and-bound, even if the number of variables is as … Read more
We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope in Euclidean n-space. This is an important issue that arises at every `stage’ in a cutting plane algorithm. If q cuts are to be added, with q no larger than n, … Read more
We investigate the polyhedral structure of an integer program with a single functional constraint: the integer capacity-cover polyhedron. Such constraints arise in telecommunications planning and facility location applications, and feature the use of general integer (rather than just binary) variables. We derive a large class of facet-defining inequalities by using an augmenting technique that builds … Read more