A Priori Optimization

Dimitris J. Bertsimas, Patrick Jaillet and Amedeo R. Odoni
Additional contact information
Dimitris J. Bertsimas: Massachusetts Institute of Technology, Cambridge, Massachusetts
Patrick Jaillet: Ecole Nationale des Ponts et Chaussées, Noisy Le Grand, France
Amedeo R. Odoni: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1990, vol. 38, issue 6, 1019-1033

Abstract: Consider a complete graph G = ( V , E ) in which each node is present with probability p . We are interested in solving combinatorial optimization problems on subsets of nodes which are present with a certain probability. We introduce the idea of a priori optimization as a strategy competitive to the strategy of reoptimization, under which the combinatorial optimization problem is solved optimally for every instance. We consider four problems: the traveling salesman problem (TSP), the minimum spanning tree, vehicle routing, and traveling salesman facility location. We discuss the applicability of a priori optimization strategies in several areas and show that if the nodes are randomly distributed in the plane the a priori and reoptimization strategies are very close in terms of performance. We characterize the complexity of a priori optimization and address the question of approximating the optimal a priori solutions with polynomial time heuristics with provable worst-case guarantees. Finally, we use the TSP as an example to find practical solutions based on ideas of local optimality.

Keywords: networks/graphs: stochastic heuristics; traveling salesman; probability: stochastic model applications; transportation: vehicle routing (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (40)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.38.6.1019 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:38:y:1990:i:6:p:1019-1033

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().