Jean Pauphilet

The Surprising Performance of Random Partial Benders Decomposition

  • Jean Pauphilet
  • Yupeng Wu
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Stochastic Programming Tags ,

    Benders decomposition is a technique to solve large-scale mixed-integer optimization problems by decomposing them into a pure-integer master problem and a continuous separation subproblem. To accelerate convergence, we propose Random Partial Benders Decomposition (RPBD), a decomposition method that randomly retains a subset of the continuous variables within the master problem. Unlike existing problem-specific approaches, RPBD … Read more

    Operationalizing Experimental Design: Data Collection for Remote Ocean Monitoring

  • Jean Pauphilet
  • Baizhi Song
    • Categories (Mixed) Integer Nonlinear Programming, Statistics, Transportation Tags , , , ,

    Problem definition: To collect data on ocean plastic pollution and build more accurate predictive models, we need to manually take high-resolution pictures of the sea surface via floating or flying drones. Operating these vehicles, like many data collection problems in agriculture or environmental science, challenges the traditional optimal experimental design (OED) formulation from statistics by … Read more

    Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization

  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Semi-definite Programming

    Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-round strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, we derive a semidefinite relaxation and a randomized rounding scheme that obtains provably near-optimal solutions, building on the blueprint from Goemans and Williamson for the Max-Cut problem. … Read more

    Optimizing the Path Towards Plastic-Free Oceans

  • Dick den Hertog
  • Jean Pauphilet
  • Yannick Pham
  • Bruno Sainte-Rose
  • Baizhi Song
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Transportation Tags , , ,

    Increasing ocean plastic pollution is irreversibly harming ecosystems and human economic activities. We partner with a non-profit organization and use optimization to help clean up oceans from plastic faster. Specifically, we optimize the route of their plastic collection system in the ocean to maximize the quantity of plastic collected over time. We formulate the problem … Read more

    Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Sean Lo
  • Jean Pauphilet
    • Categories Data-Mining, Global Optimization Theory, Semi-definite Programming

    Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible. Unfortunately, existing methods for matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not possess any optimality guarantees. We reexamine matrix completion with an optimality-oriented eye. We reformulate … Read more

    A Stochastic Benders Decomposition Scheme for Large-Scale Stochastic Network Design

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
  • Periklis Petridis
    • Categories Cutting Plane Approaches, Network Optimization, Stochastic Programming Tags , ,

    Network design problems involve constructing edges in a transportation or supply chain network to minimize construction and daily operational costs. We study a stochastic version where operational costs are uncertain due to fluctuating demand and estimated as a sample average from historical data. This problem is computationally challenging, and instances with as few as  100 … Read more

    Sparse PCA With Multiple Components

  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories Data Science Theory, Data-Mining, Semi-definite Programming

    Sparse Principal Component Analysis (sPCA) is a cardinal technique for obtaining combinations of features, or principal components (PCs), that explain the variance of high-dimensional datasets in an interpretable manner. This involves solving a sparsity and orthogonality-constrained convex maximization problem, which is extremely computationally challenging. Most existing works address sparse PCA via methods—such as iteratively computing … Read more

    Minkowski Centers via Robust Optimization: Computation and Applications

  • Dick den Hertog
  • Jean Pauphilet
  • Mohamed Yahya Soali
    • Categories Robust Optimization Tags , , ,

    Centers of convex sets are geometric objects that have received extensive attention in the mathematical and optimization literature, both from a theoretical and practical standpoint. For instance, they serve as initialization points for many algorithms such as interior-point, hit-and-run, or cutting-planes methods. First, we observe that computing a Minkowski center of a convex set can be formulated as … Read more

    A new perspective on low-rank optimization

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , ,

    A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable convex relaxations. We invoke the matrix perspective function — the matrix analog of the perspective function — and characterize explicitly … Read more

    Hospital-wide Inpatient Flow Optimization

  • Dimitris Bertsimas
  • Jean Pauphilet
    • Categories Applications - OR and Management Sciences, Robust Optimization Tags , , ,

    To improve quality and delivery of care, operations need to be coordinated and optimized across all services in real-time. We propose a multi-stage adaptive robust optimization approach combined with machine learning techniques to achieve this goal. Informed by data and predictions, our framework unifies the bed assignment process across the entire hospital and accounts for … Read more