4 Presentations

• 
  03:30 PM - 03:55 PM

  On constrained mixed-integer DR-submodular minimization

  • Qimeng (Kim) Yu, presenter, Northwestern University
  • Simge Küçükyavuz, Northwestern University

  Submodular set functions play an important role in integer programming and combinatorial optimization. Increasingly, applications in resource allocation and machine learning have led to generalized submodular functions defined over general integer or continuous domains. In our study, we focus on the notion of Diminishing Returns (DR) submodularity and the problem of minimizing DR-submodular functions over mixed-integer feasible sets defined by box constraints and monotonicity constraints. We propose multiple classes of valid inequalities and further show that these inequalities, along with trivial constraints, fully describe the convex hull of the epigraph of DR-submodular functions under the aforementioned constraints. Our results hold in the original decision space, which avoids pseudo-polynomial expansions that are used to handle general integer variables in the existing literature.
• 
  03:55 PM - 04:20 PM

  Solving BIP Problems With Balas’ Additive Algorithm Using GPUs

  • Joseph Glover, Toronto Metropolitan University
  • Vinh Quan, presenter, University of Toronto at Scarborough
  • Saeed Zolfaghari, Toronto Metropolitan University

  Egon Balas’ additive algorithm, also known as implicit enumeration, is a technique that uses a branch-and-bound (B&B) approach to finding optimal solutions to 0-1 integer programming problems. We will present several parallel implementations of Balas’ algorithm that takes advantage of NVIDIA Graphical Processing Units (GPUs) to simultaneously evaluate thousands of subproblems. These implementations include using a depth-first search, breath-first search and best-first search strategy. Results show that utilizing a breadth-first search strategy across 69,632 parallel processors can lead to a max speedup of 1670x for some of our test problems.
• 
  04:20 PM - 04:45 PM

  Représentation générique de problèmes d'optimisation combinatoire

  • Léo Boisvert, presenter, Polytechnique Montréal

  Mots-clé: Graph Neural Networks, Constraint Programming, Machine Learning for combinatorial optimization
  Les méthodes à base d’apprentissage gagnent en popularité pour la résolution de problèmes d’optimisation combinatoire. Celles-ci nécessitent que l’on représente les problèmes sous une forme qui permette à un modèle -généralement un réseau de neurones- d’apprendre. Récemment, les Graph Neural Networks (GNN) se sont imposés comme le modèle de choix pour les problèmes d’optimisation combinatoire. Plusieurs problèmes sont naturellement représentés par des graphes, mais il n’existe toujours pas de représentation générique des problèmes d’optimisation combinatoire, c’est-à-dire une manière unifiée de représenter un problème d’optimisation combinatoire quelconque. Afin de standardiser la recherche et de pouvoir comparer différentes méthodes, une telle représentation serait bénéfique. Dans cette présentation, nous présenterons nos travaux dans cette voie et montrerons nos résultats obtenus avec une représentation générique des problèmes SAT et TSP décisionnel.
• 
  04:45 PM - 05:10 PM

  A study of the set-covering polyhedron through tilting vectors

  • Francois Lamothe, presenter, UQAM
  • Matthieu Gruson, HEC Montréal/CIRRELT
  • Claudio Contardo, ESG UQÀM / GERAD

  Given a ground-set of elements and a family of subsets, the set covering problem consists in choosing a minimum number of elements such that each subset contains at least one of the chosen elements. In this work, we study the set-covering polyhedron which is the convex hull of integer solutions of the set-covering problem.

  In particular, we link the study of the facets of the set-covering polyhedron to the theory of inequality tilting. This theory, introduced by Chvatal et al. (2013), studies how inequalities can be rotated around their contact points with a polyhedron in order to obtain new inequalities that induce faces of higher dimension. To that end, we introduce the \textit{tilting vectors} which characterize the degrees of freedom of the possible rotations of a valid inequality. We will present the following contributions. We study how tilting vectors characterize facet-defining inequalities. We show that tilting vectors can be used to tilt inequalities similarly to the procedure proposed by Chvatal et al. (2013). We present how the number of computations required to tilt an inequality can be reduced when the inequality has a lot of zero coefficients. Finally, we use the tilting vectors to extend several necessary and/or sufficient conditions for facets of the set-covering polyhedron presented by Cornuéjols and Sassano (1989),
  Sassano (1989) and Balas and Ng (1989).