Integer Programming

A Lifted Linear Programming Branch-and-Bound Algorithm for Mixed Integer Conic Quadratic Programs

  • Shabbir Ahmed
  • George L. Nemhauser
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming

    This paper develops a linear programming based branch-and-bound algorithm for mixed integer conic quadratic programs. The algorithm is based on a higher dimensional or lifted polyhedral relaxation of conic quadratic constraints introduced by Ben-Tal and Nemirovski. The algorithm is different from other linear programming based branch-and-bound algorithms for mixed integer nonlinear programs in that, it … Read more

    Solving the uncapacitated facility location problem with semi-Lagrangian relaxation

  • Antonio Alonso-Ayuso
  • Cesar Beltran-Royo
  • Jean-Philippe Vial
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Convex Optimization Tags , ,

    The semi-Lagrangian Relaxation (SLR) method has been introduced in Beltran et al. (2006) to solve the p-median problem. In this paper we apply the method to the Uncapacitated Facility Location (UFL) problem. We perform computational experiments on two main collections of UFL problems with unknown optimal values. On one collection, we manage to solve to … Read more

    Lattice based extended formulations for integer linear equality systems

  • Karen I. Aardal
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming

    We study different extended formulations for the set $X =\{x\in\mathbb{Z}^n \mid Ax = Ax^0\}$ in order to tackle the feasibility problem for the set $X_+=X \cap \mathbb{Z}^n_+$. Here the goal is not to find an improved polyhedral relaxation of conv$(X_+)$, but rather to reformulate in such a way that the new variables introduced provide good … Read more

    Efficient Formulations for the Multi-Floor Facility Layout Problem with Elevators

  • Marc Goetschalckx
  • Takashi Irohara
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Production and Logistics Tags , , , ,

    The block layout problem for a multi-floor facility is an important sub class of the facility layout problem with practical applications when the price of land is high or when a compact building allows for more efficient environmental control. Several alternative formulations for the block layout problem of a multi-floor facility are presented, where the … Read more

    On a Generalization of the Master Cyclic Group Polyhedron

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

    We study the Master Equality Polyhedron (MEP) which generalizes the Master Cyclic Group Polyhedron and the Master Knapsack Polyhedron. We present an explicit characterization of the polar of the nontrivial facet-defining inequalities for the MEP. This result generalizes similar results for the Master Cyclic Group Polyhedron by Gomory (1969) and for the Master Knapsack Polyhedron … Read more

    Experiments in Robust Portfolio Optimization

  • Daniel Bienstock
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Robust Optimization Tags , , ,

    We present experimental results on portfolio optimization problems with return errors under the robust optimization framework. We use several a histogram-like model for return deviations, and a model that allows correlation among errors, together with a cutting-plane algorithm which proves effective for large, real-life data sets. Citation Columbia Center for Financial Engineering Report 2007-01 Columbia … Read more

    Simple Explicit Formula for Counting Lattice Points of Polyhedra

  • Jean-Bernard Lasserre
  • Eduardo Santillan Zeron
    • Categories Integer Programming, Polyhedra

    Given $z\in C^n$ and $A\in Z^{m\times n}$, we consider the problem of evaluating the counting function $h(y;z):=\sum\{z^x : x \in Z^n; Ax = y, x \geq 0\}$. We provide an explicit expression for $h(y;z)$ as well as an algorithm with possibly numerous but simple computations. In addition, we exhibit finitely many fixed convex cones of … Read more

    An Exact Solution Approach for Portfolio Optimization Problems under Stochastic and Integer Constraints

  • Pierre Bonami
  • Miguel A. Lejeune
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Stochastic Programming Tags , , ,

    In this paper, we study extensions of the classical Markowitz mean-variance portfolio optimization model. First, we consider that the expected asset returns are stochastic by introducing a probabilistic constraint which imposes that the expected return of the constructed portfolio must exceed a prescribed return threshold with a high confidence level. We study the deterministic equivalents … Read more

    MIP Reformulations of the Probabilistic Set Covering Problem

  • Vineet Goyal
  • Miguel A. Lejeune
  • Anureet Saxena
    • Categories 0-1 Programming, Cutting Plane Approaches, Stochastic Programming Tags , , ,

    In this paper we address the following probabilistic version (PSC) of the set covering problem: $min \{ cx \ |\ {\mathbb P} (Ax\ge \xi) \ge p,\ x_{j}\in \{0,1\}^N\}$ where $A$ is a 0-1 matrix, $\xi$ is a random 0-1 vector and $p\in (0,1]$ is the threshold probability level. We formulate (PSC) as a mixed integer … Read more

    The wireless network jamming problem

  • Clayton W. Commander
  • Panos M. Pardalos
  • Valeriy Ryabchenko
  • Stan Uryasev
  • Grigoriy Zrazhevsky
    • Categories Combinatorial Optimization, Integer Programming, Telecommunications Tags , , , ,

    In adversarial environments, disabling the communication capabilities of the enemy is a high priority. We introduce the problem of determining the optimal number and locations for a set of jamming devices in order to neutralize a wireless communication network. This problem is known as the WIRELESS NETWORK JAMMING PROBLEM. We develop several mathematical programming formulations … Read more