1. On inverse linear programming problems under the bottleneck-type weighted Hamming distance
- Author
-
Javad Tayyebi and Massoud Aman
- Subjects
Mathematical optimization ,021103 operations research ,Linear programming ,Applied Mathematics ,0211 other engineering and technologies ,P versus NP problem ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Multi-commodity flow problem ,Linear-fractional programming ,010201 computation theory & mathematics ,Cutting stock problem ,Discrete Mathematics and Combinatorics ,Criss-cross algorithm ,Minimum-cost flow problem ,Change-making problem ,Algorithm ,Mathematics - Abstract
Given a linear programming problem with the objective function coefficients vector c and a feasible solution x 0 to this problem, a corresponding inverse linear programming problem is to modify the vector c as little as possible to make x 0 form an optimal solution to the linear programming problem. The modifications can be measured by different distances. In this article, we consider the inverse linear programming problem under the bottleneck-type weighted Hamming distance. We propose an algorithm based on the binary search technique to solve the problem. At each iteration, the algorithm has to solve a linear programming problem. We also consider the inverse minimum cost flow problem as a special case of the inverse linear programming problems and specialize the proposed method for solving this problem in strongly polynomial time. The specialized algorithm solves a shortest path problem at each iteration. It is shown that its complexity is better than the previous one.
- Published
- 2018
- Full Text
- View/download PDF