Title:  Cutting planes for the reformulation-linearization technique (RLT) relaxations of mixed 0–1 polynomial programs

Abstract:

The reformulation-linearization technique (RLT), due to Sherali and Adams, is a general framework for constructing hierarchies of linear programming (LP) relaxations of various optimisation problems.  It was first developed for 0-1 polynomial programs, but was soon adapted to continuous polynomial programs, and then extended to mixed 0-1 polynomial programs. Since then, it has been further extended and adapted, to cover a wide range of integer programming and global optimisation problems. As one moves up the levels of the RLT hierarchy, the LP relaxations grow stronger, but the number of variables increases exponentially. In practice, therefore, one can hope to solve the relaxations only at very low levels of the hierarchy. In fact, even solving the relaxation at the first level can be  challenging.

We developed a framework which enables one to strengthen low-level RLT relaxations by adding cutting planes, rather than additional variables. Our framework allows to generate cutting planes at any given level of the hierarchy, by optimally weakening linear inequalities that are valid at any given higher level. The framework is applicable to mixed 0-1 polynomial programs with bounded continuous variables. It consists of three main components. First, we give procedures for constructing low-degree polynomial over- and under-estimators of polynomials of higher degree. Second, we show how to use those over- and under-estimators to convert any valid linear inequality for a given high-level RLT relaxation into an exponentially large collection of cutting planes for a given low-level RLT relaxation. Third, we present separation algorithms that, under certain conditions, enable one to find in polynomial time the most-violated cutting plane in a given collection.


In order to explore the potential of these new cutting planes, we will present some computational results, using the quadratic knapsack problem (QKP) as an example. It turns out that, for the difficult sparse QKP instances, our cutting planes close around half of the gap between the upper bound from the standard first-level relaxation and the optimum.

Bio:

Dr Franklin Djeumou Fomeni is a Postdoctoral Research Fellow at the Inter-University Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT) in Montreal, Canada. He received a B.Sc. and a Masters in Mathematics from the University of Yaounde 1, Cameroon. He was then selected by the African Institute for Mathematical Sciences (AIMS, www.nexteinstein.org) as one of the 50 brightest Africa-wide students to complete their 10-month Postgraduate Diploma program in Mathematical Sciences in Cape Town, South Africa. He subsequently completed an MSc in Applied Mathematics at the University of the Witwatersrand, South Africa. Franklin obtained his PhD in Operations Research from Lancaster University, United Kingdom, under the supervision of Adam Letchford.  He has received several awards for his academic achievements, among which, the Kingsman Prize for the best PhD thesis in Operations Research at Lancaster University, UK; the Rand Merchant Gold Medal, awarded to the best MSc student within the Faculty of Science at the University of the Witwatersrand, South Africa.


Franklin held postdoctoral positions at Polytechnique Montreal, Canada and at the Centre for Transport and Logistics (CENTRAL) at Lancaster University, UK.  His primary research interest is in Combinatorial Optimization, where he develops exact and heuristic solution methods using techniques such as Cutting planes, Branch-and-Cut, Dynamic Programming. He also has a particular interest in the application of optimization to problems in energy, transportation networks, Logistics, air traffic flow management and Manufacturing. His research has been published in journals such as Mathematical Programming, Transportations Research Part B: Methodological, European Journal of Operational Research, Computers & Operations Research and INFORMS Journal on Computing.