IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v232y2014i2p241-248.html
   My bibliography  Save this article

Zero duality gap in surrogate constraint optimization: A concise review of models

Author

Listed:
  • Alidaee, Bahram

Abstract

Surrogate constraint relaxation was proposed in the 1960s as an alternative to the Lagrangian relaxation for solving difficult optimization problems. The duality gap in the surrogate relaxation is always as good as the duality gap in the Lagrangian relaxation. Over the years researchers have proposed procedures to reduce the gap in the surrogate constraint. Our aim is to review models that close the surrogate duality gap. Five research streams that provide procedures with zero duality gap are identified and discussed. In each research stream, we will review major results, discuss limitations, and suggest possible future research opportunities. In addition, relationships between models if they exist, are also discussed.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:232:y:2014:i:2:p:241-248
    DOI: 10.1016/j.ejor.2013.04.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713003214
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2013.04.023?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. Isada, Yuriko & James, Ross J. W. & Nakagawa, Yuji, 2005. "An approach for solving nonlinear multi-objective separable discrete optimization problem with one constraint," European Journal of Operational Research, Elsevier, vol. 162(2), pages 503-513, April.
    2. Djangir A. Babayev & Fred Glover & Jennifer Ryan, 1997. "A New Knapsack Solution Approach by Integer Equivalent Aggregation and Consistency Determination," INFORMS Journal on Computing, INFORMS, vol. 9(1), pages 43-50, February.
    3. Sarin, Sanjiv & Karwan, Mark H. & Rardin, Ronald L., 1988. "Surrogate duality in a branch-and-bound procedure for integer programming," European Journal of Operational Research, Elsevier, vol. 33(3), pages 326-333, February.
    4. George Vairaktarakis & Janice Kim Winch, 1999. "Worker Cross-Training in Paced Assembly Lines," Manufacturing & Service Operations Management, INFORMS, vol. 1(2), pages 112-131.
    5. Fred Glover, 1975. "Surrogate Constraint Duality in Mathematical Programming," Operations Research, INFORMS, vol. 23(3), pages 434-451, June.
    6. Xing-Si Li & Shu-Cherng Fang, 1997. "On the entropic regularization method for solving min-max problems with applications," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 46(1), pages 119-130, February.
    7. Fred Glover, 1965. "A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem," Operations Research, INFORMS, vol. 13(6), pages 879-919, December.
    8. Narciso, Marcelo G. & Lorena, Luiz Antonio N., 1999. "Lagrangean/surrogate relaxation for generalized assignment problems," European Journal of Operational Research, Elsevier, vol. 114(1), pages 165-177, April.
    9. E A Silver, 2004. "An overview of heuristic solution methods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(9), pages 936-956, September.
    10. Duan Li & Xiaoling Sun, 2006. "Nonlinear Integer Programming," International Series in Operations Research and Management Science, Springer, number 978-0-387-32995-6, December.
    11. Ablanedo-Rosas, José H. & Rego, César, 2010. "Surrogate constraint normalization for the set covering problem," European Journal of Operational Research, Elsevier, vol. 205(3), pages 540-551, September.
    12. S. L. van de Velde, 1993. "Duality-Based Algorithms for Scheduling Unrelated Parallel Machines," INFORMS Journal on Computing, INFORMS, vol. 5(2), pages 192-205, May.
    13. John N. Hooker, 2002. "Logic, Optimization, and Constraint Programming," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 295-321, November.
    14. S.-L. Kim & S. Kim, 1998. "Exact Algorithm for the Surrogate Dual of an Integer Programming Problem: Subgradient Method Approach," Journal of Optimization Theory and Applications, Springer, vol. 96(2), pages 363-375, February.
    15. Harvey J. Greenberg & William P. Pierskalla, 1970. "Surrogate Mathematical Programming," Operations Research, INFORMS, vol. 18(5), pages 924-939, October.
    16. Albert E. Fernandes Muritiba & Manuel Iori & Enrico Malaguti & Paolo Toth, 2010. "Algorithms for the Bin Packing Problem with Conflicts," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 401-415, August.
    17. Ram, Balasubramanian & Karwan, Mark H. & Babu, A. J. G., 1988. "Aggregation of constraints in integer programming," European Journal of Operational Research, Elsevier, vol. 35(2), pages 216-227, May.
    18. David F. Rogers & Robert D. Plante & Richard T. Wong & James R. Evans, 1991. "Aggregation and Disaggregation Techniques and Methodology in Optimization," Operations Research, INFORMS, vol. 39(4), pages 553-582, August.
    19. Mohammadi Bidhandi, Hadi & Mohd. Yusuff, Rosnah & Megat Ahmad, Megat Mohamad Hamdan & Abu Bakar, Mohd Rizam, 2009. "Development of a new approach for deterministic supply chain network design," European Journal of Operational Research, Elsevier, vol. 198(1), pages 121-128, October.
    20. Silvano Martello & David Pisinger & Paolo Toth, 1999. "Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 45(3), pages 414-424, March.
    21. Mark H. Karwan & Ronald L. Rardin, 1984. "Surrogate Dual Multiplier Search Procedures in Integer Programming," Operations Research, INFORMS, vol. 32(1), pages 52-69, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Edirisinghe, Chanaka & Jeong, Jaehwan, 2019. "Indefinite multi-constrained separable quadratic optimization: Large-scale efficient solution," European Journal of Operational Research, Elsevier, vol. 278(1), pages 49-63.

    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. N. Boland & A. C. Eberhard & A. Tsoukalas, 2015. "A Trust Region Method for the Solution of the Surrogate Dual in Integer Programming," Journal of Optimization Theory and Applications, Springer, vol. 167(2), pages 558-584, November.
    2. Marco Antonio Boschetti & Vittorio Maniezzo, 2022. "Matheuristics: using mathematics for heuristic design," 4OR, Springer, vol. 20(2), pages 173-208, June.
    3. Saïd Hanafi & Christophe Wilbaut, 2011. "Improved convergent heuristics for the 0-1 multidimensional knapsack problem," Annals of Operations Research, Springer, vol. 183(1), pages 125-142, March.
    4. Ablanedo-Rosas, José H. & Rego, César, 2010. "Surrogate constraint normalization for the set covering problem," European Journal of Operational Research, Elsevier, vol. 205(3), pages 540-551, September.
    5. Glover, Fred, 2013. "Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems," European Journal of Operational Research, Elsevier, vol. 230(2), pages 212-225.
    6. Arnaud Fréville & SaÏd Hanafi, 2005. "The Multidimensional 0-1 Knapsack Problem—Bounds and Computational Aspects," Annals of Operations Research, Springer, vol. 139(1), pages 195-227, October.
    7. Edirisinghe, Chanaka & Jeong, Jaehwan, 2019. "Indefinite multi-constrained separable quadratic optimization: Large-scale efficient solution," European Journal of Operational Research, Elsevier, vol. 278(1), pages 49-63.
    8. Renaud Chicoisne, 2023. "Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes," Computational Optimization and Applications, Springer, vol. 84(3), pages 789-831, April.
    9. Yuji Nakagawa & Ross J. W. James & César Rego & Chanaka Edirisinghe, 2014. "Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models," Management Science, INFORMS, vol. 60(3), pages 695-707, March.
    10. Silvano Martello & Paolo Toth, 2003. "An Exact Algorithm for the Two-Constraint 0--1 Knapsack Problem," Operations Research, INFORMS, vol. 51(5), pages 826-835, October.
    11. Yoon, Yourim & Kim, Yong-Hyuk & Moon, Byung-Ro, 2012. "A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 218(2), pages 366-376.
    12. Joseph, Anito & Gass, Saul I. & Bryson, Noel, 1998. "An objective hyperplane search procedure for solving the general all-integer linear programming (ILP) problem," European Journal of Operational Research, Elsevier, vol. 104(3), pages 601-614, February.
    13. Satoshi Suzuki & Daishi Kuroiwa, 2012. "Necessary and Sufficient Constraint Qualification for Surrogate Duality," Journal of Optimization Theory and Applications, Springer, vol. 152(2), pages 366-377, February.
    14. Cerqueus, Audrey & Przybylski, Anthony & Gandibleux, Xavier, 2015. "Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems," European Journal of Operational Research, Elsevier, vol. 244(2), pages 417-433.
    15. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    16. Audrey Cerqueus & Xavier Gandibleux & Anthony Przybylski & Frédéric Saubion, 2017. "On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem," Journal of Heuristics, Springer, vol. 23(5), pages 285-319, October.
    17. Cesar Rego & Frank Mathew & Fred Glover, 2010. "RAMP for the capacitated minimum spanning tree problem," Annals of Operations Research, Springer, vol. 181(1), pages 661-681, December.
    18. Y.M. Ermoliev & A.V. Kryazhimskii & A. Ruszczynski, 1995. "Constraint Aggregation Principle in Convex Optimization," Working Papers wp95015, International Institute for Applied Systems Analysis.
    19. M. A. Venkataramana & John J. Dinkel & John Mote, 1991. "Vector processing approach to constrained network problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(1), pages 71-85, February.
    20. Selcuk Karabati & Panagiotis Kouvelis & Gang Yu, 2001. "A Min-Max-Sum Resource Allocation Problem and Its Applications," Operations Research, INFORMS, vol. 49(6), pages 913-922, December.

    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:ejores:v:232:y:2014:i:2:p:241-248. 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.elsevier.com/locate/eor .

    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.