Cid de Souza's CV

CID CARVALHO DE SOUZA - SHORT CURRICULUM VITAE

Office address :

Universidade Estadual de Campinas

Instituto de Computação

Cidade Universitária - Barão Geraldo

Caixa Postal 6176

13084-971 -Campinas (SP) - Brazil

Voice: 55-19-35215877

Fax: 55-19-35215847

Email:

URL: www.ic.unicamp.br/~cid

Personal:

Born 2nd June, 1963 in Piquete (SP), Brazil.

Brazilian. Married. Two children.

Education:

2005: Professor Titular (Full professor), Universidade Estadual de Campinas (UNICAMP)

2002-2003: Pos-doc at Carnegie Mellon University (Graduate School on Industrial Administration)
1998: Livre Docente (Associate Professor), Universidade Estadual de Campinas (UNICAMP)
1993: Dr. Sciences Appliquées, Université Catholique de Louvain (CORE)
1989: MSc. in Systems Engineering, Catholic University of Rio de Janeiro (PUC-RJ)
1985: Electrical Engineer, concentration in Systems Engineering, Catholic University of Rio de Janeiro (PUC-RJ)

Experience and Job History:

2005 - : full professor at the Institute of Computing of the University of Campinas (IC-UNICAMP)

2004 - 2006: head of the Department of Theory of Computing (IC-UNICAMP)

1998 - 2005: associate professor at the Institute of Computing of the University of Campinas (IC-UNICAMP)

1994 - 1998: assistant professor at the Institute of Computing of the University of Campinas (IC-UNICAMP)

1998 - 2000: head of the Department of Theory of Computing (IC-UNICAMP)

1995 - 1997: coordinator of the graduate program (IC-UNICAMP)

1988: PETROBRAS (Brazil Oil), training course in Mathematical Programming for Engineers.

1986 - 1987: White Martins (Industrial gas company), system analyst.

1984 - 1986: Exxon (Brazil), system analyst.

1984 - 1985: Brazilian Telecom, trainee.

Academic Fellowships and Grants:

2008 - present: Research Fellowship, Brazilian National Council for Science and Technology (CNPq), level 1d

2003: Pos-doctoral fellowship CAPES (Ministry of Education, Brazil)

2002: Pos-doctoral fellowship FAPESP (State Council for Research, São Paulo, Brazil)

1999 - 2007: Research Fellowship, Brazilian National Council for Science and Technology (CNPq), level 2

1995 - 1999: Research Fellowship, Brazilian National Council for Science and Technology (CNPq), level 2c

1993 - 1994: Research Fellowship, Université Catholique de Louvain (Belgium)

1989 - 1993: Doctorate Fellowship, Brazilian National Council for Science and Technology (CNPq)

1987 - 1989: M.Sc. Fellowship, Brazilian Ministry of Education (CAPES)

1987 - 1989: Research Support, IBM (Brazil)

1994 - 1999: fellowships for 10+ M.Sc. and postdoctoral students supervised or under supervision at FAPESP (State of São Paulo Research Foundation, Brazil)

Teaching:

Courses at UNICAMP:

Data Structures (Graduate and Undergraduate)
Design and Analysis of Algorithms (Graduate and Undergraduate)
Discrete Mathematics and Graph Theory (Undergraduate)
Integer Programming (Graduate)
Introduction to Computer Programming (Undergraduate)
Network Flows (Graduate)

Research Interests:

The formulation and resolution of problems in the fields of Operations Research (routing, scheduling, etc) and Computer Science (discrete computational geometry, computational biology, graphs, etc) by combinatorial optimization and mixed integer programming. Other: design and analysis of exact and approximate algorithms, heuristics, distributed algorithms for combinatorial optimization, the application of polyhedral combinatorics to different structured problems, hybrid algorithms using Constraint Programming, Mathematical Programming and Metaheuristics for hard combinatorial optimization problems.

Awards:

