integer programming

Reformulations and Algorithms for the Optimization of Switching Decisions in Nonlinear Optimal Control

  • Sebastian Sager
    • Categories (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags , , ,

    In model-based nonlinear optimal control switching decisions that can be optimized often play an important role. Prominent examples of such hybrid systems are gear switches for transport vehicles or valves in chemical engineering. Optimization algorithms need to take the discrete nature of the variables that model these switching decisions into account. Unnecessarily, for many applications … Read more

    A Multistage Stochastic Programming Approach to Open Pit Mine Production Scheduling with Uncertain Geology

  • Natashia Boland
  • Gary Froyland
  • Irina Dumitrescu
    • Categories Applications - OR and Management Sciences, Integer Programming, Stochastic Programming Tags , , ,

    The Open Pit Mine Production Scheduling Problem (OPMPSP) studied in recent years is usually based on a single geological estimate of material to be excavated and processed over a number of decades. However techniques have now been developed to generate multiple stochastic geological estimates that more accurately describe the uncertain geology. While some attempts have … Read more

    Lattice-based Algorithms for Number Partitioning in the Hard Phase

  • Bala Krishnamoorthy
  • Nathan Moyer
  • William Webb
    • Categories Approximation Algorithms, Combinatorial Optimization, Integer Programming Tags , , ,

    The number partitioning problem (NPP) is to divide n numbers a_1,…,a_n into two disjoint subsets such that the difference between the two subset sums – the discrepancy, D, is minimized. In the balanced version of NPP (BalNPP), the subsets must have the same cardinality. With $a_j$s chosen uniformly from $[1,R]$, R > 2^n gives the … Read more

    Modeling and Solving Location Routing and Scheduling Problems

  • Z. Akca
  • Ted K. Ralphs
  • R.T. Berger
    • Categories 0-1 Programming, Network Optimization, Production and Logistics Tags , , ,

    This paper studies location routing and scheduling problems, a class of problems in which the decisions of facility location, vehicle routing, and route assignment are optimized simultaneously. For a version with capacity and time restrictions, two formulations are presented, one graph-based and one set-partitioning-based. For the set-partitioning-based formulation, valid inequalities are identified and their effectiveness … Read more

    On mixing inequalities: rank, closure and cutting plane proofs

  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    We study the mixing inequalities which were introduced by Gunluk and Pochet (2001). We show that a mixing inequality which mixes n MIR inequalities has MIR rank at most n if it is a type I mixing inequality and at most n-1 if it is a type II mixing inequality. We also show that these … Read more

    Improved strategies for branching on general disjunctions

  • Gérard Cornuéjols
  • Leo Liberti
  • Giacomo Nannicini
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags , ,

    Within the context of solving Mixed-Integer Linear Programs by a Branch-and-Cut algorithm, we propose a new strategy for branching. Computational experiments show that, on the majority of our test instances, this approach enumerates fewer nodes than traditional branching. On average, on instances that contain both integer and continuous variables the number of nodes in the … Read more

    Extended Formulations for Packing and Partitioning Orbitopes

  • Yuri Faenza
  • Volker Kaibel
    • Categories 0-1 Programming, Polyhedra Tags , ,

    We give compact extended formulations for the packing and partitioning orbitopes (with respect to the full symmetric group) described and analyzed in Kaibel and Pfetsch (Math. Program. 114 (1), 2008, 1-36). These polytopes are the convex hulls of all 0/1-matrices with lexicographically sorted columns and at most, resp. exactly, one 1-entry per row. They are … Read more

    A Branch-and-Price Algorithm for Combined Location and Routing Problems Under Capacity Restrictions

  • Z. Akca
  • Ted K. Ralphs
  • R.T. Berger
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Transportation Tags , , ,

    We investigate the problem of simultaneously determining the location of facilities and the design of vehicle routes to serve customer demands under vehicle and facility capacity restrictions. We present a set-partitioning-based formulation of the problem and study the relationship between his formulation and the graph-based formulations that have been used in previous studies of this … Read more

    Experiments with Branching using General Disjunctions

  • Ashutosh Mahajan
  • Ted K. Ralphs
    • Categories Integer Programming Tags , , ,

    Branching is an important component of the branch-and-cut algorithm for solving mixed integer linear programs. Most solvers branch by imposing a disjunction of the form“$x_i \leq k \vee x_i \geq k+1$” for some integer $k$ and some integer-constrained variable $x_i$. A generalization of this branching scheme is to branch by imposing a more general disjunction … Read more