Integer Programming

Finding the best root node strategy for the approximation of the time-indexed bound in min-sum scheduling

  • Yunpeng Pan
  • Leyuan Shi
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization

    We identify the best root node strategy for the approximation of the time-indexed bound in min-sum scheduling by sorting through various options that involve the primal simplex, dual simplex, and barrier methods for linear programming, the network simplex method for network flow problems, and Dantzig-Wolfe decomposition and column generation. Citation Submitted for publication. Article Download … Read more

    Facets of Two-Dimensional Infinite Group Problems

  • Santanu S. Dey
  • Jean-Philippe P. Richard
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches

    In this paper, we lay the foundation for the study of the two-dimensional mixed integer infinite group problem (2DMIIGP). We introduce tools to determine if a given continuous and piecewise linear function over the two-dimensional infinite group is subadditive and to determine whether it defines a facet. We then present two different constructions that yield … Read more

    A new model and a computational study for Demand-wise Shared Protection

  • Claus G. Gruber
  • Arie M.C.A. Koster
  • Sebastian Orlowski
  • Adrian Zymolka
  • Roland Wessäly
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Telecommunications Tags , , ,

    This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within … Read more

    An algorithmic framework for convex mixed integer nonlinear programs

  • Lorenz T. Biegler
  • Pierre Bonami
  • Andrew R. Conn
  • Gérard Cornuéjols
  • Ignacio E. Grossmann
  • Carl D. Laird
  • Jon Lee
  • Andrea Lodi
  • François Margot
  • Nicolas Sawaya
    • Categories (Mixed) Integer Nonlinear Programming

    This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent … Read more

    A novel integer programming formulation for the K-SONET ring assignment problem

  • Elder M. Macambira
  • Claudio N. Meneses
  • Panos M. Pardalos
  • Mauricio G.C. Resende
    • Categories 0-1 Programming, Graphs and Matroids, Telecommunications Tags , , ,

    We consider the problem of interconnecting a set of customer sites using SONET rings of equal capacity, which can be defined as follows: Given an undirected graph G=(V,E) with nonnegative edge weight d(u,v), (u,v) in E, and two integers K and B, find a partition of the nodes of G into K subsets so that … Read more

    A special ordered set approach to discontinuous piecewise linear optimization

  • Ismael de Farias
  • Ming Zhao
  • Hongxia Zhao
    • Categories Integer Programming Tags , , ,

    Piecewise linear functions (PLFs) are commonly used to approximate nonlinear functions. They are also of interest in their own, arising for example in problems with economies of scale. Early approaches to piecewise linear optimization (PLO) assumed continuous PLFs. They include the incremental cost MIP model of Markowitz and Manne and the convex combination MIP model … Read more

    A Near Maximum Likelihood Decoding Algorithm for MIMO Systems Based on Semi-Definite Programming

  • Amir K. Khandani
  • Amin Mobasher
  • Renata Sotirov
  • Mahmoud Taherzadeh
    • Categories 0-1 Programming, Quadratic Programming, Telecommunications Tags , , , ,

    In Multi-Input Multi-Output (MIMO) systems, Maximum-Likelihood (ML) decoding is equivalent to finding the closest lattice point in an N-dimensional complex space. In general, this problem is known to be NP hard. In this paper, we propose a quasi-maximum likelihood algorithm based on Semi-Definite Programming (SDP). We introduce several SDP relaxation models for MIMO systems, with … Read more

    The polar of a simple mixed-integer set

  • Ismael de Farias
  • Ming Zhao
    • Categories Integer Programming Tags , , , ,

    We study the convex hull $P$ of the set $S = \{(x, y) \in \Re_{+} \times Z^{n}: x + B_{i} y_{ij} \geq b_{ij}, j \in N_{i}, i \in M\}$, where $M = \{1, \ldots, m\}$, $N_{i} = \{1, \ldots, n_{i}\}$ $\forall i \in M$, $\sum_{i = 1}^{m}n_{i} = n$, and $B_{1} | \cdots | B_{m}$. … Read more

    Clustering via Minimum Volume Ellipsoids

  • Romy Shioda
  • Levent Tunçel
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining, Semi-definite Programming

    We propose minimum volume ellipsoids (MVE) clustering as an alternate clustering technique to k-means clustering for Gaussian data points and explore its value and practicality. MVE clustering allocates data points into clusters that minimizes the total volumes of each cluster’s covering ellipsoids. Motivations for this approach include its scale-invariance, its ability to handle asymmetric and … Read more

    An Explicit Semidefinite Characterization of Satisfiability for Tseitin Instances

  • Miguel F. Anjos
    • Categories 0-1 Programming, Basic Sciences Applications, Semi-definite Programming Tags , , , ,

    This paper is concerned with the application of semidefinite programming to the satisfiability problem, and in particular with using semidefinite liftings to efficiently obtain proofs of unsatisfiability. We focus on the Tseitin satisfiability instances which are known to be hard for many proof systems. We present an explicit semidefinite programming problem with dimension linear in … Read more