Journées de l'optimisation 2018

HEC Montréal, Québec, Canada, 7 — 9 mai 2018

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TB8 Combinatorial optimization

8 mai 2018 15h30 – 17h10

Salle: Metro inc. (72)

Présidée par Borzou Rostami

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h30 - 15h55

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

    • Mathieu Frappier, prés., 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h55 - 16h20

    A metaheuristic approach for the single-finger keyboard layout problem

    • Ana Herthel, prés.,
    • 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h20 - 16h45

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

    • Diego Ponce, prés., 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h45 - 17h10

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

    • Borzou Rostami, prés., Polytechnique Montreal
    • Andrea Lodi, Polytechnique Montréal
    • 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.