M.Sc. dissertation supervised (joint with Prof. Arnaldo V. Moura): by A. A. Cire, second prize in the UNESCO - Latin American Conference on Informatics (2009).
Best Paper Award in the Application Track of the International Conference on Principles and Practice of Constraint Programming (CP 2008), Sydney, Australia, 14-18 September 2008. Paper title: "Planning and Scheduling the Operation of a Very Large Oil Pipeline Network" (joint with A. Moura, A. Ciré and T. Lopes).
Grant "Zeferino Vaz" for excellence in teaching and research from the University of Campinas (2007).
Prêmio PETROBRAS de Tecnologia 2005 - Categoria "Produção"
(Brazilian Oil Company, Tecnology Prize 2005 - Category "Production") won by the student Romulo P. Albuquerque (joint supervision with Prof. Arnaldo V. Moura).
M.Sc. dissertation supervised (joint with Prof. Arnaldo V. Moura): by T. H. Yunes, first prize in the UNESCO - Latin American Conference on Informatics (2001).
Grant "Zeferino Vaz" for excellence in teaching and research from the University of Campinas (2001).
M.Sc. dissertation supervised: by C. N. Menezes, 4th prize in the UNESCO - Latin American Conference on Informatics (1998).

Postdoctoral students Supervised:

G. Manic, Mathematical modeling and applications of optimization problems relative to subgraphs with common structures (concluded 02/2008).
Luidi Simonetti, Constrained spanning forest in graphs. (concluded 06/2010).
Yuri Frota, Constrained spanning forest in graphs. (concluded 05/2010).

Doctoral Thesis Supervised:

E. Hoshino, The column generation method applied to graph optimization problems (concluded in 12/2009).
V. Cavalcante, Relax-and-cut algorithms for 0--1 Integer Programming problems, (concluded 07/2008).
E. M. Macambira, Integer Programming for Telecommunication Problems, (concluded 05/2003).
[co-supervised with Prof. Dr. Nelson Maculan, COPPE/UFRJ].
P. Coll, Scheduling Tasks in Unrelated Processors Under Precedence Constraints, (concluded 09/2002).
[co-supervised with Prof. Dr. Celso Ribeiro, PUC-Rio].

Master Thesis Supervised:

B. C. Marini, Algorithms for the scheduling of operations on a unidirectional multiproduct oil pipeline, (concluded 10/2011).
A. A. S. Braga, Lagrangian Relaxation and Cutting Planes Algorithms for the Set Partitioning Problem, (concluded 11/2011).
P. K. Zilli, Analysis of heuristic algorithms for "rich" vehicle routing problems, (concluded 05/2011).
M. C. Couto, An exact algorithm for an Art Gallery problem, (concluded 08/2010).
[co-supervised with Prof. Dr. Pedro de Rezende, UNICAMP].
C. A. Furushima, Algorithms for the solving the set packing problem using quasi-integral polyhedra, (concluded 12/2010).
T. M. T. Lopes, The planning and scheduling of the opearations in a pipeline oil network,
[co-supervised with Prof. Dr. Arnaldo Moura, UNICAMP]. (concluded 08/2010).
Breno Piva Ribeiro. A polyhedral study of the maximum common induced subgraph, (concluded 08/2009).
A. A. Cire, The flow problem in oil pipelines: heuristics and Constraint Programming, (concluded 08/2008).
[co-supervised with Prof. Dr. Arnaldo Moura, UNICAMP].

R.P. Albuquerque, Scheduling Activities for the development of oil wells: GRASP and other techniques, (concluded 10/2005).
[co-supervised with Prof. Dr. Arnaldo Moura, UNICAMP].

R. Santos, Use of canonical cuts in the local branching method for mixed 0-1 integer programs, (concluded 12/2006).

G. Vaz, Timetabling for urban bus lines using Constraint Programming, (concluded 06/2003).
[co-supervised by Prof. Dr. Arnaldo Moura, UNICAMP].

J. Martins, Scheduling activities in offshore oil platforms with hybrid algorithms, (concluded 12/2002).
[co-supervised by Prof. Dr. Arnaldo Moura, UNICAMP].

F. Calheiros, Optimal Rectangular Partitions: Lagrangian algorithms and cutting planes, (concluded September, 2001).
[co-supervised by Prof. Dr. Abílio Lucena, UFRJ].

M. Rodrigues, Planning trips of urban bus lines, (concluded June, 2001).

T. Yunes, Crew scheduling problems in Urban Public Transport: Constraint Logic Programming and other optimization techniques, concluded (2000).
[co-supervised by Prof. Dr. Arnaldo Moura, IC-UNICAMP].

