(Mixed) Integer Nonlinear Programming

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

    An improved algorithm for computing Steiner minimal trees in Euclidean d-space

  • Kurt M. Anstreicher
  • Marcia Fampa
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , ,

    We describe improvements to Smith’s branch-and-bound (B&B) algorithm for the Euclidean Steiner problem in R^d. Nodes in the B&B tree correspond to full Steiner topologies associated with a subset of the terminal nodes, and branching is accomplished by “merging” a new terminal node with each edge in the current Steiner tree. For a given topology … Read more

    A Feasibility Pump for Mixed Integer Nonlinear Programs

  • Pierre Bonami
  • Gérard Cornuéjols
  • Andrea Lodi
  • François Margot
    • Categories (Mixed) Integer Nonlinear Programming Tags ,

    We present an algorithm for finding a feasible solution to a convex mixed integer nonlinear program. This algorithm, called Feasibility Pump, alternates between solving nonlinear programs and mixed integer linear programs. We also discuss how the algorithm can be iterated so as to improve the first solution it finds, as well as its integration 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

    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

    Compact linearization for bilinear mixed-integer problems

  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Scheduling Tags , ,

    We present a compact linearization for a broad class of bilinear 0-1 mixed-integer problems subject to assignment constraints. We apply the linearization to three classes of problems: quadratic assignment, multiprocessor scheduling with communication delays, and graph partitioning, and show that it yields faster solution times. CitationDEI, Politecnico di Milano, Working paper, April 2005.ArticleDownload View PDF

    In Situ Column Generation for a Cutting-Stock Problem

  • Jon Lee
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Production and Logistics Tags , ,

    Working with an integer bilinear programming formulation of a one-dimensional cutting-stock problem, we develop an ILP-based local-search heuristic. The ILPs holistically integrate the master and subproblem of the usual price driven pattern-generation paradigm, resulting in a unified model that generates new patterns in situ. We work harder to generate new columns, but we are guaranteed … Read more

    On generalized branching methods for mixed integer programming

  • Zhifeng Li
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , ,

    In this paper we present a restructuring of the computations in Lenstra’s methods for solving mixed integer linear programs. We show that the problem of finding a good branching hyperplane can be formulated on an adjoint lattice of the Kernel lattice of the equality constraints without requiring any dimension reduction. As a consequence the short … Read more

    Formulations and Valid Inequalities for the Heterogeneous Vehicle Routing Problem

  • Hande Yaman
    • Categories (Mixed) Integer Nonlinear Programming, Transportation Tags , , , ,

    We consider the vehicle routing problem where one can choose among vehicles with different costs and capacities to serve the trips. We develop six different formulations: the first four based on Miller-Tucker-Zemlin constraints and the last two based on flows. We compare the linear programming bounds of these formulations. We derive valid inequalities and lift … Read more

    A Piecewise Linearization Framework for Retail Shelf Space Management Models

  • Faiz Al-Khayyal
  • Jens Irion
  • J-C Lu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications, Marketing

    Managing shelf space is critical for retailers to attract customers and to optimize profit. This paper develops a shelf space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. The resultant model maximizes a signomial objective function over linear and bilinear constraints in mixed-integer variables. We propose a piecewise linearization … Read more