IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v478y2017icp158-167.html
   My bibliography  Save this article

Dual mean field search for large scale linear and quadratic knapsack problems

Author

Listed:
  • Banda, Juan
  • Velasco, Jonás
  • Berrones, Arturo

Abstract

An implementation of mean field annealing to deal with large scale linear and non linear binary optimization problems is given. Mean field annealing is based on the analogy between combinatorial optimization and interacting physical systems at thermal equilibrium. Specifically, a mean field approximation of the Boltzmann distribution given by a Lagrangian that encompass the objective function and the constraints is calculated. The original discrete task is in this way transformed into a continuous variational problem. In our version of mean field annealing, no temperature parameter is used, but a good starting point in the dual space is given by a “thermodynamic limit” argument. The method is tested in linear and quadratic knapsack problems with sizes that are considerably larger than those used in previous studies of mean field annealing. Dual mean field annealing is capable to find high quality solutions in running times that are orders of magnitude shorter than state of the art algorithms. Moreover, as may be expected for a mean field theory, the solutions tend to be more accurate as the number of variables grow.

Suggested Citation

  • Banda, Juan & Velasco, Jonás & Berrones, Arturo, 2017. "Dual mean field search for large scale linear and quadratic knapsack problems," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 478(C), pages 158-167.
  • Handle: RePEc:eee:phsmap:v:478:y:2017:i:c:p:158-167
    DOI: 10.1016/j.physa.2017.02.052
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437117302169
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

    File URL: https://libkey.io/10.1016/j.physa.2017.02.052?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. Dolgui, Alexandre & Kovalev, Sergey & Pesch, Erwin, 2015. "Approximate solution of a profit maximization constrained virtual business planning problem," Omega, Elsevier, vol. 57(PB), pages 212-216.
    2. Ohlsson, Mattias & Peterson, Carsten & Soderberg, Bo, 2001. "An efficient mean field approach to the set covering problem," European Journal of Operational Research, Elsevier, vol. 133(3), pages 583-595, September.
    3. John N. Hooker, 2002. "Logic, Optimization, and Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 295-321, November.
    4. Alain Billionnet & Éric Soutif, 2004. "Using a Mixed Integer Programming Tool for Solving the 0–1 Quadratic Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 188-197, May.
    5. Billionnet, Alain & Soutif, Eric, 2004. "An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 157(3), pages 565-575, September.
    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. Liu, Yipeng & Koehler, Gary J., 2010. "Using modifications to Grover's Search algorithm for quantum global optimization," European Journal of Operational Research, Elsevier, vol. 207(2), pages 620-632, December.
    2. Schauer, Joachim, 2016. "Asymptotic behavior of the quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 255(2), pages 357-363.
    3. Dolgui, Alexandre & Hashemi-Petroodi, S. Ehsan & Kovalev, Sergey & Kovalyov, Mikhail Y., 2021. "Profitability of a multi-model manufacturing line versus multiple dedicated lines," International Journal of Production Economics, Elsevier, vol. 236(C).
    4. Teobaldo Bulhões & Anand Subramanian & Gilberto F. Sousa Filho & Lucídio dos Anjos F. Cabral, 2017. "Branch-and-price for p-cluster editing," Computational Optimization and Applications, Springer, vol. 67(2), pages 293-316, June.
    5. Shuming Wang & Yan-Fu Li & Tong Jia, 2020. "Distributionally Robust Design for Redundancy Allocation," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 620-640, July.
    6. Chevalier, Philippe & Thomas, Isabelle & Geraets, David & Goetghebeur, Els & Janssens, Olivier & Peeters, Dominique & Plastria, Frank, 2012. "Locating fire stations: An integrated approach for Belgium," Socio-Economic Planning Sciences, Elsevier, vol. 46(2), pages 173-182.
    7. Yuning Chen & Jin-Kao Hao, 2015. "Iterated responsive threshold search for the quadratic multiple knapsack problem," Annals of Operations Research, Springer, vol. 226(1), pages 101-131, March.
    8. Alidaee, Bahram, 2014. "Zero duality gap in surrogate constraint optimization: A concise review of models," European Journal of Operational Research, Elsevier, vol. 232(2), pages 241-248.
    9. Li, Haitao & Womer, Keith, 2012. "Optimizing the supply chain configuration for make-to-order manufacturing," European Journal of Operational Research, Elsevier, vol. 221(1), pages 118-128.
    10. Britta Schulze & Michael Stiglmayr & Luís Paquete & Carlos M. Fonseca & David Willems & Stefan Ruzika, 2020. "On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(1), pages 107-132, August.
    11. Polyakovskiy, Sergey & M’Hallah, Rym, 2021. "Just-in-time two-dimensional bin packing," Omega, Elsevier, vol. 102(C).
    12. Relich Marcin, 2012. "An evaluation of project completion with application of fuzzy set theory," Management, Sciendo, vol. 16(1), pages 216-229, May.
    13. Réal Carbonneau & Gilles Caporossi & Pierre Hansen, 2014. "Globally Optimal Clusterwise Regression By Column Generation Enhanced with Heuristics, Sequencing and Ending Subset Optimization," Journal of Classification, Springer;The Classification Society, vol. 31(2), pages 219-241, July.
    14. Bulhões, Teobaldo & Correia, Rubens & Subramanian, Anand, 2022. "Conference scheduling: A clustering-based approach," European Journal of Operational Research, Elsevier, vol. 297(1), pages 15-26.
    15. Robert Fourer & David M. Gay, 2002. "Extending an Algebraic Modeling Language to Support Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 322-344, November.
    16. Andrew J. Collins & Kasi Bharath Vegesana & Michael J. Seiler & Patrick O’Shea & Prasanna Hettiarachchi & Frederic McKenzie, 2013. "Simulation and mathematical programming decision-making support for smallholder farming," Environment Systems and Decisions, Springer, vol. 33(3), pages 427-439, September.
    17. Turner, S.D.O. & Romero, D.A. & Zhang, P.Y. & Amon, C.H. & Chan, T.C.Y., 2014. "A new mathematical programming approach to optimize wind farm layouts," Renewable Energy, Elsevier, vol. 63(C), pages 674-680.
    18. Mervat Chouman & Teodor Gabriel Crainic & Bernard Gendron, 2018. "The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 143-184, June.
    19. Isma Dahmani & Mhand Hifi, 2021. "A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs," Annals of Operations Research, Springer, vol. 298(1), pages 125-147, March.
    20. MirHassani, S.A. & Yarahmadi, A., 2017. "Wind farm layout optimization under uncertainty," Renewable Energy, Elsevier, vol. 107(C), pages 288-297.

    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:eee:phsmap:v:478:y:2017:i:c:p:158-167. 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: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.