A hybrid approach for biobjective optimization

Thomas Jacob Riis Stidsen*, Kim Allan Andersen

*Corresponding author for this work

    Research output: Contribution to journalJournal articleResearchpeer-review

    84 Downloads (Pure)

    Abstract

    A large number of the real world planning problems which are today solved using Operations Research methods are actually multiobjective planning problems, but most of them are solved using singleobjective methods. The reason for converting, i.e. simplifying, multiobjective problems to singleobjective problems is that no standard multiobjective solvers exist and specialized algorithms need to be programmed from scratch.In this article we will present a hybrid approach, which operates both in decision space and in objective space. The approach enables massive efficient parallelization and can be used to a wide variety of biobjective Mixed Integer Programming models. We test the approach on the biobjective extension of the classic traveling salesman problem, on the standard datasets, and determine the full set of nondominated points. This has only been done once before (Florios and Mavrotas, 2014), and in our approach we do it in a fraction of the time.
    Original languageEnglish
    JournalDiscrete Optimization
    Volume28
    Pages (from-to)89-114
    ISSN1572-5286
    DOIs
    Publication statusPublished - 2018

    Keywords

    • Biobjective optimization
    • Branch-and-cut algorithm
    • Mixed integer programming
    • Traveling salesman problem

    Cite this

    @article{cb327387e6bb4f25807fa9fd9f13f531,
    title = "A hybrid approach for biobjective optimization",
    abstract = "A large number of the real world planning problems which are today solved using Operations Research methods are actually multiobjective planning problems, but most of them are solved using singleobjective methods. The reason for converting, i.e. simplifying, multiobjective problems to singleobjective problems is that no standard multiobjective solvers exist and specialized algorithms need to be programmed from scratch.In this article we will present a hybrid approach, which operates both in decision space and in objective space. The approach enables massive efficient parallelization and can be used to a wide variety of biobjective Mixed Integer Programming models. We test the approach on the biobjective extension of the classic traveling salesman problem, on the standard datasets, and determine the full set of nondominated points. This has only been done once before (Florios and Mavrotas, 2014), and in our approach we do it in a fraction of the time.",
    keywords = "Biobjective optimization, Branch-and-cut algorithm, Mixed integer programming, Traveling salesman problem",
    author = "Stidsen, {Thomas Jacob Riis} and Andersen, {Kim Allan}",
    year = "2018",
    doi = "10.1016/j.disopt.2018.02.001",
    language = "English",
    volume = "28",
    pages = "89--114",
    journal = "Discrete Optimization",
    issn = "1572-5286",
    publisher = "Elsevier",

    }

    A hybrid approach for biobjective optimization. / Stidsen, Thomas Jacob Riis; Andersen, Kim Allan.

    In: Discrete Optimization, Vol. 28, 2018, p. 89-114.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - A hybrid approach for biobjective optimization

    AU - Stidsen, Thomas Jacob Riis

    AU - Andersen, Kim Allan

    PY - 2018

    Y1 - 2018

    N2 - A large number of the real world planning problems which are today solved using Operations Research methods are actually multiobjective planning problems, but most of them are solved using singleobjective methods. The reason for converting, i.e. simplifying, multiobjective problems to singleobjective problems is that no standard multiobjective solvers exist and specialized algorithms need to be programmed from scratch.In this article we will present a hybrid approach, which operates both in decision space and in objective space. The approach enables massive efficient parallelization and can be used to a wide variety of biobjective Mixed Integer Programming models. We test the approach on the biobjective extension of the classic traveling salesman problem, on the standard datasets, and determine the full set of nondominated points. This has only been done once before (Florios and Mavrotas, 2014), and in our approach we do it in a fraction of the time.

    AB - A large number of the real world planning problems which are today solved using Operations Research methods are actually multiobjective planning problems, but most of them are solved using singleobjective methods. The reason for converting, i.e. simplifying, multiobjective problems to singleobjective problems is that no standard multiobjective solvers exist and specialized algorithms need to be programmed from scratch.In this article we will present a hybrid approach, which operates both in decision space and in objective space. The approach enables massive efficient parallelization and can be used to a wide variety of biobjective Mixed Integer Programming models. We test the approach on the biobjective extension of the classic traveling salesman problem, on the standard datasets, and determine the full set of nondominated points. This has only been done once before (Florios and Mavrotas, 2014), and in our approach we do it in a fraction of the time.

    KW - Biobjective optimization

    KW - Branch-and-cut algorithm

    KW - Mixed integer programming

    KW - Traveling salesman problem

    U2 - 10.1016/j.disopt.2018.02.001

    DO - 10.1016/j.disopt.2018.02.001

    M3 - Journal article

    VL - 28

    SP - 89

    EP - 114

    JO - Discrete Optimization

    JF - Discrete Optimization

    SN - 1572-5286

    ER -