Month: September 2008

Mixed-Integer Models for Nonseparable Piecewise Linear Optimization: Unifying Framework and Extensions

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

    We study the modeling of non-convex piecewise linear functions as Mixed Integer Programming (MIP) problems. We review several new and existing MIP formulations for continuous piecewise linear functions with special attention paid to multivariate non-separable functions. We compare these formulations with respect to their theoretical properties and their relative computational performance. In addition, we study … Read more

    SESOP-TN: Combining Sequential Subspace Optimization with Truncated Newton method

  • Michael Zibulevsky
    • Categories Unconstrained Optimization Tags ,

    SESOP-TN is a method for very large scale unconstrained optimization of smooth functions. It combines ideas of Sequential Subspace Optimization (SESOP) [Narkiss-Zibulevsky-2005] with those of the Truncated Newton (TN) method . Replacing TN line search with subspace optimization, we allow Conjugate Gradient (CG) iterations to stay matched through consequent TN steps. This resolves the problem … Read more

    Detecting Critical Nodes in Sparse Graphs

  • Ashwin Arulselvan
  • Clayton W. Commander
  • Lily Elefteriadou
  • Panos M. Pardalos
    • Categories Combinatorial Optimization Tags , , ,

    Identifying critical nodes in a graph is important to understand the structural characteristics and the connectivity properties of the network. In this paper, we focus on detecting critical nodes, or nodes whose deletion results in the minimum pair-wise connectivity among the remaining nodes. This problem, known as the CRITICAL NODE PROBLEM has applications in several … Read more

    Implicitely and Densely Discrete Black-Box Optimization Problems

  • Luis Nunes Vicente
    • Categories Integer Programming, Nonlinear Optimization, Other Topics Tags , , , , , ,

    This paper addresses derivative-free optimization problems where the variables lie implicitly in an unknown discrete closed set. The evaluation of the objective function follows a projection onto the discrete set, which is assumed dense rather than sparse. Such a mathematical setting is a rough representation of what is common in many real-life applications where, despite … Read more

    PSwarm: A Hybrid Solver for Linearly Constrained Global Derivative-Free Optimization

  • A. Ismael F. Vaz
  • Luis Nunes Vicente
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Global Optimization Tags , , , , , , ,

    PSwarm was developed originally for the global optimization of functions without derivatives and where the variables are within upper and lower bounds. The underlying algorithm used is a pattern search method, more specifically a coordinate search method, which guarantees convergence to stationary points from arbitrary starting points. In the (optional) search step of coordinate search, … Read more

    A Linear Programming Approach for the Least-Squares Protein Morphing Problem

  • Mihai Anitescu
  • Sanghyun Park
    • Categories Approximation Algorithms, Basic Sciences Applications, Linear Programming Tags , , , ,

    This work addresses the computation of free-energy di fferences between protein conformations by using morphing (i.e., transformation) of a source conformation into a target conformation. To enhance the morph- ing procedure, we employ permutations of atoms; we transform atom n in the source conformation into atom \sigma(n) in the target conformation rather than directly transforming atom … Read more

    Strong Valid Inequalities for Orthogonal Disjunctions and 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 develop a convexification tool that enables the construction of convex hulls for orthogonal disjunctive sets using convex extensions and disjunctive programming techniques. A distinguishing feature of our technique is that, unlike most applications of disjunctive programming, it does not require the introduction of new variables in the relaxation. We develop and … Read more

    Python Optimization Modeling Objects (Pyomo)

  • William E. Hart
    • Categories Modeling Languages and Systems, Optimization Software Design Principles Tags , , ,

    We describe Pyomo, an open-source tool for modeling optimization applications in Python. Pyomo can be used to define abstract problems, create concrete problem instances, and solve these instances with standard solvers. Pyomo provides a capability that is commonly associated with algebraic modeling languages like AMPL and GAMS. Pyomo leverages the capabilities of the Coopr software, … Read more

    A Level-3 Reformulation-linearization Technique Based Bound for the Quadratic Assignment Problem

  • Monique Guignard
  • Peter M. Hahn
  • William L. Hightower
  • Yi-Rong Zhu
    • Categories 0-1 Programming, Combinatorial Optimization Tags , , , , ,

    We apply the level-3 Reformulation Linearization Technique (RLT3) to the Quadratic Assignment Problem (QAP). We then present our experience in calculating lower bounds using an essentially new algorithm, based on this RLT3 formulation. This algorithm is not guaranteed to calculate the RLT3 lower bound exactly, but approximates it very closely and reaches it in some … Read more

    Chance-constrained optimization via randomization: feasibility and optimality

  • Marco C. Campi
  • Simone Garatti
    • Categories Convex Optimization, Semi-infinite Programming, Stochastic Programming Tags , ,

    In this paper we study the link between a semi-infinite chance-constrained optimization problem and its randomized version, i.e. the problem obtained by sampling a finite number of its constraints. Extending previous results on the feasibility of randomized convex programs, we establish here the feasibility of the solution obtained after the elimination of a portion of … Read more