4 Presentations

• 
  03:30 PM - 03:55 PM

  A novel Newton-min algorithm for linear complementarity problems (LCP)

  • Mathieu Frappier, presenter, Université de Sherbrooke
  • Jean-Pierre Dussault, Université de Sherbrooke
  • Jean-Charles Gilbert, Inria Paris
  • Ibtihel Ben Gharbia, IFPEN, Rueil-Malmaison

  Despite its efficiency in many applications, there is yet no global convergence result for the semi-smooth Newton algorithm on the min function to solve an LCP involving a P-matrix. One reason is that the Newton-min direction is not always a descent direction at the kinks of the least-squares merit function. New variants ensuring both descent and finite local convergence are proposed. Empirical comparisons with other solvers will be presented.

• 
  03:55 PM - 04:20 PM

  A metaheuristic approach for the single-finger keyboard layout problem

  • Ana Herthel, presenter,
  • Anand Subramanian, Universidade Federal da Paraíba (UFPB - Brazil)

  SK-QAP is the problem associated with designing a single-finger keyboard layout. This work approaches the SK-QAP 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.

• 
  04:20 PM - 04:45 PM

  Mathematical programming formulations for the effcient solution of the k-sum approval voting problem

  • Diego Ponce, presenter, Concordia University
  • Justo Puerto, University of Seville
  • Federica Ricca, Universitá di Roma, La Sapienza
  • Andrea Scozzari, Universitá degli Studi Niccoló Cusano, Roma

  In this work we model the approval voting problem as a mixed integer linear program. Different formulations for the Minisum, Minimax and k-centrum objective functions have been developed, which are experimentally compared in a data base from the literature.

• 
  04:45 PM - 05:10 PM

  A convex reformulation and an outer approximation for a class of binary quadratic program

  • Borzou Rostami, presenter, Polytechnique Montreal
  • Andrea Lodi, Polytechnique Montreal
  • Fausto Errico, École de technologie supérieure

  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 mixed-integer nonlinear program (MINLP) and mixed-integer 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 branch-and-cut 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 state-of-the-art solver applied to different MILP reformulations of the corresponding problems.