Publications of Giovanni Rinaldi

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Rinaldi G., in the category IASI Research Reports (or show them all):


IASI Research Report n. 203  (Previous    Next)


Padberg M., Giovanni Rinaldi

A branch-and-cut approach to a traveling salesman problem with side constraints.

ABSTRACT
A problem posed by O.L. Deutsch as the Artificial Intelligence Design Challenge for the 1987 American Institute of Aeronautics and Astronautics [AIAA] Conference on Guidance, Navigation & Control (Monterey, CA, August 17-19, 1987) is formulated as a zero-one linear program. We show that the associated (relaxed) linear programming problem can be solved in polynomial time despite an exponentiation of the proposed constraint system in terms of the underlying parameter n of the number of cities considered, when a nonlinear constraint of the problem is either ignored or approximated by linearization. We describe a software system AIAA/SOLVER that we have implemented to solve the problem to optimality under an apparently weak assumption about its stochastic cost structure using branch-and-cut.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -