Integer Programming

Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints

  • Alberto Del Pia
  • Jeff Linderoth
  • Haoran Zhu
    • Categories 0-1 Programming, Cutting Plane Approaches, Global Optimization Tags , , , ,

    We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and generalizes the extended reformulation-linearization technique of Nguyen, Richard, and Tawarmalani to instances with general complementarity conditions between variables. We demonstrate … Read more

    Cutting-plane algorithm for sparse estimation of the Cox proportional-hazards model

  • Hiroki Saishu
  • Kota Kudo
  • Yuichi Takano
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Statistics Tags , , , , ,

    Survival analysis is a family of statistical methods for analyzing event occurrence times. In this paper, we address the mixed-integer optimization approach to sparse estimation of the Cox proportional-hazards model for survival analysis. Specifically, we propose a high-performance cutting-plane algorithm based on reformulation of bilevel optimization for sparse estimation. This algorithm solves the upper-level problem … Read more

    Markov Chain-based Policies for Multi-stage Stochastic Integer Linear Programming with an Application to Disaster Relief Logistics

  • Margarita P Castro
  • Merve Bodur
  • Yongjia Song
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    We introduce an aggregation framework to address multi-stage stochastic programs with mixed-integer state variables and continuous local variables (MSILPs). Our aggregation framework imposes additional structure to the integer state variables by leveraging the information of the underlying stochastic process, which is modeled as a Markov chain (MC). We demonstrate that the aggregated MSILP can be … Read more

    V-polyhedral disjunctive cuts

  • Egon Balas
  • Aleksandr M. Kazachkov
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , , ,

    We introduce V-polyhedral disjunctive cuts (VPCs) for generating valid inequalities from general disjunctions. Cuts are critical to integer programming solvers, but the benefit from many families is only realized when the cuts are applied recursively, causing numerical instability and “tailing off” of cut strength after several rounds. To mitigate these difficulties, the VPC framework offers … Read more

    Recursive McCormick Linearization of Multilinear Programs

  • Arvind U. Raghunathan
  • Carlos Cardonha
  • David Bergman
  • Carlos Nohra
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , ,

    Linear programming (LP) relaxations are widely employed in exact solution methods for multilinear programs (MLP). One example is the family of Recursive McCormick Linearization (RML) strategies, where bilinear products are substituted for artificial variables, which deliver a relaxation of the original problem when introduced together with concave and convex envelopes. In this article, we introduce … Read more

    Efficient composite heuristics for integer bound constrained noisy optimization

  • Morteza Kimiaei
  • Arnold Neumaier
    • Categories Bound-constrained Optimization, Integer Programming, Optimization Software Benchmark Tags , , , ,

    This paper discusses a composite algorithm for bound constrained noisy derivative-free optimization problems with integer variables. This algorithm is an integer variant of the matrix adaptation evolution strategy. An integer derivative-free line search strategy along affine scaling matrix directions is used to generate candidate points. Each affine scaling matrix direction is a product of the … Read more

    Dendrograms, Minimum Spanning Trees and Feature Selection

  • Martine LabbĂ©
  • Mercedes Landete
  • Marina Leal
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , ,

    Feature selection is a fundamental process to avoid overfitting and to reduce the size of databases without significant loss of information that applies to hierarchical clustering. Dendrograms are graphical representations of hierarchical clustering algorithms that for single linkage clustering can be interpreted as minimum spanning trees in the complete network defined by the database. In … Read more

    Maximizing resilience in large-scale social networks

  • Samuel Kroger
  • Hamidreza Validi
  • Illya V. Hicks
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , ,

    Motivated by the importance of social resilience as a crucial element in cascading leaving of users from a social network, we study identifying a largest relaxed variant of a degree-based cohesive subgraph: the maximum anchored k-core problem. Given graph G=(V,E) and integers k and b, the maximum anchored k-core problem seeks to find a largest … Read more

    Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump

  • Timo Berthold
  • Gioni Mexi
  • Domenico Salvagnin
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming Tags ,

    The Feasibility Pump (FP) is one of the best-known primal heuristics for mixed-integer programming (MIP): more than 15 papers suggested various modifications of all of its steps. So far, no variant considered information across multiple iterations, but all instead maintained the principle to optimize towards a single reference integer point. In this paper, we evaluate … Read more

    A Penalty Branch-and-Bound Method for Mixed-Integer Quadratic Bilevel Problems

  • Horländer Andreas
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities Tags , , ,

    We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of … Read more