R. Scachetti, Clustering and Routing in distribution logistics, concluded (1999).

C. Cavalcante, Scheduling under labor constraints, concluded (1998).

A. Nunes, Minimum Weight Triangulations: an integer programming approach, concluded (1997).

C. Meneses, Exact solutions of rectangular partitions via integer programming, concluded (1997).

E. Macambira, The Edge-Weighted Clique Problem: valid inequalities, facets and Polyhedral Computations, concluded (1997).

Publications:

Published papers:

An Exact Algorithm for Minimizing Vertex-Guards on Art Galleries, International Transactions in Operations Research, v. 18, p. 425-448, 2011. (with M. C. Couto and P. J. de Rezende).
The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm, Discrete and Applied Mathematics, Volume 159, Issue 16, Pages 1901-1914 (with L. Simonetti and Y. A. Frota).
Exact Algorithms for the Vertex Separator Problem in Graphs, Networks 57(3), 212-230, 2011 (with V. F. Cavalcante).
An exact approach to the problem of extracting an embedded network matrix, Computers and Operations Research, 38 (11), 1483 - 1492, 2011 (with R. M. V. de Figueiredo and M. Labbé).
A Branch-and-Price Approach for the Partition Coloring Problem, Operations Research Letters, 39 (2), 132-137, 2011, (with E. A. Hoshino and Y. A. Frota).
Experimental Evaluation of Algorithms for the Orthogonal Milling Problem with Turn Costs, Lecture Notes in Computer Science, vol. 6630, 304-314, Proceedings of the 10th International Symposium on Experimental Algorithms (SEA 2011). Kolimpari, Greece, May 2011. (with I. de Assis).
Planning and Scheduling the Operation of a Very Large Oil Pipeline Network, Constraints, v. 15, p. 151-189, 2010, (with A.V. Moura, A. Cire and T. Lopes).
A branch-and-cut algorithm for the maximum common edge subgraph problem Eletronic Notes in Discrete Mathematics, vol. 35, 47-52, December 2009 (special issue of the V Latin-American Algorithms, Graphs and Optimization Symposium) (with G. Manic and L. Bahiense)
Upper and lower bounding procedures for the for the minimum caterpillar spanning problem Eletronic Notes in Discrete Mathematics, vol. 35, 83-88, December 2009 (special issue of the V Latin-American Algorithms, Graphs and Optimization Symposium) (with L. Simonetti and Y. Frota)
A branch-and-cut-and-price approach for the capacitated m-ring-star problem Eletronic Notes in Discrete Mathematics, vol. 35, 103-108, December 2009 (special issue of the V Latin-American Algorithms, Graphs and Optimization Symposium) (with E.A. Hoshino)
Scheduling activities at oil wells with resource displacement, International Transactions in Operational Research, Vol 15, Issue 6, 659-683, November 2008 (with A. V. Moura, R. A. Pereira). http://DOI:10.1111/j.1475-3995.2008.00652.x
Acyclic Orientations with Path Constraints, RAIRO Operations Research, Volume 42, Issue 4, 455-468, October 2008 (with R.M.V. Figueiredo, V.C. Barbosa and N. Maculan).
Planning and Scheduling the Operation of a Very Large Oil Pipeline Network, Lecture Notes in Computer Science, vol. 5202, 36-51. Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP 2008), Sydney, Australia, September 2008 (with A. Moura, A. Ciré and T. Lopes).
Experimental Evaluation of an Exact Algorithm for the Orthogonal Art Gallery Problem Lecture Notes in Computer Science, vol. 5038, 101-113. Proceedings of the 7th International Workshop Experimental and Efficient Algorithms (WEA 2008), Provincetown, Cape Cod, Massachusetts, USA, May 30-June 1, 2008 (with M.C. Couto and P.J. Rezende)
Column Generation Algorithms for the Capacitated m-Ring-Star Problem, Lecture Notes in Computer Science, vol. 5092, 631-641. Proceedings of the 14th Annual International Computing and Combinatorics Conference (COCOON 2008), Dalian, China, June 2008 (with E.A. Hoshino)

