3 Presentations

• 
  01:30 PM - 01:55 PM

  A Comparison of Duality-Based Models for Inverse Linear Optimization

  • Yingcong Tan, presenter, University of Toronto
  • Terekhov Daria, Concordia University
  • Andrew Delong, Concordia University

  In inverse optimization (IO), the goal is to impute the unknown coefficients of an optimization model (the ``forward model'') from observed optimal decisions. In inverse linear optimization, the forward model is a (parametric) linear program. We extend and unify three different inverse linear optimization models that are based on duality, and compare them to the bilevel formulation of IO. We show that all three models have identical solution sets whenever a perfect fit to the observations is possible, but otherwise may have distinct optima. We also show that, even for identical solution sets, the coefficients returned by a solver for different IO models can have different generalization performances in practice, i.e., when the resulting forward model is solved under new conditions.
• 
  01:55 PM - 02:20 PM

  Résolution exacte de problèmes parcimonieux structurés : pourquoi et comment?

  • Sébastien Bourguignon, presenter, Ecole Centrale de Nantes
  • Gwenaël Samain,
  • Jordan Ninin,

  Les problèmes parcimonieux structurés visent à ajuster un ensemble de données (généralement au sens des moindres carrés) à un modèle linéaire, où la solution recherchée contient des groupes de variables simultanément nulles ou non-nulles. Des applications concernent le traitement du signal, la statistique et l'apprentissage automatique, domaines où les approches existantes résolvent des formulations relâchées du problème initial (NP-difficile) afin d'aborder des problèmes de grande taille. Dans cette communication, nous développons un cadre d'optimisation de type séparation et évaluation, permettant la résolution exacte de problèmes parcimonieux structurés de taille plus modeste. Une méthode de parcours d'arbre est proposée, où chaque noeud implique une décision sur la nullité conjointe d'une partie des variables. Des relaxations convexes efficaces sont proposées et résolues au moyen d'algorithmes de type descente par blocs. Enfin, la dualité convexe est exploitée afin d'accélérer les étapes d'élagage. Des expériences numériques valident l'intérêt des modèles parcimonieux structurés par rapport au cas de parcimonie scalaire simple et les solutions exactes ainsi obtenues s'avèrent de meillure qualité que celles des méthodes existantes, tout en restant accessibles pour des problèmes de petite dimension.
• 
  02:20 PM - 02:45 PM

  Novel Dynamic Programming for Quadratic Knapsack Problem

  • M. Eliass Fennich, presenter, Université Laval
  • Franklin Djeumou Fomeni, GERAD, Polytechnique Montréal
  • Leandro C. Coelho, Université Laval

  In the Quadratic Knapsack Problem (QKP), given a set of weighted objects, we need to determine a subset of these objects that maximizes the total linear and quadratic profit while respecting a knapsack constraint. This quadratic aspect of the problem makes it NP-hard in the strong sense. Heuristic dynamic programming is among the most efficient algorithms to solve this problem. It belongs to the divide-and-conquer family of algorithms, where the idea is to find the best solution for smaller instances of the problem and deduce the solution for other states from that. However, only a few states are used in this heuristic, and the computation of their value does not consider the potential quadratic profit that could be obtained from some future items, allowing efficient calculations. We present a novel heuristic in which we integrate these future profits, leading to better solutions for states with high capacity in the early stages of the algorithm. We take advantage of this approximation and propose a propagation heuristic for the yet unexplored states. Furthermore, we propose a local search improvement where we solve a reduced QKP with the remaining capacity from removing items in a solution. Some computational results will be presented to demonstrate the benefits of the new ideas.