99. Fundamental properties of absolute value linear programming problems
Invited abstract in session WD-6: Linear Programming, stream Methods for non-/monotone inclusions and their applications.
Wednesday, 11:25 - 12:40Room: M:H
Authors (first author is the speaker)
| 1. | Milan HladÃk
|
| Department of Applied Mathematics, Charles University, Faculty of Mathematics and Physics |
Abstract
The area of absolute value linear programming is quite recent and intensively developing. The basic problem has the form of a linear program, but the constraints have an additional absolute value term, which makes them nonlinear and nonsmooth and the problem itself hard to deal with. Even the simple-formulated problem Ax+|x|=b, called the absolute value equations by Mangasarian, is intractable; the classical NP-hard problems such as the Set-Partitioning problem or the standard linear complementarity problem can easily be reduced to this form.
In our presentation, we explore basic properties of absolute value linear programs. In particular, we inspect the geometric shape of the solution set and study conditions for convexity, connectedness and boundedness. We also analyse the corresponding complexity issues, showing that many basic questions are NP-hard to answer. The problem also admits a certain type of duality, based on the theory of interval linear programming. Since one may ask for integral solutions, we investigate conditions ensuring integrality of the vertices of the feasible set, extending the classical results on unimodular matrices in linear programming.
Keywords
- Linear and nonlinear optimization
- Global optimization
- Complementarity and variational problems
Status: accepted
Back to the list of papers