Integer Programming

Mixed-Integer Quadratic Optimization and Iterative Clustering Techniques for Semi-Supervised Support Vector Machines

  • Martin Schmidt
  • Jan Pablo Burgard
  • Maria Eduarda Pinheiro
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Algorithms, Data Science Applications Tags , , ,

    Among the most famous algorithms for solving classification problems are support vector machines (SVMs), which find a separating hyperplane for a set of labeled data points. In some applications, however, labels are only available for a subset of points. Furthermore, this subset can be non-representative, e.g., due to self-selection in a survey. Semi-supervised SVMs tackle … Read more

    Safe and Verified Gomory Mixed Integer Cuts in a Rational MIP Framework

  • Leon Eifler
  • Ambros Gleixner
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably … 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

    An approximation algorithm for multi-objective mixed-integer convex optimization

  • Ina Lammel
  • Karl-Heinz Küfer
  • Philipp Süss
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , ,

    In this article we introduce an algorithm that approximates Pareto fronts of multiobjective mixed-integer convex optimization problems. The algorithm constructs an inner and outer approximation of the front exploiting the convexity of the patches and is applicable to problems with an arbitrary number of criteria. In the algorithm, the problem is decomposed into patches, which … Read more

    Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Semi-definite Programming Tags , , , ,

    We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator \( \text{LS}_+\), with a particular focus on a search for relatively small graphs with high \( \text{LS}_+\)-rank (the least number of iterations of the \( \text{LS}_+\) operator on the fractional stable set polytope to compute the … Read more

    Column Elimination for Capacitated Vehicle Routing Problems

  • Anthony Karahalios
  • Willem-Jan van Hoeve
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Dynamic Programming Tags , , ,

    We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more

    Evaluation of Political Redistricting in Japan by Optimization and Enumeration

  • Keisuke Hotta
  • Jun Kawahara
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , ,

    The political/electoral districting problem for the single-seat constituency system is a problem of decomposing a graph into connected components of a given number of seats under several conditions and objectives. We evaluate and analyze the current division of single-seat constituencies for the House of Representatives using optimization and enumeration. The objective function is to minimize … Read more

    On Supervalid Inequalities for Binary Interdiction Games

  • Ningji Wei
  • Jose L. Walteros
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Integer Programming Tags , , ,

    Supervalid inequalities are a specific type of constraints often used within the branch-and-cut framework to strengthen the linear relaxation of mixed-integer programs. These inequalities share the particular characteristic of potentially removing feasible integer solutions as long as they are already dominated by an incumbent solution. This paper focuses on supervalid inequalities for solving binary interdiction … Read more

    Submodular maximization and its generalization through an intersection cut lens

  • Liding Xu
  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , , , ,

    We study a mixed-integer set \(\mathcal{S}:=\{(x,t) \in \{0,1\}^n \times \mathbb{R}: f(x) \ge t\}\) arising in the submodular maximization problem, where \(f\) is a submodular function defined over \(\{0,1\}^n\). We use intersection cuts to tighten a polyhedral outer approximation of \(\mathcal{S}\). We construct a continuous extension \(\mathsf{F}\) of \(f\), which is convex and defined over the … Read more

    Monoidal Strengthening of Simple V-Polyhedral Disjunctive Cuts

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

    Disjunctive cutting planes can tighten a relaxation of a mixed-integer linear program. Traditionally, such cuts are obtained by solving a higher-dimensional linear program, whose additional variables cause the procedure to be computationally prohibitive. Adopting a V-polyhedral perspective is a practical alternative that enables the separation of disjunctive cuts via a linear program with only as … Read more