3 Presentations

• 
  03:30 PM - 03:55 PM

  Large scale taxi routing in Julia

  • Sébastien Martin, presenter, MIT
  • Dimitris Bertsimas, Massachusetts Institute of Technology
  • Patrick Jaillet, Massachusetts Institute of Technology

  We study the taxi-routing problem and solve large scale instances with real demand data using Julia. We combine scalable mixed-integer formulations, randomized heuristics and decision under uncertainty to optimize the routing decisions of Manhattan's yellow cabs. We explore the necessary trade-offs to extend traditional OR techniques to large instances with real demand data. All optimization formulations, data wrangling, algorithms and visualizations are coded in Julia.

• 
  03:55 PM - 04:20 PM

  Mixed-integer convex optimization

  • Miles Lubin, presenter, Massachusetts Institute of Technology
  • Emre Yamangil, Los Alamos National Laboratory
  • Russel Bent, Los Alamos National Laboratory
  • Christopher Coey, MIT ORC
  • Juan Pablo Vielma, MIT Sloan/ORC

  We present a new framework for mixed-integer convex optimization based on polyhedral outer approximation in an extended set of variables. The generation of extended formulations is automated based on the modeling framework of disciplined convex programming. This new approach has resulted in the solution of open benchmark instances from the MINLPLIB2 benchmark library. The solver, Pajarito, is implemented in Julia and was recently released as open-source software.

• 
  04:20 PM - 04:45 PM

  Optimal survey design: Nonconvex MINLP in Couenne vs. MIQCP reformulation in CPLEX

  • Christopher Coey, presenter, MIT ORC
  • Juan Pablo Vielma, MIT Sloan/ORC

  We propose and solve a novel optimal survey design model that integrates learning and optimization by implicitly modeling the 'exploration vs. exploitation' trade-off in this multistage adaptive setting. The natural formulation possesses nonconvex constraints with binary-continuous bilinear terms. Compounding the challenge of these nonconvex constraints, many of the bilinear terms are unbounded. This MINLP formulation can be given directly to Couenne, a global solver. However, by using McCormick linearizations on the bilinear terms, and clever techniques (which require a feasible solution) for bounding the unbounded variables, an MIQCP formulation can be solved with CPLEX. Alternatively, rather than searching for bounds and writing McCormick constraints, we could model the bilinear terms with CPLEX's 'indicator constraints', and tell CPLEX to use 'local implied bound cuts', a relatively new feature. We implement these three formulations in JuMP and compare performance.