Integer Programming

Optimal Cross-Validation for Sparse Linear Regression

  • Ryan Cory-Wright
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Algorithms

    Given a high-dimensional covariate matrix and a response vector, ridge-regularized sparse linear regression selects a subset of features that explains the relationship between covariates and the response in an interpretable manner. To choose hyperparameters that control the sparsity level and amount of regularization, practitioners commonly use k-fold cross-validation. However, cross-validation substantially increases the computational cost … Read more

    Distributionally Risk-Receptive and Robust Multistage Stochastic Integer Programs and Interdiction Models

  • Sumin Kang
  • Manish Bansal
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization, Stochastic Programming Tags , , , , , ,

    In this paper, we study distributionally risk-receptive and distributionally robust (or risk-averse) multistage stochastic mixed-integer programs (denoted by DRR- and DRO-MSIPs). We present cutting plane-based and reformulation-based approaches for solving DRR- and DRO-MSIPs without and with decision-dependent uncertainty to optimality. We show that these approaches are finitely convergent with probability one. Furthermore, we introduce generalizations … Read more

    Using dual relaxations in multiobjective mixed-integer quadratic programming

  • Marianna De Santis
  • Gabriele Eichfelder
  • Daniele Patria
  • Leo Warnow
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , , ,

    We present a branch-and-bound method for multiobjective mixed-integer convex quadratic programs that computes a superset of efficient integer assignments and a coverage of the nondominated set. The method relies on outer approximations of the upper image set of continuous relaxations. These outer approximations are obtained addressing the dual formulations of specific subproblems where the values … Read more

    Mixed-Integer Programming for a Class of Robust Submodular Maximization Problems

  • Hsin-Yi Huang
  • Hao-Hsiang Wu
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Stochastic Programming

    We consider robust submodular maximization problems (RSMs), where given a set of \(m\) monotone submodular objective functions, the robustness is with respect to the worst-case (scaled) objective function. The model we consider generalizes two variants of robust submodular maximization problems in the literature, depending on the choice of the scaling vector. On one hand, by using … Read more

    Compressed Sensing: A Discrete Optimization Approach

  • Dimitris Bertsimas
  • Nicholas A. G. Johnson
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming, Statistics Tags , , , ,

    We study the Compressed Sensing (CS) problem, which is the problem of finding the most sparse vector that satisfies a set of linear measurements up to some numerical tolerance. CS is a central problem in Statistics, Operations Research and Machine Learning which arises in applications such as signal processing, data compression, image reconstruction, and multi-label … Read more

    Outlier detection in regression: conic quadratic formulations

  • Andrés Gómez
  • José Neto
    • Categories (Mixed) Integer Nonlinear Programming, Statistics Tags , , ,

    In many applications, when building linear regression models, it is important to account for the presence of outliers, i.e., corrupted input data points. Such problems can be formulated as mixed-integer optimization problems involving cubic terms, each given by the product of a binary variable and a quadratic term of the continuous variables. Existing approaches in … Read more

    Democratization of Complex-Problem Solving: Toward Privacy-Aware, Transparent and Inclusive Optimization

  • Mikhail Bragin
  • Karmel S. Shehadeh
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags , , , , , ,

    Critical operations often involve stakeholders with diverse perspectives, yet centralized optimization assumes participation or private information, neither of which is a priori guaranteed. Additionally, decision-making involves discrete decisions, making optimization computationally challenging. Centralized formulations use approximations to manage complexity, often overlooking stakeholder perspectives, leading to bias. To resolve these challenges, we adopt a privacy-aware participatory-distributed … Read more

    Political districting to optimize the Polsby-Popper compactness score with application to voting rights

  • Pietro Belotti
  • Austin Buchanan
  • Soraya Ezazipour
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Integer Programming Tags , ,

    In the academic literature and in expert testimony, the Polsby-Popper score is the most popular way to measure the compactness of a political district. Given a district with area \(A\) and perimeter \(P\), its Polsby-Popper score is given by \( (4 \pi A)/P^2\). This score takes values between zero and one, with circular districts achieving … Read more

    On the Partial Convexification of the Low-Rank Spectral Optimization: Rank Bounds and Algorithms

  • Yongchun Li
  • Weijun Xie
    • Categories Integer Programming Tags , , , ,

    A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective subject to multiple two-sided linear matrix inequalities intersected with a low-rank and spectral constrained domain set. Although solving LSOP is, in general, NP-hard, its partial convexification (i.e., replacing the domain set by its convex hull) termed “LSOP-R”, is often tractable and yields a high-quality solution. … Read more

    When Deep Learning Meets Polyhedral Theory: A Survey

  • Joey Huchette
  • Gonzalo Muñoz
  • Thiago Serra
  • Calvin Tsay
    • Categories (Mixed) Integer Linear Programming, Optimization in Data Science, Polyhedra

    In the past decade, deep learning became the prevalent methodology for predictive modeling thanks to the remarkable accuracy of deep neural networks in tasks such as computer vision and natural language processing. Meanwhile, the structure of neural networks converged back to simpler representations based on piecewise constant and piecewise linear functions such as the Rectified … Read more