A general model of some inverse combinatorial optimization problems and its solution method under \(\ell_\infty\) norm (Q1598883)

From MaRDI portal
Revision as of 05:03, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
A general model of some inverse combinatorial optimization problems and its solution method under \(\ell_\infty\) norm
scientific article

    Statements

    A general model of some inverse combinatorial optimization problems and its solution method under \(\ell_\infty\) norm (English)
    0 references
    0 references
    0 references
    28 May 2002
    0 references
    Given a combinatorial optimization problem \(\min \{ w(F): F \in {\mathcal F} \}\) and a feasible solution \(\overline F\) to it, the associated inverse combinatorial optimization problem asks for a new weighting vector \(\overline w\) such that \(\overline F\) is optimal under \(\overline w\) and the distance between \(w\) and \(\overline w\) is minimized under a suitable norm. A related reverse problem asks to adjust in the most economic way suitable parameters (e.g. capacities) in order to achieve a given target value for the optimal solution or not exceed a given budget. This paper proposes an optimization model which generalizes several inverse and reverse problems, focalizing on the \(L_1\) and \(L_{\infty}\) norms. For the \(L_{\infty}\) norm a Newton-type algorithm is described which solves the model in a strongly polynomial number of iterations, each one of them requiring the solution of a related subproblem for a fixed value of a scalar parameter. The paper discusses several inverse optimization problems that can be solved in strongly polynomial time by the proposed procedure.
    0 references
    0 references
    path
    0 references
    cycle
    0 references
    mean-cycle
    0 references
    assignment
    0 references
    spanning tree
    0 references
    matching
    0 references
    matroid intersection
    0 references
    basis
    0 references

    Identifiers