GRASP with path-relinking for the weighted maximum satisfiability problem

  • Paola Festa
  • Panos M. Pardalos
  • Mauricio G.C. Resende
  • Leonidas S. Pitsoulis
    • Categories Meta Heuristics, Stochastic Approaches Tags , , ,

    A GRASP with path-relinking for finding good-quality solutions of the weighted maximum satisfiability problem (MAX-SAT) is described in this paper. GRASP, or Greedy Randomized Adaptive Search Procedure, is a randomized multi-start metaheuristic, where at each iteration locally optimal solutions are constructed, each independent of the others. Previous experimental results indicate its effectiveness for solving weighted … Read more

    Rebalancing an Investment Portfolio in the Presence of Convex Transaction Costs

  • Stephen E. Braun
  • John E. Mitchell
    • Categories Convex Optimization, Finance and Economics, Linear, Cone and Semidefinite Programming Tags ,

    The inclusion of transaction costs is an essential element of any realistic portfolio optimization. In this paper, we consider an extension of the standard portfolio problem in which convex transaction costs are incurred to rebalance an investment portfolio. In particular, we consider linear, piecewise linear, and quadratic transaction costs. The Markowitz framework of mean-variance efficiency … Read more

    Bregman distances, totally convex functions and a method for solving operator equations in Banach spaces

  • Dan Butnariu
  • Elena Resmerita
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , , ,

    The aim of this paper is twofold. First, several basic mathematical concepts involved in the construction and study of Bregman type iterative algorithms are presented from a unified analytic perspective. Also, some gaps in the current knowledge about those concepts are filled in. Second, we employ existing results on total convexity, sequential consistency, uniform convexity … Read more

    On the Minimum Volume Covering Ellipsoid of Ellipsoids

  • E. Alper Yildirim
    • Categories Convex Optimization Tags , , ,

    We study the problem of computing a $(1+\eps)$-approximation to the minimum volume covering ellipsoid of a given set $\cS$ of the convex hull of $m$ full-dimensional ellipsoids in $\R^n$. We extend the first-order algorithm of Kumar and \Yildirim~that computes an approximation to the minimum volume covering ellipsoid of a finite set of points in $\R^n$, … Read more

    Convex Optimization of Centralized Inventory Operations

  • Samuel Burer
  • Moshe Dror
    • Categories Game Theory, Linear, Cone and Semidefinite Programming, Production and Logistics

    Given a finite set of outlets with joint normally distributed demands and identical holding and penalty costs, inventory centralization induces a cooperative cost allocation game with nonempty core. It is well known that for this newsvendor inventory setting the expected cost of centralization can be expressed as a constant multiple of the standard deviation of … Read more

    Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks

  • Arie M.C.A. Koster
  • Adrian Zymolka
    • Categories (Mixed) Integer Linear Programming, Graphs and Matroids, Telecommunications Tags , , ,

    In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of … Read more

    On Complexity of Multistage Stochastic Programs

  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , ,

    In this paper we derive estimates of the sample sizes required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented analysis is self contained and is based on a, relatively elementary, one dimensional Cramer’s Large Deviations Theorem. CitationWorking paper, Georgia Institute of Technology, … Read more

    A linear programming approach to increasing the weight of all minimum spanning trees

  • Mourad Baiou
  • Francisco Barahona
    • Categories Graphs and Matroids Tags , , ,

    Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. We formulate this as a combinatorial linear program and give … Read more

    Two-Stage Stochastic Semidefinite Programming and Decomposition Based Interior Point Methods

  • Sanjay Mehrotra
  • M. Gokhan Ozevin
    • Categories Semi-definite Programming, Stochastic Programming Tags , , ,

    We introduce two-stage stochastic semidefinite programs with recourse and present a Benders decomposition based linearly convergent interior point algorithms to solve them. This extends the results of Zhao, who showed that the logarithmic barrier associated with the recourse function of two-stage stochastic linear programs with recourse behaves as a strongly self-concordant barrier on the first … Read more

    Further Extension of TSP Assign Neighborhood

  • Fred Glover
  • Gregory Gutin
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization

    We introduce a new extension of Punnen’s exponential neighborhood for the traveling salesman problem (TSP). In contrast to an interesting generalization of Punnen’s neighborhood by De Franceschi, Fischetti and Toth (2005), our neighborhood is searchable in polynomial time, a feature that invites exploitation by heuristic and metaheuristic procedures for the TSP and related problems, including … Read more