Integer Programming

A Penalized Quadratic Convex Reformulation Method for Random Quadratic Unconstrained Binary Optimization

  • Karthik Natarajan
  • Kim-Chuan Toh
  • Dongjian Shi
    • Categories 0-1 Programming, Stochastic Approaches Tags , ,

    The Quadratic Convex Reformulation (QCR) method is used to solve quadratic unconstrained binary optimization problems. In this method, the semidefinite relaxation is used to reformulate it to a convex binary quadratic program which is solved using mixed integer quadratic programming solvers. We extend this method to random quadratic unconstrained binary optimization problems. We develop a … Read more

    A Mixed Integer Nonlinear Programming Framework for Fixed Path Coordination of Multiple Underwater Vehicles under Acoustic Communication Constraints

  • Pramod Abichandani
  • Hande Benson
  • Shambadeb Basu
  • Solmaz Torabi
    • Categories (Mixed) Integer Nonlinear Programming, Control Applications, Telecommunications Tags , , ,

    Mixed Integer Nonlinear Programming (MINLP) techniques are increasingly used to address challenging problems in robotics, especially Multi-Vehicle Motion Planning (MVMP). The main contribution of this paper is a discrete time-distributed Receding Horizon Mixed Integer Nonlinear Programming (RH-MINLP) formulation of the underwater multi-vehicle path coordination problem with constraints on kinematics, dynamics, collision avoidance, and acoustic communication … Read more

    Closedness of Integer Hulls of Simple Conic Sets

  • Santanu S. Dey
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    Let $C$ be a full-dimensional pointed closed convex cone in $R^m$ obtained by taking the conic hull of a strictly convex set. Given $A \in Q^{m \times n_1}$, $B \in Q^{m \times n_2}$ and $b \in Q^m$, a simple conic mixed-integer set (SCMIS) is a set of the form $\{(x,y)\in Z^{n_1} \times R^{n_2}\,|\,\ Ax +By … Read more

    Using diversification, communication and parallelism to solve mixed-integer linear programs

  • Shabbir Ahmed
  • Rodolfo Carvajal
  • Kevin C Furman
  • George L. Nemhauser
  • Vikas Goel
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Optimization Software and Modeling Systems, Parallel Algorithms Tags , , , , ,

    Performance variability of modern mixed-integer programming solvers and possible ways of exploiting this phenomenon present an interesting opportunity in the development of algorithms to solve mixed-integer linear programs (MILPs). We propose a framework using multiple branch-and-bound trees to solve MILPs while allowing them to share information in a parallel execution. We present computational results on … Read more

    Cutting-planes for optimization of convex functions over nonconvex sets

  • Daniel Bienstock
  • Alexander Michalka
    • Categories (Mixed) Integer Nonlinear Programming, Convex and Nonsmooth Optimization, Cutting Plane Approaches Tags ,

    Motivated by mixed-integer, nonlinear optimization problems, we derive linear inequality characterizations for sets of the form conv{(x, q ) \in R^d × R : q \in Q(x), x \in R^d – int(P )} where Q is convex and differentiable and P \subset R^d . We show that in several cases our characterization leads to polynomial-time … Read more

    A Strong Preemptive Relaxation for Weighted Tardiness and Earliness/Tardiness Problems on Unrelated Parallel Machines

  • Kerem Bülbül
  • Halil Sen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Scheduling

    Research on due date oriented objectives in the parallel machine environment is at best scarce compared to objectives such as minimizing the makespan or the completion time related performance measures. Moreover, almost all existing work in this area is focused on the identical parallel machine environment. In this study, we leverage on our previous work … Read more

    Analysis of MILP Techniques for the Pooling Problem

  • Santanu S. Dey
  • Akshay Gupte
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Global Optimization Tags , , , , ,

    The $pq$-relaxation for the pooling problem can be constructed by applying McCormick envelopes for each of the bilinear terms appearing in the so-called $pq$-formulation of the pooling problem. This relaxation can be strengthened by using piecewise-linear functions that over- and under-estimate each bilinear term. The resulting relaxation can be written as a mixed integer linear … Read more

    Acceleration and Stabilization Techniques for Column Generation Applied to Capacitated Resource Management Problems

  • Alper Uygur
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Scheduling Tags , , ,

    This research presents a very efficient method of solving a broad class of large-scale capacitated resource management problems by introducing a new formulation and decomposition. A heuristic called Likelihood of Assignment is utilized not only to find high quality initial integer feasible solutions, but also to guide the Branch-and-Price (B&P) Algorithm towards stabilization. Although Column … Read more

    REDUCTION OF TWO-STAGE PROBABILISTIC OPTIMIZATION PROBLEMS WITH DISCRETE DISTRIBUTION OF RANDOM DATA TO MIXED INTEGER PROGRAMMING PROBLEMS

  • Andrey Kibzun
  • Vladimir I. Norkin
  • Andrey Naumov
    • Categories (Mixed) Integer Nonlinear Programming, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    We consider models of two-stage stochastic programming with a quantile second stage criterion and optimization models with a chance constraint on the second stage objective function values. Such models allow to formalize requirements to reliability and safety of the system under consideration, and to optimize the system in extreme conditions. We suggest a method of … Read more

    Locally Ideal Formulations for Piecewise Linear Functions with Indicator Variables

  • Jeff Linderoth
  • James R. Luedtke
  • Srikrishna Sridhar
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering

    In this paper, we consider mixed integer linear programming (MIP) formulations for piecewise linear functions (PLFs) that are evaluated when an indicator variable is turned on. We describe modifications to standard MIP formulations for PLFs with desirable theoretical properties and superior computational performance in this context. Citation Technical Report #1788, Computer Sciences Department, University of … Read more