We study the restricted inverse optimal value problem on linear programming under weighted $l_1$ norm (RIOVLP $_1$). Given a linear programming problem $LP_c: \min \{ cx|Ax=b,x\geq 0\}$ with a feasible solution $x^0$ and a value $K$, we aim to adjust the vector $c$ to $\bar{ c}$ such that $x^0$ becomes an optimal solution of the problem LP$_{ \bar c}$ whose objective value $\bar{ c}x^0$ equals $K$. The objective is to minimize the distance $\|\bar c - c\|_1=\sum_{ j=1}^nd_j|\bar c_j-c_j|$ under weighted $l_1$ norm.Firstly, we formulate the problem (RIOVLP$_1$) as a linear programming problem by dual theories. Secondly, we construct a sub-problem $(D^z)$, which has the same form as $LP_c$, of the dual (RIOVLP$_1$) problem corresponding to a given value $z$. Thirdly, when the coefficient matrix $A$ is unimodular, we design a binary search algorithm to calculate the critical value $z^*$ corresponding to an optimal solution of the problem (RIOVLP$_1$). Finally, we solve the (RIOV) problems on Hitchcock and shortest path problem, respectively, in $O(T_{ MCF}\log\max\{ d_{ max},x^0_{ max},n\})$ time, where we solve a sub-problem $(D^z)$ by minimum cost flow in $T_{ MCF}$ time in each iteration. The values $d_{ max},x^0_{ max}$ are the maximum values of $d$ and $x^0$, respectively.
Categories: math.OC