Month: October 2008

Modeling and Solving Location Routing and Scheduling Problems

  • Z. Akca
  • Ted K. Ralphs
  • R.T. Berger
    • Categories 0-1 Programming, Network Optimization, Production and Logistics Tags , , ,

    This paper studies location routing and scheduling problems, a class of problems in which the decisions of facility location, vehicle routing, and route assignment are optimized simultaneously. For a version with capacity and time restrictions, two formulations are presented, one graph-based and one set-partitioning-based. For the set-partitioning-based formulation, valid inequalities are identified and their effectiveness … Read more

    On LP Relaxations for the Pattern Minimization Problem

  • Alessandro Aloisio
  • Claudio Arbib
  • Fabrizio Marinelli
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We discuss two formulations of the Pattern Minimization Problem: (1) introduced by Vanderbeck, and (2) obtained adding setup variables to the cutting stock formulation by Gilmore-Gomory. Let $z_i^{LP}(u)$ be the bound given by the linear relaxation of ($i$) under a given vector $u = (u_k)$ of parameters. We show that $z_2^{LP}(u}) \ge z_1^{LP}(u)$ and provide … Read more

    Necessary conditions for local optimality in d.c. programming

  • Immanuel M. Bomze
  • Claude LemarĂ©chal
    • Categories Constrained Nonlinear Optimization, Unconstrained Optimization

    Using $\eps$-subdifferential calculus for difference-of-convex (d.c.) programming, D\”ur proposed a condition sufficient for local optimality, and showed that this condition is not necessary in general. Here it is proved that whenever the convex part is strongly convex, this condition is also necessary. Strong convexity can always be ensured by changing the given d.c. decomposition slightly. … Read more

    Exploiting special structure in semidefinite programming: a survey of theory and applications

  • Etienne de Klerk
    • Categories Semi-definite Programming Tags

    Semidefinite Programming (SDP) may be seen as a generalization of Linear Programming (LP). In particular, one may extend interior point algorithms for LP to SDP, but it has proven much more difficult to exploit structure in the SDP data during computation. We survey three types of special structure in SDP data: 1) a common `chordal’ … Read more

    Improved bounds for interatomic distance in Morse clusters

  • Bernardetta Addis
  • Werner Schachinger
    • Categories Global Optimization, Global Optimization Theory Tags ,

    We improve the best known lower bounds on the distance between two points of a Morse cluster in $\mathbb{R}^3$, with $\rho \in [4.967,15]$. Our method is a generalization of the one applied to the Lennard-Jones potential in~\cite{Schac}, and it also leads to improvements of lower bounds for the energy of a Morse cluster. Some of … Read more

    A globally convergent primal-dual interior-point filter method for nonlinear programming: new filter optimality measures and computational results

  • R. Silva
  • Michael Ulbrich
  • Stefan Ulbrich
  • Luis Nunes Vicente
    • Categories Constrained Nonlinear Optimization, Optimization Software and Modeling Systems, Quadratic Programming Tags , , , ,

    In this paper we modify the original primal-dual interior-point filter method proposed in [18] for the solution of nonlinear programming problems. We introduce two new optimality filter entries based on the objective function, and thus better suited for the purposes of minimization, and propose conditions for using inexact Hessians. We show that the global convergence … Read more

    Lipschitz behavior of the robust regularization

  • Adrian Lewis
  • C.H. Jeffrey Pang
    • Categories Control Applications, Nonsmooth Optimization, Robust Optimization Tags , , , , , , , ,

    To minimize or upper-bound the value of a function “robustly”, we might instead minimize or upper-bound the “epsilon-robust regularization”, defined as the map from a point to the maximum value of the function within an epsilon-radius. This regularization may be easy to compute: convex quadratics lead to semidefinite-representable regularizations, for example, and the spectral radius … Read more