Jeff Linderoth

Regularization vs. Relaxation: A convexification perspective of statistical variable selection

  • Kun Chen
  • Hongbo Dong
  • Jeff Linderoth
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Statistics Tags , , ,

    Variable selection is a fundamental task in statistical data analysis. Sparsity-inducing regularization methods are a popular class of methods that simultaneously perform variable selection and model estimation. The central problem is a quadratic optimization problem with an $\ell_0$-norm penalty. Exactly enforcing the $\ell_0$-norm penalty is computationally intractable for larger scale problems, so different sparsity-inducing penalty … Read more

    Quadratic Cone Cutting Surfaces for Quadratic Programs with On-Off Constraints

  • Hyemin Jeon
  • Jeff Linderoth
  • Andrew J. Miller
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming

    We study the convex hull of a set arising as a relaxation of difficult convex mixed integer quadratic programs (MIQP). We characterize the extreme points of our set and the extreme points of its continuous relaxation. We derive four quadratic cutting surfaces that improve the strength of the continuous relaxation. Each of the cutting surfaces … Read more

    A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching

  • Santanu S. Dey
  • Hyemin Jeon
  • Burak Kocuk
  • Jeff Linderoth
  • James R. Luedtke
  • Xu Andy Sun
    • Categories Applications - Science and Engineering, Integer Programming Tags , ,

    It is well-known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. In fact, the USA Energy Policy Act of 2005 (Section 1223) states that the U.S. should “encourage, as appropriate, the deployment of advanced transmission technologies” including “optimized transmission line configurations”. As such, … Read more

    Validating Sample Average Approximation Solutions with Negatively Dependent Batches

  • Jiajie Chen
  • Cong Han Lim
  • Jeff Linderoth
  • Peter Qian
  • Stephen Wright
    • Categories Stochastic Programming

    Sample-average approximations (SAA) are a practical means of finding approximate solutions of stochastic programming problems involving an extremely large (or infinite) number of scenarios. SAA can also be used to find estimates of a lower bound on the optimal objective value of the true problem which, when coupled with an upper bound, provides confidence intervals … Read more

    Models and Solution Techniques for Production Planning Problems with Increasing Byproducts

  • Jeff Linderoth
  • James R. Luedtke
  • Srikrishna Sridhar
    • Categories Applications - OR and Management Sciences, Chemical Engineering, Facility Planning and Design Tags , ,

    We consider a production planning problem where the production process creates a mixture of desirable products and undesirable byproducts. In this production process, at any point in time the fraction of the mixture that is an undesirable byproduct increases monotonically as a function of the cumulative mixture production up to that time. The mathematical formulation … Read more

    Locally Ideal Formulations for Piecewise Linear Functions with Indicator Variables

  • Jeff Linderoth
  • James R. Luedtke
  • Srikrishna Sridhar
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering

    In this paper, we consider mixed integer linear programming (MIP) formulations for piecewise linear functions (PLFs) that are evaluated when an indicator variable is turned on. We describe modifications to standard MIP formulations for PLFs with desirable theoretical properties and superior computational performance in this context. Citation Technical Report #1788, Computer Sciences Department, University of … Read more

    Mixed-Integer Nonlinear Optimization

  • Pietro Belotti
  • Christian Kirches
  • Sven Leyffer
  • Jeff Linderoth
  • James R. Luedtke
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Many optimal decision problems in scientific, engineering, and public sector applications involve both discrete decisions and nonlinear system dynamics that affect the quality of the final design or plan. These decision problems lead to mixed-integer nonlinear programming (MINLP) problems that combine the combinatorial difficulty of optimizing over discrete variable sets with the challenges of handling … Read more

    On valid inequalities for quadratic programming with continuous variables and binary indicators

  • Hongbo Dong
  • Jeff Linderoth
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Quadratic Programming Tags ,

    In this paper we study valid inequalities for a fundamental set that involves a continuous vector variable x in [0,1]^n, its associated quadratic form x x’ and its binary indicators. This structure appears when deriving strong relaxations for mixed integer quadratic programs (MIQPs). We treat valid inequalities for this set as lifted from QPB, which … Read more

    Strong Branching Inequalities for Convex Mixed Integer Nonlinear Programs

  • Mustafa Kilinc
  • Jeff Linderoth
  • James R. Luedtke
  • Andrew J. Miller
    • Categories (Mixed) Integer Nonlinear Programming

    Strong branching is an effective branching technique that can significantly reduce the size of the branch-and-bound tree for solving Mixed Integer Nonlinear Programming (MINLP) problems. The focus of this paper is to demonstrate how to effectively use discarded information from strong branching to strengthen relaxations of MINLP problems. Valid inequalities such as branching-based linearizations, various … Read more

    A Probing Algorithm for MINLP with Failure Prediction by SVM

  • Pietro Belotti
  • Jon Lee
  • Jeff Linderoth
  • Giacomo Nannicini
  • François Margot
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization

    Bound tightening is an important component of algorithms for solving nonconvex Mixed Integer Nonlinear Programs. A {\em probing} algorithm is a bound-tightening procedure that explores the consequences of restricting a variable to a subinterval with the goal of tightening its bounds. We propose a variant of probing where exploration is based on iteratively applying a … Read more