Integer Programming

Derivative-free Methods for Mixed-Integer Constrained Optimization Problems

  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Constrained Nonlinear Optimization

    Methods which do not use any derivative information are becoming popular among researchers, since they allow to solve many real-world engineering problems. Such problems are frequently characterized by the presence of discrete variables which can further complicate the optimization process. In this paper, we propose derivative-free algorithms for solving continuously differentiable Mixed Integer NonLinear Programming … Read more

    Decomposition Algorithms for Two-Stage Chance-Constrained Programs

  • Simge Küçükyavuz
  • James R. Luedtke
  • Xiao Liu
    • Categories Branch and Cut Algorithms, Integer Programming, Stochastic Programming Tags , , ,

    We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. In addition, we propose a new model, where “recovery” decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve … Read more

    Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse

  • Merve Bodur
  • Sanjeeb Dash
  • Oktay Gunluk
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Stochastic Programming Tags , ,

    With stochastic integer programming as the motivating application, we investigate techniques to use integrality constraints to obtain improved cuts within a Benders decomposition algorithm. We compare the effect of using cuts in two ways: (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are then used … Read more

    Deriving the convex hull of a polynomial partitioning set through lifting and projection

  • Trang T. Nguyen
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , ,

    Relaxations of the bilinear term, $x_1x_2=x_3$, play a central role in constructing relaxations of factorable functions. This is because they can be used directly to relax products of functions with known relaxations. In this paper, we provide a compact, closed-form description of the convex hull of this and other more general bivariate monomial terms (which … Read more

    Generating subtour constraints for the TSP from pure integer solutions

  • Ulrich Pferschy
  • Rostislav Stanek
    • Categories Combinatorial Optimization, Integer Programming Tags , ,

    The traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph G = (V, E) and nonnegative real edge distances d, the TSP asks for a shortest tour through all vertices with respect to the distances d. The method of choice for solving the TSP to optimality is … Read more

    A Trust Region Method for the Solution of the Surrogate Dual in Integer Programming

  • Natashia Boland
  • Andrew C. Eberhard
  • Angelos Tsoukalas
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Nonsmooth Optimization Tags , ,

    We propose an algorithm for solving the surrogate dual of a mixed integer program. The algorithm uses a trust region method based on a piecewise affine model of the dual surrogate value function. A new and much more flexible way of updating bounds on the surrogate dual’s value is proposed, which numerical experiments prove to … Read more

    Polyhedral Approximation of Ellipsoidal Uncertainty Sets via Extended Formulations – a computational case study –

  • Andreas Bärmann
  • Andreas Heidt
  • Sebastian Pokutta
  • Alexander Martin
  • Christoph Thurner
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Second-Order Cone Programming Tags , , ,

    Robust optimization is an important technique to immunize optimization problems against data uncertainty. In the case of a linear program and an ellipsoidal uncertainty set, the robust counterpart turns into a second-order cone program. In this work, we investigate the efficiency of linearizing the second-order cone constraints of the latter. This is done using the … Read more

    Decomposition Algorithm for Optimizing Multi-server Appointment Scheduling with Chance Constraints

  • Yan Deng
  • Siqian Shen
    • Categories Cutting Plane Approaches, Stochastic Programming

    We schedule appointments with random service durations on multiple servers with operating time limits. We minimize the costs of operating servers and serving appointments, subject to a joint chance constraint limiting the risk of server overtime. Using finite samples of the uncertainty, we formulate the problem as a mixed-integer linear program, and propose a two-stage … Read more

    The continuous knapsack set

  • Sanjeeb Dash
  • Oktay Gunluk
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming Tags ,

    We study the convex hull of the continuous knapsack set which consists of a single inequality constraint with n non-negative integer and m non-negative bounded continuous variables. When n = 1, this set is a slight generalization of the single arc flow set studied by Magnanti, Mirchandani, and Vachani (1993). We first show that in … Read more

    Subset Selection by Mallows’ Cp: A Mixed Integer Programming Approach

  • Ryuhei Miyashiro
  • Yuichi Takano
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Statistics Tags , , ,

    This paper concerns a method of selecting the best subset of explanatory variables for a linear regression model. Employing Mallows’ C_p as a goodness-of-fit measure, we formulate the subset selection problem as a mixed integer quadratic programming problem. Computational results demonstrate that our method provides the best subset of variables in a few seconds when … Read more