← volver

Ciclo seminarios Instituto Sistemas Complejos de Ingeniería (ISCI)

Auditorio Sala Asamblea, 4to piso, Beauchef 851

Invitada: Monique Guignard – Spielberg, Professor, Department of Operations, Information and Decisions The Wharton School, University of Pennsylvania

Título de la conferencia: “A Review of some Approaches for 0-1 Quadratic Optimization Problems with Linear Constraints”

Abstract

Solving optimization problems in 0-1 variables is much more difficult when the objective function is quadratic rather than linear, particularly when it is nonconvex. The talk will concentrate on methods used either for computing valid bounds on the optimum, or for generating good feasible solutions. Preprocessing approaches, based on convexification or on linearization, have been developed to generate valid bounds on the optimum.  We will briefly describe two of them, QCR(*) (Quadratic Convex Reformulation), based on semi-definite programming, and RLT (Reformulation Linearization Technique), which can be used for generating valid bounds on the optimal values.  The Convex Hull Heuristic, loosely based on Simplicial Decomposition, is a generic matheuristic for 0-1 quadratic problems with linear constraints. Numerical results will be presented for several special problems, in particular QAP (quadratic assignment problem), GQAP (generalized QAP), CDAP (crossdock door assignment problem), and QKP (quadratic knapsack problem).

(*) Two implementations of the QCR method can be found in the GAMS library: (GQAPSDP,SEQ=339) for the GQAP, and (KQKPSDP,SEQ=355) for the QKP with a cardinality constraint

Almuerzos previa inscripción desde las 13:15

INSCRIPCIONES AQUÍ

Organiza: Instituto Sistemas Complejos de Ingeniería (ISCI)

Consultas: seminarios@isci.cl