Heuristics and Constraint Programming Hybridizations for a Real Pipeline Planning and Scheduling Problem Proceedings of the 11th IEEE International Conference on Computational Science and Engineering (CSE-08), São Paulo, Brazil, July 16-18, 2008. IEEE Computer Society Press, p.455-462.. (with A.V. Moura, A. Cire and T. Lopes).

A relax-and-cut algorithm to the set partitioning problem. Computers and Operations Research, 35, pages 1963-1981, 2008. (with V. Cavalcante and A. Lucena).

An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem. Proceedings of the XX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2007), Belo Horizonte, Brazil, October 2007, pages 87-94, IEEE Computer Society. http://doi.ieeecomputersociety.org/10.1109/SIBGRAPI.2007.7. (with M. Couto and P. J. de Rezende).

Lagrangian relaxation and cutting planes for the vertex separator problem. Lecture Notes in Computer Science, vol. 4614, 471-482. (Post) Proceedings of the First International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE 2007), Hangzhou, China, April 2007 (with V. Cavalcante).

Multiprocessor Scheduling under Precedence Constraints. Discrete and Applied Mathematics, Volume 154 (5), 770-801, April 2006. (with P. Coll and C. Ribeiro).

A column generation approach for SONET ring assignment. Networks, Volume 47, Issue 3, 157-171. May 2006.
(with E. Macambira and N. Maculan).

Vehicle and Crew Scheduling for Urban Bus Lines. European Journal of Operational Research, Volume 170, Issue 3, 844-862, May 2006.
(with M. M. Rodrigues and A. V. Moura).

The Datapath Merging Problem in Reconfigurable Systems: Lower Bounds and Heuristic Evaluation (with A. Lima, N. Moreano and G. Araujo).
ACM Journal on Experimental Algorithms, Volume 10, Issue 2, pages 1-16, 2005.
A note on characterizing canonical cuts using geometry. International Transactions in Operational Research, (12), 581--593, 2005 (with E. Macambira and N. Maculan).

Efficient Datapath Merging for Reconfigurable Architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 24, Issue 7, July 2005, pages 969 - 980 (Digital Object Identifier 10.1109/TCAD.2005.850844) (with N. Moreano, E. Borin and G. Araujo).

The vertex separator problem: algorithms and computations. Mathematical Programming - Series A, Volume 103, Issue 3, Jul 2005, Pages 609 - 631 (with Egon Balas).

The vertex separator problem: a polyhedral investigation. Mathematical Programming - Series A, Volume 103, Issue 3, Jul 2005, Pages 583 - 608 (with Egon Balas).

Hybrid Column Generation Approaches for Urban Transit Crew Management Problems. Transportation Science, vol. 39, No. 2, 273--288, May 2005. (with Tallys H. Yunes and Arnaldo V. Moura)

Comparative Experiments with GRASP and Constraint Programming for the Oil Well Drilling Problem Lecture Notes in Computer Science, vol. 3503, 328-340, Proceedings of the Fourth International Workshop Experimental and Efficient Algorithms (WEA 2005), Santorini, Greece, May 2005 (with R. A. Pereira and A. V. Moura).

The Datapath Merging Problem in Reconfigurable Systems: Lower Bounds and Heuristic Evaluation. Lecture Notes in Computer Science, vol. 3059, 545--558, Proceedings of the Third International Workshop Experimental and Efficient Algorithms (WEA 2004), Angra dos Reis, RJ, Brazil, May 25-28, 2004. (with A. M. M. Lima, N. B. Moreano and G. Araujo).

Constructing Nurse Schedules at Large Hospitals. International Transactions in Operations Research, v.10, 245-265, 2003. (with D. Ferber, T. Dias and A. Moura).

Optimal Rectangular Partitions. Networks, 41 (1), 51-67, 2003 (with Abílio Lucena and Felipe Calheiros).

Rearrangement of DNA fragments: a branch-and-cut algorithm, Discrete Applied Mathematics, (116)1-2, 161-177, 2002 (with C.E. Ferreira and Y. Wakabayashi)

Scheduling Projects with Labor Constraints. Discrete Applied Mathematics, 112, 27-52, 2001 (with C.C Cavalcante, M.W.P. Savelsbergh, Y. Wang and L.A. Wolsey).

