On the complexity of postoptimality analysis of 0/1 programs

C.P.M. van Hoesel, A.P.M. Wagelmans

    Research output: Book/ReportReportAcademic

    21 Downloads (Pure)

    Abstract

    In this paper we address the complexity of postoptimality analysis of 0/1 programs with a linear objective function. After an optimal solution has been determined for a given cost vector, one may want to know how much each cost coefficient can vary individually without affecting the optimality of the solution. We show that, under mild conditions, the existence of a polynomial method to calculate these maximal ranges implies a polynomial method to solve the 0/1 program itself. As a consequence, postoptimality analysis of many well-known NP-hard problems can not be performed by polynomial methods, unless P=NP. A natural question that arises with respect to these problems is whether it is possible to calculate in polynomial time reasonable approximations of the maximal ranges. We show that it is equally unlikely that there exists a polynomial method that calculates conservative ranges for which the relative deviation from the true ranges is guaranteed to be at most some constant. Finally, we address the issue of postoptimality analysis of e-optimal solutions of NP-hard 0/1 problems. It is shown that for an e-optimal solution that has been determined in polynomial time, it is not possible to calculate in polynomial time the maximal amount by which a cost coefficient can be increased such that the solution remains e-optimal, unless P=NP.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Universiteit Eindhoven
    Number of pages15
    Publication statusPublished - 1991

    Publication series

    NameMemorandum COSOR
    Volume9135
    ISSN (Print)0926-4493

    Fingerprint

    Polynomial Methods
    Calculate
    Polynomial time
    Optimal Solution
    Range of data
    Costs
    Coefficient
    NP-hard Problems
    Linear Function
    Optimality
    Deviation
    NP-complete problem
    Objective function
    Vary
    Imply
    Approximation

    Cite this

    van Hoesel, C. P. M., & Wagelmans, A. P. M. (1991). On the complexity of postoptimality analysis of 0/1 programs. (Memorandum COSOR; Vol. 9135). Eindhoven: Technische Universiteit Eindhoven.
    van Hoesel, C.P.M. ; Wagelmans, A.P.M. / On the complexity of postoptimality analysis of 0/1 programs. Eindhoven : Technische Universiteit Eindhoven, 1991. 15 p. (Memorandum COSOR).
    @book{10135fcba54e40f1acc6b97abe4c6d57,
    title = "On the complexity of postoptimality analysis of 0/1 programs",
    abstract = "In this paper we address the complexity of postoptimality analysis of 0/1 programs with a linear objective function. After an optimal solution has been determined for a given cost vector, one may want to know how much each cost coefficient can vary individually without affecting the optimality of the solution. We show that, under mild conditions, the existence of a polynomial method to calculate these maximal ranges implies a polynomial method to solve the 0/1 program itself. As a consequence, postoptimality analysis of many well-known NP-hard problems can not be performed by polynomial methods, unless P=NP. A natural question that arises with respect to these problems is whether it is possible to calculate in polynomial time reasonable approximations of the maximal ranges. We show that it is equally unlikely that there exists a polynomial method that calculates conservative ranges for which the relative deviation from the true ranges is guaranteed to be at most some constant. Finally, we address the issue of postoptimality analysis of e-optimal solutions of NP-hard 0/1 problems. It is shown that for an e-optimal solution that has been determined in polynomial time, it is not possible to calculate in polynomial time the maximal amount by which a cost coefficient can be increased such that the solution remains e-optimal, unless P=NP.",
    author = "{van Hoesel}, C.P.M. and A.P.M. Wagelmans",
    year = "1991",
    language = "English",
    series = "Memorandum COSOR",
    publisher = "Technische Universiteit Eindhoven",

    }

    van Hoesel, CPM & Wagelmans, APM 1991, On the complexity of postoptimality analysis of 0/1 programs. Memorandum COSOR, vol. 9135, Technische Universiteit Eindhoven, Eindhoven.

    On the complexity of postoptimality analysis of 0/1 programs. / van Hoesel, C.P.M.; Wagelmans, A.P.M.

    Eindhoven : Technische Universiteit Eindhoven, 1991. 15 p. (Memorandum COSOR; Vol. 9135).

    Research output: Book/ReportReportAcademic

    TY - BOOK

    T1 - On the complexity of postoptimality analysis of 0/1 programs

    AU - van Hoesel, C.P.M.

    AU - Wagelmans, A.P.M.

    PY - 1991

    Y1 - 1991

    N2 - In this paper we address the complexity of postoptimality analysis of 0/1 programs with a linear objective function. After an optimal solution has been determined for a given cost vector, one may want to know how much each cost coefficient can vary individually without affecting the optimality of the solution. We show that, under mild conditions, the existence of a polynomial method to calculate these maximal ranges implies a polynomial method to solve the 0/1 program itself. As a consequence, postoptimality analysis of many well-known NP-hard problems can not be performed by polynomial methods, unless P=NP. A natural question that arises with respect to these problems is whether it is possible to calculate in polynomial time reasonable approximations of the maximal ranges. We show that it is equally unlikely that there exists a polynomial method that calculates conservative ranges for which the relative deviation from the true ranges is guaranteed to be at most some constant. Finally, we address the issue of postoptimality analysis of e-optimal solutions of NP-hard 0/1 problems. It is shown that for an e-optimal solution that has been determined in polynomial time, it is not possible to calculate in polynomial time the maximal amount by which a cost coefficient can be increased such that the solution remains e-optimal, unless P=NP.

    AB - In this paper we address the complexity of postoptimality analysis of 0/1 programs with a linear objective function. After an optimal solution has been determined for a given cost vector, one may want to know how much each cost coefficient can vary individually without affecting the optimality of the solution. We show that, under mild conditions, the existence of a polynomial method to calculate these maximal ranges implies a polynomial method to solve the 0/1 program itself. As a consequence, postoptimality analysis of many well-known NP-hard problems can not be performed by polynomial methods, unless P=NP. A natural question that arises with respect to these problems is whether it is possible to calculate in polynomial time reasonable approximations of the maximal ranges. We show that it is equally unlikely that there exists a polynomial method that calculates conservative ranges for which the relative deviation from the true ranges is guaranteed to be at most some constant. Finally, we address the issue of postoptimality analysis of e-optimal solutions of NP-hard 0/1 problems. It is shown that for an e-optimal solution that has been determined in polynomial time, it is not possible to calculate in polynomial time the maximal amount by which a cost coefficient can be increased such that the solution remains e-optimal, unless P=NP.

    M3 - Report

    T3 - Memorandum COSOR

    BT - On the complexity of postoptimality analysis of 0/1 programs

    PB - Technische Universiteit Eindhoven

    CY - Eindhoven

    ER -

    van Hoesel CPM, Wagelmans APM. On the complexity of postoptimality analysis of 0/1 programs. Eindhoven: Technische Universiteit Eindhoven, 1991. 15 p. (Memorandum COSOR).