IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v61y2013i2p386-397.html

A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One

Author

Listed:
  • Shashi Mittal

    (Amazon.com, Seattle, Washington 98109)

  • Andreas S. Schulz

    (Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

In this paper, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two linear functions, parallel machine scheduling problems with the makespan objective, robust versions of weighted multiobjective optimization problems, and assortment optimization problems with logit choice models. The main idea behind our approximation schemes is the construction of an approximate Pareto-optimal frontier of the functions that constitute the given objective. Using this idea, we give the first fully polynomial-time approximation schemes for the max-min resource allocation problem with a fixed number of agents, combinatorial optimization problems in which the objective function is the sum of a fixed number of ratios of linear functions, or the product of a fixed number of linear functions, and assortment optimization problems with logit choice model.

Suggested Citation

  • Shashi Mittal & Andreas S. Schulz, 2013. "A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One," Operations Research, INFORMS, vol. 61(2), pages 386-397, April.
    • Handle: RePEc:inm:oropre:v:61:y:2013:i:2:p:386-397
    DOI: 10.1287/opre.1120.1093
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1120.1093
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1120.1093?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
    ---><---

    References listed on IDEAS

    as
    1. Arthur Warburton, 1987. "Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems," Operations Research, INFORMS, vol. 35(1), pages 70-79, February.
    2. Nir Halman & Diego Klabjan & Mohamed Mostagir & Jim Orlin & David Simchi-Levi, 2009. "A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand," Mathematics of Operations Research, INFORMS, vol. 34(3), pages 674-685, August.
    3. Gerhard J. Woeginger, 2000. "When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 57-74, February.
    4. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2007. "Approximation of min-max and min-max regret versions of some combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 179(2), pages 281-290, June.
    5. Nimrod Megiddo, 1979. "Combinatorial Optimization with Rational Objective Functions," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 414-424, November.
    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. Danny Segev, 2022. "Technical Note—Approximation Schemes for Capacity-Constrained Assortment Optimization Under the Nested Logit Model," Operations Research, INFORMS, vol. 70(5), pages 2820-2836, September.
    2. Yi-Chun Akchen & Dmitry Mitrofanov, 2023. "Consider or Choose? The Role and Power of Consideration Sets," Papers 2302.04354, arXiv.org, revised Feb 2025.
    3. Meng Qi & Ho‐Yin Mak & Zuo‐Jun Max Shen, 2020. "Data‐driven research in retail operations—A review," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(8), pages 595-616, December.
    4. Brad D. Woods & Abraham P. Punnen, 2020. "A class of exponential neighbourhoods for the quadratic travelling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 303-332, August.
    5. Shaoning Han & Andrés Gómez & Oleg A. Prokopyev, 2022. "Fractional 0–1 programming and submodularity," Journal of Global Optimization, Springer, vol. 84(1), pages 77-93, September.
    6. Nan Liu & Yuhang Ma & Huseyin Topaloglu, 2020. "Assortment Optimization Under the Multinomial Logit Model with Sequential Offerings," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 835-853, July.
    7. H. Edwin Romeijn & Dolores Romero Morales & Wilco Van den Heuvel, 2014. "Computational complexity of finding Pareto efficient outcomes for biobjective lot‐sizing models," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(5), pages 386-402, August.
    8. Gallego, Guillermo & Li, Anran & Truong, Van-Anh & Wang, Xinshang, 2020. "Approximation algorithms for product framing and pricing," LSE Research Online Documents on Economics 101983, London School of Economics and Political Science, LSE Library.
    9. Nathan Adelgren & Akshay Gupte, 2022. "Branch-and-Bound for Biobjective Mixed-Integer Linear Programming," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 909-933, March.
    10. Rui Chen & Hai Jiang, 2020. "Capacitated assortment and price optimization under the nested logit model," Journal of Global Optimization, Springer, vol. 77(4), pages 895-918, August.
    11. Rui Chen & Hai Jiang, 2020. "Assortment optimization with position effects under the nested logit model," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(1), pages 21-33, February.
    12. Miri Gilenson & Hussein Naseraldin & Liron Yedidsion, 2019. "An approximation scheme for the bi-scenario sum of completion times trade-off problem," Journal of Scheduling, Springer, vol. 22(3), pages 289-304, June.
    13. Jacob B. Feldman & Huseyin Topaloglu, 2015. "Capacity Constraints Across Nests in Assortment Optimization Under the Nested Logit Model," Operations Research, INFORMS, vol. 63(4), pages 812-822, August.
    14. Brad D. Woods & Abraham P. Punnen, 0. "A class of exponential neighbourhoods for the quadratic travelling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-30.
    15. Büsing, Christina & Goetzmann, Kai-Simon & Matuschke, Jannik & Stiller, Sebastian, 2017. "Reference points and approximation algorithms in multicriteria discrete optimization," European Journal of Operational Research, Elsevier, vol. 260(3), pages 829-840.
    16. Guillermo Gallego & Anran Li & Van-Anh Truong & Xinshang Wang, 2020. "Approximation Algorithms for Product Framing and Pricing," Operations Research, INFORMS, vol. 68(1), pages 134-160, January.
    17. Antoine Désir & Vineet Goyal & Jiawei Zhang, 2022. "Technical Note—Capacitated Assortment Optimization: Hardness and Approximation," Operations Research, INFORMS, vol. 70(2), pages 893-904, March.

    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. Halman, Nir & Kellerer, Hans & Strusevich, Vitaly A., 2018. "Approximation schemes for non-separable non-linear boolean programming problems under nested knapsack constraints," European Journal of Operational Research, Elsevier, vol. 270(2), pages 435-447.
    2. Büsing, Christina & Goetzmann, Kai-Simon & Matuschke, Jannik & Stiller, Sebastian, 2017. "Reference points and approximation algorithms in multicriteria discrete optimization," European Journal of Operational Research, Elsevier, vol. 260(3), pages 829-840.
    3. Retel Helmrich, Mathijn J. & Jans, Raf & van den Heuvel, Wilco & Wagelmans, Albert P.M., 2015. "The economic lot-sizing problem with an emission capacity constraint," European Journal of Operational Research, Elsevier, vol. 241(1), pages 50-62.
    4. Wei Chen & Milind Dawande & Ganesh Janakiraman, 2014. "Fixed-Dimensional Stochastic Dynamic Programs: An Approximation Scheme and an Inventory Application," Operations Research, INFORMS, vol. 62(1), pages 81-103, February.
    5. Nir Halman & Mikhail Y. Kovalyov & Alain Quilliot & Dvir Shabtay & Moshe Zofi, 2019. "Bi-criteria path problem with minimum length and maximum survival probability," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 469-489, June.
    6. Nir Halman, 2020. "Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1157-1181, October.
    7. J. Puerto & A. M. Rodríguez-Chía & A. Tamir, 2009. "Minimax Regret Single-Facility Ordered Median Location Problems on Networks," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 77-87, February.
    8. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, September.
    9. Safer, Hershel M. & Orlin, James B., 1953-, 1995. "Fast approximation schemes for multi-criteria combinatorial optimization," Working papers 3756-95., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    10. Mark M. Nejad & Lena Mashayekhy & Daniel Grosu & Ratna Babu Chinnam, 2017. "Optimal Routing for Plug-In Hybrid Electric Vehicles," Transportation Science, INFORMS, vol. 51(4), pages 1304-1325, November.
    11. Elisabeth Günther & Felix G. König & Nicole Megow, 2014. "Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width," Journal of Combinatorial Optimization, Springer, vol. 27(1), pages 164-181, January.
    12. Christoph Hertrich & Martin Skutella, 2023. "Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1079-1097, September.
    13. Soroush, H.M., 2008. "Optimal paths in bi-attribute networks with fractional cost functions," European Journal of Operational Research, Elsevier, vol. 190(3), pages 633-658, November.
    14. Steffen Rebennack & Ashwin Arulselvan & Lily Elefteriadou & Panos M. Pardalos, 2010. "Complexity analysis for maximum flow problems with arc reversals," Journal of Combinatorial Optimization, Springer, vol. 19(2), pages 200-216, February.
    15. Yongjian Yang & Guangqiang Yin & Chunyu Wang & Yunqiang Yin, 0. "Due date assignment and two-agent scheduling under multitasking environment," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-17.
    16. Özen, Ulaş & Doğru, Mustafa K. & Armagan Tarim, S., 2012. "Static-dynamic uncertainty strategy for a single-item stochastic inventory control problem," Omega, Elsevier, vol. 40(3), pages 348-357.
    17. Bart Smeulders & Laurens Cherchye & Bram De Rock & Frits C. R. Spieksma, 2013. "The Money Pump as a Measure of Revealed Preference Violations: A Comment," Journal of Political Economy, University of Chicago Press, vol. 121(6), pages 1248-1258.
    18. Nir Halman & Giacomo Nannicini, 2025. "Fully Polynomial Time Approximation Schemes for Robust Multistage Decision Making," INFORMS Journal on Computing, INFORMS, vol. 37(5), pages 1306-1327, September.
    19. Li, Jianping & Ge, Yu & He, Shuai & Lichen, Junran, 2014. "Approximation algorithms for constructing some required structures in digraphs," European Journal of Operational Research, Elsevier, vol. 232(2), pages 307-314.
    20. Franco Quezada & Céline Gicquel & Safia Kedad-Sidhoum, 2022. "Combining Polyhedral Approaches and Stochastic Dual Dynamic Integer Programming for Solving the Uncapacitated Lot-Sizing Problem Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1024-1041, March.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:inm:oropre:v:61:y:2013:i:2:p:386-397. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.