Calculating some inverse linear programming problems (Q1923457)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Calculating some inverse linear programming problems
scientific article

    Statements

    Calculating some inverse linear programming problems (English)
    0 references
    2 March 1997
    0 references
    For the general linear programming problem \[ \min \{cx/Ax = b,\;x \geq 0\} \] the inverse problem is expressed as \[ \min \bigl\{ |c-\widetilde c|/ \widetilde c\in F(x^0) \bigr\} \] where \(c,x \in \mathbb{R}^n\), \(b \in \mathbb{R}^m\), \(A\) is an \(m \times n\) matrix, \(x^0\) is a feasible solution, \[ F(x^0) = \bigl\{\widetilde c \in \mathbb{R}^n/ \min \{\widetilde cx/Ax=b,\;x\geq 0\} = \widetilde cx^0 \bigr\} \] and \(|\dots|\) is the \(l_1\) norm. A method for solving this inverse problem is suggested which is based on the optimality conditions for linear programming problems. For the application of the given method to inverse minimum cost flow or assignment problems is found that this method yields strongly polynomial algorithms.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    linear programming
    0 references
    inverse problem
    0 references
    inverse minimum cost flow
    0 references
    assignment problems
    0 references
    polynomial algorithms
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references