Universidade Federal do Rio de Janeiro COPPE

Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia

Instituto de Matemática

 
Visualizar Meses
Visualizar Meses
Visualizar Flat
Visualizar Flat
Visualizar Semanas
Visualizar Semanas
Visualizar Dias
Visualizar Dias
Categorias
Categorias
Procurar
Procurar

Evento: 'Conferência: Pierre Bonami (CNRS-France)'

Eventos PESC (Palestras, Seminários, etc.)
Palestras, Seminários, etc. do PESC/COPPE/UFRJ.
Data: Wednesday, March 04, 2009 At 14:00
Duração: 2 Horas

Pierre BONAMI, pesquisador do CNRS no Laboratoire d'Informatique Fondamentale, Université de la Mediterannée, estará visitando o Programa de Engenharia de Sistemas e Computação (COPPE-UFRJ) de 02 a 06 de março de 2009, convidado por Nelson Maculan (Tel.: +55.21.25628708, e-mail: maculan@cos.ufrj.br).

Conferencista: Pierre Bonami

Título: Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs
(joint work with Anureet Saxena and Jon Lee)

Resumo
We address the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, we propose new methods for generating valid inequalities by using the equation /Y/ = /x/ /x/ ^ /T/ . We use the concave constraint 0 >= Y - x x^T to derive disjunctions of two types. The first ones are directly derived from the eigenvectors of the matrix Y - x x^T^ with positive eigenvalues, the second type of disjunctions are obtained by combining several eigenvectors in order to minimize the /width/ of the disjunction. We also use the convex SDP constraint Y - xx^T to derive convex quadratic cuts and combine both approaches in a cutting plane algorithm. We present preliminary computational results to illustrate our findings.

Data: 04 de março de 2009 (quarta-feira).
Horário: 14h00.
Local: sala G-122 , bloco G (térreo), Centro de Tecnologia (COPPE-UFRJ)

-------------------------------------------------------
Pierre Bonami, Laboratoire d'Informatique Fondamentale, Parc Scientifique et Technologique de Luminy,
163 avenue de Luminy - Case 901,
F-13288 Marseille Cedex 9, France.
Tel: (+33) 4 91 82 93 17 Fax: (+33) 4 91 82 92 75
pierre.bonami@lif.univ-mrs.fr
http://pageperso.lif.univ-mrs.fr/~pierre.bonami/

PUBLICAÇÕES do Pierre BONAMI

Recent research Reports

A. Saxena, P. Bonami and J. Lee. Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Extended Formulations. IBM Research Report RC24621, August 2008.

A. Basu, P. Bonami, G. Cornuéjols and F. Margot. On the Relative Strength of Split, Triangle and Quadrilateral Cuts. Tepper Working Paper 2008 E-38, Tepper School of Business, Carnegie Mellon University (7/2008)

A. Saxena, P. Bonami and J. Lee. Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Projected Formulations. IBM Research Report RC24695, 11/2008.

Journals

P. Bonami et M. Minoux. Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation. Discrete Optimization,2, 288-307, 2005.

P. Bonami et M. Minoux. Exact MAX-2SAT solution via lift-and-proect closure. Operations Research Letters, 34(4): 387-393, 2006.

P. Bonami, G. Cornuéjols. S. Dash, M. Fischetti. A. Lodi Projected Chvátal-Gomory cuts for mixed integer linear programs. Math. Programming 113(2):241-257,2008.

P. Bonami, L. T. Biegler, A. R. Conn, G. Cornuéjols, I.E. Grossmann, Carl D. Laird, Jon Lee, A. Lodi, F. Margot, N. Sawaya, A. Wächter, An Algorithmic Framework for Convex Mixed Integer Nonlinear Programs. Discrete Optimization, in press.

P. Bonami, G. Cornuéjols. A Note on the MIR closure. OR Letters, 36(1) 4-6, 2008.

P. Bonami, G. Cornuéjols, A. Lodi, F. Margot. A feasibility pump for Mixed Integer Nonlinear Programming. Math. Programming, in press.

P. Bonami, M.A. Lejeune. An Exact Solution Approach for Integer Constrained Portfolio Optimization Problems Under Stochastic Constraints. To appear in Operations Research.


Publicly available Software

P. Bonami, J.J Forrest, L. Ladanyi, J. Lee, F. Margot, A. Wächter. Bonmin: Basic open-source Mixed INteger solver. http://www.coin-or.org/Bonmin. Also available through NEOS optimizations solver web service.

P. Bonami. CglLandP. Efficient cut generator for lift-and-project. https://projects.coin-or.org/Cgl/wiki/CglLandP
International conference with proceedings


Procurar no Calendário

Powered by ExtCalendar 2

© 2017 PESC/COPPE - Programa de Engenharia de Sistemas e Computação

Cidade Universitária, Centro de Tecnologia, Bloco H, Sala 319
Caixa Postal: 68511 CEP: 21941-972 Fones: +55 21 3938-8672 / +55 21 3938-8673 Fax: +55 21 3938-8676
Rio de Janeiro - RJ - Brasil
Horário de atendimento da Secretaria: 2a. a 6a. de 7:00 às 16:00 horas (exceto feriados escolares)