Giovanni Rinaldi
Giovanni Rinaldi Giovanni Rinaldi
Research Director
Director of the Institute

Istituto di Analisi dei Sistemi ed Informatica "Antonio Ruberti"
Via dei Taurini, 19
00185 Roma - Italy

Office n. 507
Tel.: +39 06 4993 7115
Fax: +39 06 4993 7106
email

Research interests

Combinatorial optimization, Integer linear optimization, Integer nonlinear optimization


Research groups

Selected publications
  • Bonato T., Jünger M., Reinelt G., Giovanni Rinaldi: Lifting and Separation Procedures for the Cut Polytope, Mathematical Programming 146, 351-378, 2014
  • De Giovanni L., Massi G., Pezzella F., Pfetsch M.E., Giovanni Rinaldi, Paolo Ventura: A heuristic and an exact method for the gate matrix connection cost minimization problem, International Transactions in Operational Research 20, 627-643, 2013
  • Hoffman K.L., Padberg M., Giovanni Rinaldi: Traveling Salesman Problem, in: Encyclopedia of Operations Research and Management Science - 3rd Edition, Gass S.I., Fu M.C. eds., Encyclopedia of Operations Research and Management Science, Springer New York Heidelberg Dordrecht London, 1573-1578, 2013
  • Grippo L., Palagi L., Piacentini M., Piccialli V., Giovanni Rinaldi: SpeeDP: an algorithm to compute SDP bounds for very large Max-Cut instances, Mathematical Programming 136, 353-373, 2012
  • Palagi L., Piccialli V., Rendl F., Giovanni Rinaldi, Wiegele A.: Computational Approaches to Max-Cut, in: Handbook on Semidefinite, Conic and Polynomial Optimization, Lasserre J.B., Anjos M.F. eds., International Series in Operations Research and Management Science, 166, Springer, 821-848, 2012
  • Jünger M., Liebling T., Naddef D., Nemhauser G., Pulleyblank W., Reinelt G., Giovanni Rinaldi, Wolsey L.A. eds.: 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, Springer Heidelberg, 2010
  • Jünger M., Liebling T., Naddef D., Pulleyblank W., Reinelt G., Giovanni Rinaldi, Wolsey L.A. eds.: Combinatorial Optimization and Integer Programming, Mathematical Programming, 124, 2010
  • Rendl F., Giovanni Rinaldi, Wiegele A.: Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations, Mathematical Programming 121, 307-335, 2010
  • Buchheim C., Giovanni Rinaldi: Terse integer linear programs for boolean optimization, Journal on Satisfiability, Boolean Modeling and Computation 6, 121-139, 2009
  • Giovanni Felici, Claudio Gentile, Giovanni Rinaldi, Peri F., Farina V.: Un approccio integrato per l'ottimizzazione della distribuzione di prodotti petroliferi greggi via mare, in: Scienza delle decisioni in Italia: applicazioni della ricerca operativa a problemi aziendali, Felici G., Sciomachen A. eds., ECIG, 385-398, 2008
  • Lodi A., Panconesi A., Giovanni Rinaldi eds.: Integer Programming and Combinatorial Optimization - IPCO XIII, Lecture Notes in Computer Science, 5035, Springer, 2008
  • Buchheim C., Giovanni Rinaldi: Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case, SIAM Journal on Optimization 18 (4), 1398-1413, 2007
  • Naddef D., Giovanni Rinaldi: The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation, Mathematics of Operations Research 32, 233-256, 2007
  • Rendl F., Giovanni Rinaldi, Wiegele A.: A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations, in the Proceedings of Integer Programming and Combinatorial Optimization - IPCO XII, Fischetti M., Williamson D.P. eds., Lecture Notes in Computer Science, 4513, Springer-Verlag, 295-309, 2007
  • Giovanni Felici, Giovanni Rinaldi, Sforza A., Truemper K.: A Logic programming based approach for on-line traffic control, Transportation Research Part C-Emerging Technologies 14, 175-189, 2006
  • Brewer D.D., Giovanni Rinaldi, Mogoutov A., Valente T.W.: A Quantitative Review of Associative Patterns in the Recall of Persons, Journal of Social Structure 6, 2005
  • Frangioni A., Lodi A., Giovanni Rinaldi: New Approaches for Optimizing over the Semimetric Polytope, Mathematical Programming 104, 375-388, 2005
  • Conforti M., Giovanni Rinaldi, Wolsey L.A.: On the cut polyhedron, Discrete Mathematics 277, 279-285, 2004
  • Frangioni A., Lodi A., Giovanni Rinaldi: Optimizing over Semimetric Polytopes, in the Proceedings of Integer Programming and Combinatorial Optimization - IPCO X, Bienstock D., Nemhauser G. eds., Lecture Notes in Computer Science, 3064, 2004
  • Claudio Gentile, Haus U.-U., Köppe M., Giovanni Rinaldi, Weismantel R.: On the way to perfection: Primal Operations for Stable Sets in Graphs, in: The sharpest cut, Grötschel M. ed., MPS/SIAM Series on Optimization, SIAM, 51-76, 2004
  • Liers F., Jünger M., Reinelt G., Giovanni Rinaldi: Computing exact ground states of hard Ising spin glass problems by branch-and-cut, in: New Optimization Algorithms in Physics, Hartmann A.K., Rieger H. eds., Wiley-VCH Verlag, 47-69, 2004
  • Lukic J., Anna Galluccio, Marinari E., Martin O.C., Giovanni Rinaldi: Critical Thermodynamics of the Two-Dimensional +/-J Ising Spin Glass, Physical Review Letters 92 (11), 117202-117205, 2004
  • Bielli M., Giovanni Felici, Giovanni Rinaldi, Truemper K.: A traffic simulation and signal control model based on logic programming, in the Proceedings of Traffic modeling: Trends and Challanges, Barcellona, 2003
  • Eisenbrand F., Giovanni Rinaldi, Paolo Ventura: Primal separation for 0/1 polytopes, Mathematical Programming 95, 475-491, 2003
  • Elf M., Jünger M., Giovanni Rinaldi: Minimizing Breaks by Maximizing Cuts, Operations Research Letters 31, 343-349, 2003
  • Jünger M., Reinelt G., Giovanni Rinaldi eds.: Heureka, you shrink!, Lecture Notes in Computer Science, 2570, Springer, 2003
  • McCormick S.T., Rao M.R., Giovanni Rinaldi: Easy and Difficult Objective Functions for Max Cut, Mathematical Programming 94, 459-466, 2003
  • Brewer D.D., Garrett S.B., Giovanni Rinaldi: Free-Listed Items are Effective Cues for Eliciting Additional Items in Semantic Domains, Applied Cognitive Psychology 16, 343-358, 2002
  • Brewer D.D., Garrett S.B., Giovanni Rinaldi: Patterns in the Recall of Sexual and Drug Injection Partners, in: Advances in Medical Sociology, Levy J.A., Pescosolido B.A. eds., Social Network and Health, 8, Elsevier Science Ltd., 131-149, 2002
  • Eisenbrand F., Giovanni Rinaldi, Paolo Ventura: 0/1 Optimization and 0/1 Primal Separation are Equivalent, in the Proceedings of Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 920-926, 2002
  • Frangioni A., Glover F., Lodi A., Giovanni Rinaldi: Optimizing over Semimetric Polytopes, in the Proceedings of IFORS 2002, Edinburgh, July 8--12, 2002
  • Claudio Gentile, Haus U.-U., Köppe M., Giovanni Rinaldi, Weismantel R.: A Primal Approach to the Stable Set Problem, in: Algoriths - ESA 2002, Möring R., Raman R. eds., Lecture Notes in Computer Science, 2461, Springer, 525-537, 2002
  • Naddef D., Giovanni Rinaldi: Branch and cut algorithms for the vehicle routing problem, in: The Vehicle Routing Problem, Vigo D., Toth P. eds., SIAM Monographs on Discrete Mathematics and Applications, SIAM, 53-84, 2002
  • Giovanni Rinaldi, Voigt U., Woeginger G.J.: The mathematics of playing golf, in the Proceedings of Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 265-266, 2002
  • Giovanni Rinaldi, Voigt U., Woeginger G.J.: The mathematics of playing golf, or: A new class of difficult non-linear mixed integer programs, Mathematical Programming 93, 77-86, 2002
  • Elf M., Gutwenger C., Jünger M., Giovanni Rinaldi: Branch-and-Cut Algorithms for Combinatorial Optimization and their Implementation in ABACUS, Jünger M., Naddef D. eds., Lecture Notes in Computer Science, 2241, Springer-Verlag, 157-222, 2001
  • Giovanni Felici, Claudio Gentile, Giovanni Rinaldi: Solving large MIP models in supply chain management by branch & cut, IASI-CNR, R. 522, 1/2000
  • Giovanni Felici, Giovanni Rinaldi, Sforza A., Truemper K.: Traffic control: a logic programming approach and a real application, Ricerca Operativa 30 (94/95), 39-60, 2000
  • Jünger M., Giovanni Rinaldi, Thienel S.: Practical Performances of Efficient Minimum Cut Algorithms, Algorithmica 26, 172-195, 2000
  • Giovanni Felici, Giovanni Rinaldi: Programmazione Logica, in: Science delle decisioni per i trasporti, Pallottino S., Sciomachen A. eds., Franco Angeli, 856-868, 1999
  • Giovanni Felici, Giovanni Rinaldi, Cantarella D., Sforza A.: Modelli e metodi per la regolazione semaforica, in: Science delle decisioni per i trasporti, Pallottino S., Sciomachen A. eds., Franco Angeli, 538-584, 1999
  • Augerat P., Belenguer J.M., Benavent E., Corberán A., Naddef D., Giovanni Rinaldi: Computational results with a branch and cut code for the capacitated vehicle routing problem, IASI-CNR, R. 495, 1998
  • Jünger M., Giovanni Rinaldi: Relaxations of the Max Cut Problem and Computation of Spin Glass Ground States, in the Proceedings of SOR '97, Kischka P., others eds., Operations Research Proceedings, 1998
  • Brunetta L., Conforti M., Giovanni Rinaldi: A branch-and-cut algorithm for the resolution of the equicut problem, Mathematical Programming 78, 243-263, 1997
  • Jünger M., Reinelt G., Rieger H., Giovanni Rinaldi eds.: Algorithmic Techniques in Physics, Dagstuhl Seminar Report, (197), 1997
  • Jünger M., Reinelt G., Giovanni Rinaldi: The Traveling Salesman Problem, in: Annotated Bibliographies in Combinatorial Optimization, Dell'Amico M., Maffioli F., Martello S. eds., John Wiley and Sons, Inc., 199-221, 1997
  • Chopra S., Giovanni Rinaldi: The graphical asymmetric traveling salesman polyhedron: Symmetric inequalities, SIAM Journal on Discrete Mathematics 9, 602-624, 1996
  • Caterina De Simone, Diehl M., Jünger M., Mutzel P., Reinelt G., Giovanni Rinaldi: Exact ground states of $2D \pm J$ Ising spin glasses, Journal of Statistical Physics 84, 1363-1371, 1996
  • Giovanni Felici, Giovanni Rinaldi, Truemper K.: FasTraC: A Decentralized Traffic Control System Based on Logic Programming, in the Proceedings of Proceedings of the 13th International Conference on Automated Deduction ({CADE}-13), McRobbie M.A., Slaney J.K. eds., Lecture Notes in Computer Science, 1104, Springer-Verlag, 216-220, 1996
  • Rieger H., Santen L., Blasum U., Diehl M., Jünger M., Giovanni Rinaldi: The critical exponents of the two-dimensional Ising spin glass revisited: Exact Ground State Calculations and Monte Carlo Simulations, Journal of Physics A-Mathematical and General 29, 3939-3950, 1996
  • Caterina De Simone, Diehl M., Jünger M., Mutzel P., Reinelt G., Giovanni Rinaldi: Exact ground states of Ising spin glasses: New experimental results with a branch and cut algorithm, Journal of Statistical Physics 80, 487-496, 1995
  • Jünger M., Reinelt G., Giovanni Rinaldi: The traveling salesman problem, in: Network Models, Ball M.O., others eds., Handbooks in Operations Research and Management Science, 7, Elsevier Publisher B.V. Amsterdam, 225-330, 1995
  • Lucertini M., Giovanni Rinaldi, Sassano A., Simeone B. eds.: Partitioning and Decomposition in Combinatorial Optimization, Discrete Applied Mathematics, 62, North-Holland Amsterdam, 1995
  • Caterina De Simone, Giovanni Rinaldi: A Cutting Plane Algorithm for the Max-cut Problem, Optimization Methods & Software 3, 195-214, 1994
  • Naddef D., Giovanni Rinaldi: The graphical relaxation: a new framework for the symmetric traveling salesman polytope, Mathematical Programming 58, 53-88, 1993
  • Giovanni Rinaldi, Wolsey L.A. eds.: Integer Programming and Combinatorial Optimization - IPCO III, Centro Ettore Majorana Erice, 1993
  • Naddef D., Giovanni Rinaldi: The crown inequalities for the symmetric traveling salesman polytope, Mathematics of Operations Research 17 (2), 308-326, 1992
  • Naddef D., Giovanni Rinaldi: The graphical relaxation: A new framework for the symmetric traveling salesman polytope, Mathematical Programming, 1992
  • Naddef D., Giovanni Rinaldi: The symmetric traveling salesman polytope and its graphical relaxation: composition of valid inequalities, Mathematical Programming 51 (3), 359-400, 1991
  • Padberg M., Giovanni Rinaldi: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review 33 (1), 60-100, 1991
  • Chopra S., Giovanni Rinaldi: The Graphical Asymmetric Traveling Salesman Polyhedron, in: Integer Programming and Combinatorial Optimization - IPCO I, Kannan R., Pulleyblank W.R. eds., University of Waterloo Press Waterloo, Ontario, 129-145, 1990
  • Padberg M., Giovanni Rinaldi: Addendum to Optimization of a 532-city symmetric traveling salesman problem by branch-and-cut, Operations Research Letters 9, 1990
  • Padberg M., Giovanni Rinaldi: An efficient algorithm for the minimum capacity cut problem, Mathematical Programming 47 (1), 19-36, 1990
  • Padberg M., Giovanni Rinaldi: Facet identification for the symmetric traveling salesman polytope, Mathematical Programming 47 (2), 219-257, 1990
  • Padberg M., Giovanni Rinaldi: A Branch-and-cut approach to a traveling salesman problem with side constraints, Management Science 35, 1393-1412, 1989
  • Padberg M., Giovanni Rinaldi, Sassano A. eds.: Algorithms and Discrete Optimization, Mathematical Programming, 45 (2), North-Holland Amsterdam, 1989
  • Padberg M., Giovanni Rinaldi, Sassano A. eds.: Polyhedra and Discrete Optimization, Mathematical Programming, 45 (1), North-Holland Amsterdam, 1989
  • Bianco L., Ricciardelli S., Giovanni Rinaldi, Sassano A.: Scheduling tasks with sequence dependent processing times, Naval Research Logistics Quarterly 35, 177-184, 1988
  • Padberg M., Giovanni Rinaldi: Branch-and-cut approach to a variant of the traveling salesman problem, Journal of Guidance Control and Dynamics 11, 436-440, 1988
  • Bianco L., Giovanni Rinaldi, Sassano A.: A combinatorial optimization approach to aircraft sequencing problem, in: NATO ASI Series, Vol.~F38, Odoni A.R., others eds., Springer-Verlag Berlin, 323-339, 1987
  • Padberg M., Giovanni Rinaldi: Optimization of a 532-city symmetric traveling salesman problem by branch-and-cut, Operations Research Letters 6, 1-7, 1987
  • Giovanni Rinaldi: A projective method for linear programming with box-type constraints, Algorithmica 1, 517-527, 1986
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -