Integer Programming

On n-step MIR and Partition Inequalities for Integer Knapsack and Single-node Capacitated Flow Sets

  • Kiavash Kianfar
    • Categories (Mixed) Integer Linear Programming

    Pochet and Wolsey [Y. Pochet, L.A. Wolsey, Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation. Discrete Applied Mathematics 59(1995) 57-74] introduced partition inequalities for three substructures arising in various mixed integer programs, namely the integer knapsack set with nonnegative divisible/arbitrary coefficients and two forms of single-node capacitated flow set with divisible … Read more

    Solution Methods for the Multi-trip Elementary Shortest Path Problem with Resource Constraints

  • Z. Akca
  • Ted K. Ralphs
  • R.T. Berger
    • Categories 0-1 Programming, Combinatorial Optimization, Transportation Tags , ,

    We investigate the multi-trip elementary shortest path problem (MESPPRC) with resource constraints in which the objective is to find a shortest path between a source node and a sink node such that nodes other than the specified replenishment node are visited at most once and resource constraints are not violated. After each visit to the … Read more

    A Chance-Constrained Model & Cutting Planes for Fixed Broadband Wireless Networks

  • Grit Claßen
  • Arie M.C.A. Koster
  • David Coudert
  • Napoleao Nepomuceno
    • Categories Cutting Plane Approaches, Robust Optimization, Telecommunications Tags , , ,

    In this paper, we propose a chance-constrained mathematical program for fixed broadband wireless networks under unreliable channel conditions. The model is reformulated as integer linear program and valid inequalities are derived for the corresponding polytope. Computational results show that by an exact separation approach the optimality gap is closed by 42 % on average. ArticleDownload … Read more

    A Dynamic Inequality Generation Scheme for Polynomial Programming

  • Miguel F. Anjos
  • Bissan Ghaddar
  • Juan C. Vera
    • Categories 0-1 Programming, Semi-definite Programming Tags , ,

    Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves … Read more

    Lifted Inequalities for 0−1 Mixed-Integer Bilinear Covering Sets

  • Kwanghun Chung
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Theory Tags , ,

    In this paper, we study 0-1 mixed-integer bilinear covering sets. We derive several families of facet-defining inequalities via sequence-independent lifting techniques. We then show that these sets have polyhedral structures that are similar to those of certain fixed-charge single-node flow sets. As a result, we obtain new facet-defining inequalities for these sets that generalize well-known … Read more

    Recoverable Robust Knapsacks: $\GammahBcScenarios

  • Christina Büsing
  • Arie M.C.A. Koster
  • Manuel Kutschka
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , , ,

    In this paper, we investigate the recoverable robust knapsack problem, where the uncertainty of the item weights follows the approach of Bertsimas and Sim (2003,2004). In contrast to the robust approach, a limited recovery action is allowed, i.e., upto k items may be removed when the actual weights are known. This problem is motivated by … Read more

    Recoverable Robust Knapsack: the Discrete Scenario Case

  • Christina Büsing
  • Arie M.C.A. Koster
  • Manuel Kutschka
    • Categories Cutting Plane Approaches, Polyhedra, Robust Optimization Tags , , ,

    Admission control problems have been studied extensively in the past. In a typical setting, resources like bandwidth have to be distributed to the different customers according to their demands maximizing the profit of the company. Yet, in real-world applications those demands are deviating and in order to satisfy their service requirements often a robust approach … Read more

    Bound reduction using pairs of linear inequalities

  • Pietro Belotti
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization Tags , , ,

    We describe a procedure to reduce variable bounds in Mixed Integer Nonlinear Programming (MINLP) as well as Mixed Integer Linear Programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction technique extends the implied bounds procedure used in MINLP and MILP and … Read more

    Dippy — a simplified interface for advanced mixed-integer programming

  • Iain Dunning
  • Stuart Mitchell
  • Cameron Walker
  • Qi-Shan Lim
  • Michael O'Sullivan
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Modeling Languages and Systems

    Mathematical modelling languages such as AMPL, GAMS, and Xpress-MP enable mathematical models such as mixed-integer linear programmes (MILPs) to be expressed clearly for solution in solvers such as CPLEX, MINOS and Gurobi. However some models are sufficiently difficult that they cannot be solved using “out-of-the-box” solvers, and customisation of the solver framework to exploit model-specific … Read more

    A compact variant of the QCR method for quadratically constrained quadratic 0-1 programs

  • Laura Galli
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming

    Quadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0-1 programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible. In … Read more