A general model of some inverse combinatorial optimization problems and its solution method under \(\ell_\infty\) norm (Q1598883)
From MaRDI portal
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
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
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