Stochastic Approaches

A Penalized Quadratic Convex Reformulation Method for Random Quadratic Unconstrained Binary Optimization

  • Karthik Natarajan
  • Kim-Chuan Toh
  • Dongjian Shi
    • Categories 0-1 Programming, Stochastic Approaches Tags , ,

    The Quadratic Convex Reformulation (QCR) method is used to solve quadratic unconstrained binary optimization problems. In this method, the semidefinite relaxation is used to reformulate it to a convex binary quadratic program which is solved using mixed integer quadratic programming solvers. We extend this method to random quadratic unconstrained binary optimization problems. We develop a … Read more

    Biased and unbiased random-key genetic algorithms: An experimental analysis

  • José Fernando Gonçalves
  • Mauricio G.C. Resende
  • Rodrigo F. Toso
    • Categories Meta Heuristics, Optimization Software Benchmark, Stochastic Approaches Tags , , , , , ,

    We study the runtime performance of three types of random-key genetic algorithms: the unbiased algorithm of Bean (1994); the biased algorithm of Gonçalves and Resende (2011); and a greedy version of Bean’s algorithm on 12 instances from four types of covering problems: general-cost set covering, Steiner triple covering, general-cost set K-covering, and unit-cost covering by … Read more

    STOCHASTIC OPTIMIZATION OVER A PARETO SET ASSOCIATED WITH A STOCHASTIC MULTI-OBJECTIVE OPTIMIZATION PROBLEM

  • Henri Bonnel
  • Julien Collonge
    • Categories Multi-Criteria Optimization, Stochastic Approaches Tags , , , ,

    We deal with the problem of minimizing the expectation of a real valued random function over the weakly Pareto or Pareto set associated with a Stochastic Multi-Objective Optimization Problem (SMOP) whose objectives are expectations of random functions. Assuming that the closed form of these expectations is difficult to obtain, we apply the Sample Average Approximation … Read more

    Differerential Evolution methods based on local searches

  • Marco Locatelli
  • Mirko Maischberger
  • Fabio Schoen
    • Categories Global Optimization, Stochastic Approaches Tags , , ,

    In this paper we analyze the behavior of a quite standard Differential Evolution (DE) algorithm applied to the objective function transformed by means of local searches. First some surprising results are presented which concern the application of this method to standard test functions. Later we introduce an application to disk- and to sphere-packing problems, two … Read more

    Simulation Optimization for the Stochastic Economic Lot Scheduling Problem with Sequence-Dependent Setup Times

  • Nils Löhndorf
  • Stefan Minner
  • Manuel Riel
    • Categories Optimization of Simulated Systems, Scheduling, Stochastic Approaches Tags , , , , ,

    We consider the stochastic economic lot scheduling problem (SELSP) with lost sales and random demand, where switching between products is subject to sequence-dependent setup times. We propose a solution based on simulation optimization using an iterative two-step procedure which combines global policy search with local search heuristics for the traveling salesman sequencing subproblem. To optimize … Read more

    A Stochastic Gradient Method with an Exponential Convergence Rate for Strongly-Convex Optimization with Finite Training Sets

  • Francis Bach
  • Mark Schmidt
  • Nicolas Le Roux
    • Categories Convex Optimization, Stochastic Approaches

    We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence rate. Numerical … Read more

    A PROBABILITY-DRIVEN SEARCH ALGORITHM FOR SOLVING MULTI-OBJECTIVE OPTIMIZATION PROBLEMS

  • Tran Van Hao
  • Nguyen Huu Thong
    • Categories Multi-Criteria Optimization, Nonlinear Optimization, Stochastic Approaches Tags , , ,

    This paper proposes a new probabilistic algorithm for solving multi-objective optimization problems – Probability-Driven Search Algorithm. The algorithm uses probabilities to control the process in search of Pareto optimal solutions. Especially, we use the absorbing Markov Chain to argue the convergence of the algorithm. We test this approach by implementing the algorithm on some benchmark … Read more

    A Python/C library for bound-constrained global optimization with continuous GRASP

  • Michael J. Hirsch
  • Panos M. Pardalos
  • Mauricio G.C. Resende
  • Ricardo M.A. Silva
    • Categories Global Optimization, Optimization Software and Modeling Systems, Stochastic Approaches Tags , , , , , , , ,

    This paper describes libcgrpp, a GNU-style dynamic shared Python/C library of the continuous greedy randomized adaptive search procedure (C-GRASP) for bound constrained global optimization. C-GRASP is an extension of the GRASP metaheuristic (Feo and Resende, 1989). After a brief introduction to C-GRASP, we show how to download, install, configure, and use the library through an … Read more

    Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms

  • Celso C. Ribeiro
  • Isabel Rosseti
  • Reinaldo Vallejos
    • Categories Meta Heuristics, Parallel Algorithms, Stochastic Approaches

    Run time distributions or time-to-target plots are very useful tools to characterize the running times of stochastic algorithms for combinatorial optimization. We further explore run time distributions and describe a new tool to compare two algorithms based on stochastic local search. For the case where the running times of both algorithms fit exponential distributions, we … Read more

    A concave optimization-based approach for sparse portfolio selection

  • David Di Lorenzo
  • Giampaolo Liuzzi
  • Francesco Rinaldi
  • Fabio Schoen
  • Marco Sciandrone
    • Categories Constrained Nonlinear Optimization, Finance and Economics, Stochastic Approaches Tags , , ,

    This paper considers a portfolio selection problem in which portfolios with minimum number of active assets are sought. This problem is motivated by the need of inducing sparsity on the selected portfolio to reduce transaction costs, complexity of portfolio management, and instability of the solution. The resulting problem is a difficult combinatorial problem. We propose … Read more