Journées de l'optimisation 2018
HEC Montréal, Québec, Canada, 7 — 9 mai 2018
TB8 Combinatorial optimization
8 mai 2018 15h30 – 17h10
Salle: Metro inc. (72)
Présidée par Borzou Rostami
4 présentations

15h30  15h55
A novel Newtonmin algorithm for linear complementarity problems (LCP)
Despite its efficiency in many applications, there is yet no global convergence result for the semismooth Newton algorithm on the min function to solve an LCP involving a Pmatrix. One reason is that the Newtonmin direction is not always a descent direction at the kinks of the leastsquares merit function. New variants ensuring both descent and finite local convergence are proposed. Empirical comparisons with other solvers will be presented.

15h55  16h20
A metaheuristic approach for the singlefinger keyboard layout problem
SKQAP is the problem associated with designing a singlefinger keyboard layout. This work approaches the SKQAP by means of an Iterated Local Search (ILS) algorithm. It solves the 24 existing instances and 6 new developed ones with highly competitive results both in terms of solution quality and CPU time.

16h20  16h45
Mathematical programming formulations for the effcient solution of the ksum approval voting problem
In this work we model the approval voting problem as a mixed integer linear program. Different formulations for the Minisum, Minimax and kcentrum objective functions have been developed, which are experimentally compared in a data base from the literature.

16h45  17h10
A convex reformulation and an outer approximation for a class of binary quadratic program
In this talk, we propose a general modeling framework for a large class of binary quadratic programs subject to variable partitioning constraints. This problem has a wide range of applications as many of the binary quadratic programs with linear constraints can be represented in this form. By exploiting the problems' structure, we propose mixedinteger nonlinear program (MINLP) and mixedinteger linear program (MILP) reformulations and show the relationship between the two models in terms of the relaxation strength. Our methodology relies on a convex reformulation of the proposed MINLP and a branchandcut algorithm based on outer approximation cuts where the cuts are generated on the fly by efficiently solving separation subproblems. Our experimental results on various quadratic combinatorial optimization problems show that our approach outperforms the stateoftheart solver applied to different MILP reformulations of the corresponding problems.