Undergraduate Research Assistantship Noticeboard

General

When are the seminars held?

Every Thursday 2:30 pm - 3:30 pm in MC 5417.

Who is speaking at these seminars?

Graduate students, faculty members, and guests. The last few weeks of seminars will be presentations from the URA students themselves.

How do I get the Zoom information?

Faculty members and URA students will receive an email before each seminar with the Zoom meeting information. If you wish to join the seminar and did not recieve an email, please contact Faculty Coordinator Kostya Pashkovich for the Zoom information.

Schedule

July 21 Daniela Lubke - Convex relaxation of the binary quadratic knapsack problem

Speaker:	Daniela Lubke
Affiliation:	University of Waterloo
Location:	MC 5417

Abstract:

We consider a parametric convex quadratic programming, CQP, relaxation for the quadratic knapsack problem, QKP. This relaxation maintains partial quadratic information from the original QKP by perturbing the objective function to obtain a concave quadratic term. The nonconcave part generated by the perturbation is then linearized by a standard approach that lifts the problem to the matrix space. We present a primal-dual interior point method to optimize the perturbation of the quadratic function, and propose valid inequalities on the lifted matrix variable, derived from cover inequalities for the QKP. The result also applies to more general integer quadratic problems. Our best bounds are obtained from alternating between optimizing the parametric quadratic relaxation over the perturbation and adding cutting planes generated by the valid inequalities proposed.