Month: August 2008

Necessary Conditions for the Impulsive Optimal Control of Multibody Mechanical Systems

  • Kerim Yunt
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization Tags , , , ,

    In this work, necessary conditions for the impulsive optimal control of multibody mechanical systems are stated. The conditions are obtained by the application subdifferential calculus techniques to extended-valued lower semi-continuous generalized Bolza functional that is evaluated on multiple intervals. Contrary to the approach in literature so far, the instant of possibly impulsive transition is considered … Read more

    Dynamic Subgradient Methods

  • Grégory Emiel
  • Claudia Sagastizábal
    • Categories Cutting Plane Approaches, Nonsmooth Optimization

    Lagrangian relaxation is commonly used to generate bounds for mixed-integer linear programming problems. However, when the number of dualized constraints is very large (exponential in the dimension of the primal problem), explicit dualization is no longer possible. In order to reduce the dual dimension, different heuristics were proposed. They involve a separation procedure to dynamically … Read more

    A Subspace Limited Memory BFGS Algorithm For Box Constrained Optimization

  • Yuan Gonglin
  • Wu Yanlin
  • Wei Zengxin
    • Categories Bound-constrained Optimization

    In this paper, a subspace limited BFGS algorithm is proposed for bound constrained optimization. The global convergence will be established under some suitable conditions. Numerical results show that this method is more competitive than the normal method does. Article Download View A Subspace Limited Memory BFGS Algorithm For Box Constrained Optimization

    The Facility Location Problem with Bernoulli Demands

  • Maria Albareda-Sambola
  • Francisco Saldanha-da-Gama
  • Elena Fernandez
    • Categories Stochastic Programming Tags ,

    In this paper we address a discrete capacitated facility location problem in which customers have Bernoulli demands. The problem is formulated as a two-stage stochastic program. The goal is to define an a priori solution for the location of the facilities and for the allocation of customers to the operating facilities that minimize the expected … Read more

    Projections Onto Super-Half-Spaces for Monotone Variational Inequality Problems in Finite-Dimensional Spaces

  • Yair Censor
  • Aviv Gibali
    • Categories Complementarity and Variational Inequalities Tags , ,

    The variational inequality problem (VIP) is considered here. We present a general algorithmic scheme which employs projections onto hyperplanes that separate balls from the feasible set of the VIP instead of projections onto the feasible set itself. Our algorithmic scheme includes the classical projection method and Fukushima’s subgradient projection method as special cases. Citation Technical … Read more

    An SDP-based divide-and-conquer algorithm for large scale noisy anchor-free graph realization

  • Ngai-Hang Z. Leung
  • Kim-Chuan Toh
    • Categories Basic Sciences Applications, Global Optimization Applications, Semi-definite Programming Tags , , ,

    We propose the DISCO algorithm for graph realization in $\real^d$, given sparse and noisy short-range inter-vertex distances as inputs. Our divide-and-conquer algorithm works as follows. When a group has a sufficiently small number of vertices, the basis step is to form a graph realization by solving a semidefinite program. The recursive step is to break … Read more

    Near-Optimal Solutions and Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling

  • Andreas S. Schulz
  • Nelson A. Uhan
    • Categories Combinatorial Optimization, Scheduling

    We consider the problem of minimizing the weighted sum of completion times on a single machine subject to bipartite precedence constraints where all minimal jobs have unit processing time and zero weight, and all maximal jobs have zero processing time and unit weight. For various probability distributions over these instances–including the uniform distribution–we show several … Read more

    Improved strategies for branching on general disjunctions

  • Gérard Cornuéjols
  • Leo Liberti
  • Giacomo Nannicini
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags , ,

    Within the context of solving Mixed-Integer Linear Programs by a Branch-and-Cut algorithm, we propose a new strategy for branching. Computational experiments show that, on the majority of our test instances, this approach enumerates fewer nodes than traditional branching. On average, on instances that contain both integer and continuous variables the number of nodes in the … Read more

    Identification and Elimination of Interior Points for the Minimum Enclosing Ball Problem

  • Selin Damla Ahipasaoglu
  • E. Alper Yildirim
    • Categories Convex Optimization Tags , ,

    Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$, we consider the problem of reducing the input set for the computation of the minimum enclosing ball of $\cA$. In this note, given an approximate solution to the minimum enclosing ball problem, we propose a simple procedure to identify and eliminate points in $\cA$ that are guaranteed to lie … Read more

    A new library of structured semidefinite programming instances

  • Etienne de Klerk
  • Renata Sotirov
    • Categories Semi-definite Programming Tags ,

    Solvers for semidefinite programming (SDP) have evolved a great deal in the last decade, and their development continues. In order to further support and encourage this development, we present a new test set of SDP instances. These instances arise from recent applications of SDP in coding theory, computational geometry, graph theory and structural design. Most … Read more