IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v103y1999i1d10.1023_a1021777501274.html
   My bibliography  Save this article

Stochastic Comparison Algorithm for Discrete Optimization with Estimation of Time-Varying Objective Functions

Author

Listed:
  • F. Martinelli

    (Università di Roma—Tor Vergata)

Abstract

In this paper, the optimization of time-varying objective functions, known only through estimates, is considered. Recent research defined algorithms for static optimization problems. Based on one of these algorithms, we derive an optimization scheme for the time-varying case. In stochastic optimization problems, convergence of an algorithm to the optimum prevents the algorithm from being efficiently adaptive to changes of the objective function if it is time-varying. So, convergence cannot be required in a time-varying scenario. Rather, we require convergence to the optimum with high probability together with a satisfactory dynamical behavior. Analytical and simulative results illustrate the performance of the proposed algorithm compared with other optimization techniques.

Suggested Citation

  • F. Martinelli, 1999. "Stochastic Comparison Algorithm for Discrete Optimization with Estimation of Time-Varying Objective Functions," Journal of Optimization Theory and Applications, Springer, vol. 103(1), pages 137-159, October.
    • Handle: RePEc:spr:joptap:v:103:y:1999:i:1:d:10.1023_a:1021777501274
    DOI: 10.1023/A:1021777501274
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1021777501274
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1021777501274?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. David S. Johnson & Cecilia R. Aragon & Lyle A. McGeoch & Catherine Schevon, 1989. "Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning," Operations Research, INFORMS, vol. 37(6), pages 865-892, December.
    2. L. Dai & C. H. Chen, 1997. "Rates of Convergence of Ordinal Comparison for Dependent Discrete Event Dynamic Systems," Journal of Optimization Theory and Applications, Springer, vol. 94(1), pages 29-54, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dell'Amico, Mauro & Trubian, Marco, 1998. "Solution of large weighted equicut problems," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 500-521, April.
    2. Schlereth, Christian & Stepanchuk, Tanja & Skiera, Bernd, 2010. "Optimization and analysis of the profitability of tariff structures with two-part tariffs," European Journal of Operational Research, Elsevier, vol. 206(3), pages 691-701, November.
    3. Orlin, James & Sharma, Dushyant, 2003. "The Extended Neighborhood: Definition And Characterization," Working papers 4392-02, Massachusetts Institute of Technology (MIT), Sloan School of Management.
    4. Melissa Gama & Bruno Filipe Santos & Maria Paola Scaparra, 2016. "A multi-period shelter location-allocation model with evacuation orders for flood disasters," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(3), pages 299-323, September.
    5. Pirlot, Marc, 1996. "General local search methods," European Journal of Operational Research, Elsevier, vol. 92(3), pages 493-511, August.
    6. Michael C. Fu & Jian-Qiang Hu & Chun-Hung Chen & Xiaoping Xiong, 2007. "Simulation Allocation for Determining the Best Design in the Presence of Correlated Sampling," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 101-111, February.
    7. M Kumral & P A Dowd, 2005. "A simulated annealing approach to mine production scheduling," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(8), pages 922-930, August.
    8. Noureddine Bouhmala, 2019. "Combining simulated annealing with local search heuristic for MAX-SAT," Journal of Heuristics, Springer, vol. 25(1), pages 47-69, February.
    9. Yiyo Kuo, 2014. "Design method using hybrid of line-type and circular-type routes for transit network system optimization," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(2), pages 600-613, July.
    10. Lamiri, Mehdi & Grimaud, Frédéric & Xie, Xiaolan, 2009. "Optimization methods for a stochastic surgery planning problem," International Journal of Production Economics, Elsevier, vol. 120(2), pages 400-410, August.
    11. Gabriel M. Portal & Marcus Ritt & Leonardo M. Borba & Luciana S. Buriol, 2016. "Simulated annealing for the machine reassignment problem," Annals of Operations Research, Springer, vol. 242(1), pages 93-114, July.
    12. Graeme J. Doole & David J. Pannell, 2008. "Optimisation of a Large, Constrained Simulation Model using Compressed Annealing," Journal of Agricultural Economics, Wiley Blackwell, vol. 59(1), pages 188-206, February.
    13. Michele Battistutta & Andrea Schaerf & Tommaso Urli, 2017. "Feature-based tuning of single-stage simulated annealing for examination timetabling," Annals of Operations Research, Springer, vol. 252(2), pages 239-254, May.
    14. Helena Ramalhinho-Lourenço & Daniel Serra, 1998. "Adaptive approach heuristics for the generalized assignment problem," Economics Working Papers 288, Department of Economics and Business, Universitat Pompeu Fabra.
    15. Jeffrey W. Ohlmann & Barrett W. Thomas, 2007. "A Compressed-Annealing Heuristic for the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 80-90, February.
    16. Kaji, Taichi & Ohuchi, Azuma, 1999. "A simulated annealing algorithm with the random compound move for the sequential partitioning problem of directed acyclic graphs," European Journal of Operational Research, Elsevier, vol. 112(1), pages 147-157, January.
    17. Healy, Patrick & Moll, Robert, 1995. "A new extension of local search applied to the Dial-A-Ride Problem," European Journal of Operational Research, Elsevier, vol. 83(1), pages 83-104, May.
    18. Dudek, Gregor & Stadtler, Hartmut, 2005. "Negotiation-based collaborative planning between supply chains partners," European Journal of Operational Research, Elsevier, vol. 163(3), pages 668-687, June.
    19. Lim, A. & Rodrigues, B. & Zhang, X., 2006. "A simulated annealing and hill-climbing algorithm for the traveling tournament problem," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1459-1478, November.
    20. Kim, Yeong-Dae & Lim, Hyeong-Gyu & Park, Moon-Won, 1996. "Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process," European Journal of Operational Research, Elsevier, vol. 91(1), pages 124-143, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:103:y:1999:i:1:d:10.1023_a:1021777501274. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.