3 présentations

• 
  08h30 - 08h52

  Recovering the Dantzig-Wolfe bound via Corner Benders Cuts

  • Matheus Jun Ota, prés., University of Waterloo
  • Ricardo Fukasawa, University of Waterloo
  • Aleksandr M. Kazachkov, University of Florida

  We introduce a novel technique that generates Benders cuts from a corner relaxation of the target higher-dimensional polyhedron. Moreover, we develop a computationally efficient method to separate facet-defining inequalities for the epigraph associated with this corner relaxation. By leveraging a known connection between arc-flow and path-flow formulations, we show that our method can recover the linear programming bound of a Dantzig-Wolfe formulation using multiple cuts in the projected space. We validate our approach with computational experiments on the vehicle routing problem with stochastic demands (VRPSD), a well-studied variant of the classic capacitated vehicle routing problem (CVRP) that accounts for customer demand uncertainty. Computational experiments show that, in some instances, our generic technique can enhance the performance of a problem-specific state-of-the-art algorithm for the VRPSD.

• 
  08h52 - 09h14

  LP Sampling for Improved MILP Analysis and Solution

  • John Chinneck, prés., Carleton University

  A new LP sampling heuristic can be helpful in two situations: (1) infeasible MILP: finding a minimal set of integer restrictions (IRs) causing infeasibility, and (2) feasible MILP: quickly finding an initial MILP-feasible or near-feasible solution. In case (1) most solvers do not attempt to isolate a minimal set of IRs because it takes a very long time, though this information is useful to the analyst. Doing so can also greatly speed up the isolation of the entire infeasibility (including linear constraints and variable bounds). The heuristic treats all variables as continuous and solves a number of LPs with varying objective function coefficients for the integer variables. This is often surprisingly useful in quickly reducing the original model in case (1) and quickly providing a MILP-feasible or near-feasible solution in case (2). Experimental results are provided.

• 
  09h14 - 09h36

  Tensor Completion via Integer Optimization

  • Kudva Sukanya, UC Berkeley
  • Anil Aswani, UC Berkeley
  • Jennifer Chen, UC Berkeley
  • Chen Chen, prés., The Ohio State University
  • Yongzheng Dai, The Ohio State University

  Tensor completion is a widely used machine learning model with applications ranging from multimodal data fusion to image processing. We develop a Frank-Wolfe-type approach that leverages integer programing (IP) to ensure global convergence towards minimum loss over a gauge-based tensor norm constraint. Although more computationally intensive that standard heuristic methods, our algorithm is the first practical method that can attain the information-theoretic limit in terms of data efficiency. The runtime is bottlenecked by IP solves, but our method uses a worst-case linear number of IP oracle calls and can avoid a large number of such calls in practice with a primal heuristic.