Parallel Cooperative Approaches for the Labor Constrained Scheduling Problem, in Essays and Surveys in Metaheuristics (C.C. Ribeiro and P. Hansen, editors), 201-225, Kluwer, 2001. (with C.C.B. Cavalcante, V.C. Cavalcante and C.C. Ribeiro)

Exact solutions of rectangular partitions via integer programming. International Journal of Computational Geometry and Applications, vol. 10, No. 5, 477-522, 2000. (with C. N. de Meneses).

Solving Very Large Crew Scheduling Problems to Optimality. Proceedings of the 14th ACM Symposium on Applied Computing (SAC 2000). vol. 1, 446-451, Villa Olmo, Como, Italy. March 19-21, 2000 (with T. H. Yunes and A. V. Moura).

A Hybrid Approach for Solving Large Scale Crew Scheduling Problems. Lecture Notes in Computer Science, vol. 1753, 293 - 307, Proceedings of the Second International Workshop on Practical Aspects of Declarative Languages (PADL'00). Boston, MA, USA. January 17-20, 2000 (with T. H. Yunes and A. V. Moura).

Scheduling under Labour Resource Constraints, Constraints, 5(4) (2000), 415 - 422 (with C. Cavalcante, Y. Colombani and S. Heipcke).

The Edge-Weighted Clique Problem: valid inequalities, facets and Polyhedral Computations. European Journal of Operational Research, 123 (2000), 346 - 371 (with E. M. Macambira).

A New Formulation for Scheduling Unrelated Processors under Precedence Constraints, Revue d'Automatique, Informatique et Recherche Operationelle (RAIRO), 33 (1999) , 87 - 90. (with C. C. Ribeiro, N. Maculan and S.Porto).

The Node Capacitated Graph Partitioning Problem: A Computational Study, Mathematical Programming, series B, 81 (1998), 229--256 (with C. E. Ferreira, A. Martin, R. Weismantel and L. A. Wolsey).

The Node Capacitated Graph Partitioning Problem: Formulations and Valid Inequalities, Mathematical Programming, series A, 74 (1996), 247-266 (with C. E. Ferreira, A. Martin, R. Weismantel and L. A. Wolsey).

Some New facets for the Equicut Polytope, Discrete and Applied Mathematics, Special Volume on Partitioning and Decomposition in Combinatorial Optimization, Eds. M. Lucertini, G. Rinaldi, A. Sassano e B. Simeone, Vol. 62 (1995), No. 1-3, 167-192 (with M. Laurent).

A New Approach to Minimizing the Frontwidth in Finite Element Calculations, Computer Methods in Applied Mechanics and Engineering, 111 (1994) 323-334 (with L. Wolsey, R. Keunings and O.Zone).

Heuristics for the minimum rectilinear Steiner Tree Problem: new algorithms and a computational study, Discrete and Applied Mathematics, 45 (1993), 205-220, (with C. C. Ribeiro).

A Worst-Case Bound for the Performance Ratio of Heuristics for the Minimum Rectilinear Steiner Tree Problem, OR Spektrum, 12 (1990), 109-111 (with C. C. Ribeiro).

O Problema de Steiner na Métrica Retilínea, Revista Latino-Americana de Investigación Operativa, 1-3 (1990), 213-249 (with C. C. Ribeiro).

Papers Accepted for Publication:

The maximum common edge subgraph problem: a polyhedral investigation, 2010 (with G. Manic, L. Bahiense and B. P. Ribeiro).

Polyhedral Study of The Maximum Common Induced Subgraph Problem, 2010, (with B. P. Ribeiro).

A Branch-and-Cut-and-Price Approach for the Capacitated $m$-Ring-Star Problem, 2010, (with E. A. Hoshino).

Papers Submitted:

Planning The Operation of a Large Real-World Oil Pipeline (with A. V. Moura and A. A. Ciré and T. M. Lopes).
A GRASP heuristic to construct effective drawings of proportional symbol maps (with G. Kunigami, P. J. de Rezende and R. G. Cano).
Optimizing the Layout of Proportional Symbol Maps: Polyhedra and Computation (with G. Kunigami, P. J. de Rezende and T.H. Yunes).
Languages:
Good knowledge of English, French and Portuguese.

last updated in January 2012 by ccs.