3 Presentations

• 
  03:30 PM - 03:55 PM

  Quantum-Inspired Methods for Clustering Large Datasets

  • Brian Mao, presenter, InfinityQ Technology Inc.

  Clustering is often applied throughout many different application areas, such as social networks and vehicle routing, to generate structure within datasets by grouping associated data points with strong similarity. However, most traditional clustering algorithms do not incorporate constraints that may arise in real world problems, while also using heuristics which can negatively impact cluster quality. A novel clustering algorithm is formulated and solved using quantum-inspired computing through the TitanQ platform to incorporate these constraint types, while directly solving the clustering problem via distance minimization. One example of a constraint is the generation of balanced clusters, where the number of nodes within each cluster is approximately equal. Quantum and quantum-inspired techniques, including mappings to Quadratic Unconstrained Binary Optimization (QUBO) formulations, are leveraged to solve large-scale problems. This provides the ability to potentially utilize next generation hardware to increase problem scale, solution quality, and solution speed. Native constraints are also included to enforce valid clustering solutions among the binary variables used to represent cluster assignments. This allows for increased algorithmic performance, with the addition of a novel compression scheme to induce memory improvement. Resulting clusters from the algorithm were also benchmarked against Lloyd’s algorithm on a dataset containing approximately 3000 data points.

• 
  03:55 PM - 04:20 PM

  A Polyhedral Study on L-Natural-Convex Minimization and Its Mixed-Integer Extension

  • Qimeng Yu, presenter, Université de Montréal
  • Simge Küçükyavuz, Northwestern University

  L-natural-convex functions are a class of nonlinear functions defined over integral domains. Such functions are not necessarily convex, but they display a discrete analogue of convexity. In this work, we explore the polyhedral structure of the epigraph of any L-natural-convex function and provide a class of valid inequalities. We show that these inequalities are sufficient to describe the epigraph convex hull completely, and we give an exact separation algorithm. We further examine a mixed-integer extension of this class of minimization problems and propose strong valid inequalities. We establish the connection between our results and the valid inequalities for some structured mixed-integer sets in the literature.

• 
  04:20 PM - 04:45 PM

  Leveraging 0-1 linear programming for partitioning and sampling in simulation-based optimization

  • Tommaso Schettini, presenter, HEC Montréal, École de technologie supérieure
  • Fausto Errico, École de technologie supérieure
  • Jorge Mendoza, HEC Montréal
  • Carolina Osorio, HEC Montréal

  Discrete Simulation-based Optimization (DSO) problems typically involve highly complex stochastic systems such as urban road networks.
  For such problems, computing the value of the objective function requires computationally intensive simulations.
  Thus, the methods employed tend to rely on iteratively sampling and partitioning the feasible space so as to progressively concentrate the sampling effort on its most promising portions.
  To boost the effectiveness of such methods, it is fundamental to quickly identify which portions of the feasible space are relevant to explore through an effective partitioning scheme, where solutions within the same partition behave similarly to one another with respect to the simulated objective function.
  In this presentation, we discuss a mechanism that uses the mathematical structure of the feasible space of a DSO problem to construct auxiliary 1-1 linear programming formulations to partition and sample in a DSO method.
  Additionally, we discuss two streamlined strategies for injecting problem-specific information into the proposed partitioning step and for biasing the sampling step of our approach to boost the overall performance.
  Finally, we present the application of our method to a simulation-based charger location problem for an autonomous fleet of ride-hailing taxis.