Tobias Achterberg - Gurobi Optimization - November 19th 2020

3:30 p.m. talk

Mixed Integer Programming (MIP) Solving in Practice

Mixed integer programming (MIP) has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth of applications appearing to be almost unlimited. In this lecture we will give an overview of the main algorithmic components implemented in state-of-the-art MIP solvers. We will go through all of the necessary steps to get a complete algorithm and through many of the optional steps that improve the performance of the basic procedure. We will highlight computational aspects and some implementational details, pointing out the various connections to related fields like combinatorial optimization, graph theory, linear algebra, group theory, and aspects of computer hardware. In summary, the goal is to show how much fun it is to work on the implementation of a state-of-the-art MIP solver, as it includes so many interesting algorithms from different math and computer science areas as sub-procedures.

Please email compmath@uwaterloo.ca for Zoom link

Vijay Ganesh - University of Waterloo - October 29th 2020

3:30 p.m. talk

Machine Learning and Logic Solvers: The Next Frontier SLIDES

Over the last two decades, software engineering has witnessed a silent
revolution in the form of Boolean SAT solvers. These solvers are now
integral to many analysis, synthesis, verification, and testing
approaches. This is largely due to a dramatic improvement in the
scalability of these solvers vis-a-vis large real-world formulas. What
is surprising is that the Boolean satisfiability problem is
NP-complete, believed to be intractable in general, and yet these
solvers easily solve instances containing millions of variables and
clauses in them. How can that be?
 
In my talk, I will address this question of why SAT solvers are so
efficient through the lens of machine learning as well as ideas from
(parameterized) proof complexity. I will argue that SAT solvers are
best viewed as proof systems, composed of prediction engines that
optimize some metric correlated with solver running time. These
prediction engines can be built using ML techniques, whose aim is to
structure solver proofs in an optimal way. Thus, two major paradigms
of AI, namely machine learning and logical deduction, are brought
together in a principled way to design efficient SAT solvers. A result
of my research is the MapleSAT solver, that has been the winner of
several recent international SAT competitions, and is now widely used
in industry and academia.

Please email compmath@uwaterloo.ca for Zoom link<--break->

Eldad Haber - University fo British Columbia - October 1st  2020 

3:30 p.m. talk

A Computational Mathematics View of Deep Learning with Applications    SLIDES

In this talk we discuss neural networks from the point of view of continuous dynamical systems namely, ODEs and PDEs. We show a strong link that suggests how one can view deep learning as a system of differential equations, which, in turn allows us to develop new network architectures. In the second part of the talk we discuss how deep learning can impact scientific computing by developing new integration techniques that can impact problems such as protein folding and molecular dynamics.

Please email compmath@uwaterloo.ca for Zoom link<--break->

Bartosz Protas- McMaster University - February 27th  2020 

Professor – Department of Mathematics and Statistics

DC 1304

3:00 p.m. refreshments | 3:30 p.m. talk

Searching for Singularities in Navier-Stokes Flows Using Variational Optimization Methods

In the presentation we will discuss our research program focused on a systematic search for the most singular behaviors possible in viscous incompressible flows. These events are characterized by extremal growth of various quantities, such as the enstrophy, which control the regularity of the solution. They are therefore intimately related to the question of singularity formation in the 3D Navier-Stokes system, known as the hydrodynamic blowup problem, which remains one of the most important open problems in mathematical fluid mechanics. We demonstrate how new insights concerning such questions can be obtained by formulating them as variational PDE optimization problems which can be solved computationally using suitable discrete gradient flows. More specifically, such an optimization formulation allows one to identify "extreme" initial data which, subject to certain constraints, leads to the most singular flow evolution. In offering a systematic approach to finding flow solutions which may saturate known estimates, the proposed paradigm provides a bridge between rigorous mathematical analysis and scientific computation. In particular, it makes it possible to determine whether or not certain mathematical estimates are "sharp", in the sense that they can be realized by actual vector fields, or if these estimates may still be improved. In the presentation we will review a number of results concerning 2D and 3D flows characterized by the maximum possible growth of different Sobolev norms of the solutions. Even when extreme initial data is used, highresolution computations for the 3D Navier-Stokes system reveals no tendency or singularity formation in finite time.<--break->

Henry Lam - Columbia University - February 11th 2020  

Associate Professor – Department of Industrial Engineering and Operations Research

MC 6460

3:15 p.m. refreshments | 3:30 p.m. talk

Efficient Uncertainty Quantification in Simulation Analysis

Simulation-based prediction, for instance in discrete-event analysis and machine learning, often incurs errors from both Monte Carlo computation and calibration noise from data. These errors, if overlooked, can result in incorrect inference and underestimation of risks that degrade decision-making. We present several methods to efficiently quantify these errors, by injecting subsampling, distributionally robust optimization, and random perturbation respectively into simulation runs. We explain the statistical mechanisms of these approaches and why they help resolve each of the discussed challenges faced by existing methods. This is joint work with Huajie Qian (Columbia).<--break->

Ricardo Fukasawa - University of Waterloo - January 13th 2020  

Associate Professor, Combinatorics and Optimization

MC 6460

2:15 p.m. refreshments | 2:30 p.m. talk

Solving the Vehicle Routing Problem

The vehicle routing problem (VRP) consists of finding the most efficient way to route a fleet of vehicles that depart from a common depot in order to serve a set of customers. Each customer has a given demand and the total demand carried by each vehicle cannot exceed its capacity. is The VRP is a well-studied classical combinatorial optimization problem proposed in 1959, and the techniques developed for solving it have been used to solve practical optimization problems in logistics and other application areas for years.


In this talk, we will discuss the VRP and different approaches to get optimal solutions to it. The approaches are based on integer programming formulations for the problem, each of which has its own advantages and drawbacks. We will review a few of these and discuss the main ideas behind them and how those can be extended to consider variants of the problem.