Duality gap in interval linear programming
From MaRDI portal
Publication:2302757
Abstract: This paper deals with the problem of linear programming with inexact data represented by real closed intervals. Optimization problems with interval data arise in practical computations and they are of theoretical interest for more than forty years. We extend the concept of duality gap (DG), the difference between the primal and its dual optimal value, into interval linear programming. We consider two situations: First, DG is zero for every realization of interval parameters (the so called strongly zero DG) and, second, DG is zero for at least one realization of interval parameters (the so called weakly zero DG). We characterize strongly and weakly zero DG and its special case where the matrix of coefficients is real. We discuss computational complexity of testing weakly and strongly zero DG for commonly used types of interval linear programs and their variants with the real matrix of coefficients. We distinguish the NP-hard cases and the cases that are efficiently decidable. Based on DG conditions, we extend previous results about the bounds of the optimal value set given by Rohn. We provide equivalent statements for the bounds
The duality gap in interval linear programming is studied. Concepts of a weakly and strongly zero duality gap for interval linear programming problems are introduced. The authors consider three types of interval linear programming problems: 1) problems with equality constraints and nonegative variables, 2) problems with inequality constraints without restrictions on signs of variables, 3) problems with inequality constraints and nonnegative variables. A characterization for weakly zero duality is proposed. Both sufficient and necessary conditions for a strongly zero duality gap are proved. The computational complexity of the proposed procedures is analyzed. Some open questions for further research in the area are summarized in the Conclusion.
Recommendations
- scientific article; zbMATH DE number 3880020
- Duality theory in interval-valued linear programming problems
- Duality gap in convex programming
- Duality gap function in infinite dimensional linear programming
- Duality theory for a class of interval-valued programming
- Bounding duality gap for separable problems with linear constraints
- Duality for inexact linear programming problems∗
- Duality gaps in stochastic integer programming
- On the existence of duality gaps for mixed integer programming
Cites work
- Complexity of some linear problems with interval data
- How to determine basis stability in interval linear programming
- scientific article; zbMATH DE number 3167495 (Why is no real title available?)
- scientific article; zbMATH DE number 3880009 (Why is no real title available?)
- scientific article; zbMATH DE number 3880020 (Why is no real title available?)
- scientific article; zbMATH DE number 3325265 (Why is no real title available?)
- Interval linear programming under transformations: optimal solutions and optimal value range
- Introduction to Interval Analysis
- Inverse linear programming with interval coefficients
- Linear interval inequalities
- Linear Optimization Problems with Inexact Data
- Linear programming with interval coefficients
- Linear programming with interval right hand sides
- Linear programming with variable matrix entries
- Optimal value range in interval linear programming
- Optimization and decision science: methodologies and applications. ODS, Sorrento, Italy, September 4--7, 2017
- Robustness and duality in linear programming
- Strong solvability of interval linear programming problems
- Sufficient condition of basis stability of an interval linear programming problem
- Transformations of interval linear systems of equations and inequalities
- Weak and strong solvability of interval linear systems of equations and inequalities
- Zur lösung linearer ungleichungssysteme bei störimg der rechten seite und der koeffizientenmatrix
Cited in
(13)- Interval linear programming under transformations: optimal solutions and optimal value range
- Weak optimal inverse problems of interval linear programming based on KKT conditions
- Testing weak optimality of a given solution in interval linear programming revisited: NP-hardness proof, algorithm and some polynomially-solvable cases
- The outcome range problem in interval linear programming
- scientific article; zbMATH DE number 3880020 (Why is no real title available?)
- scientific article; zbMATH DE number 5257230 (Why is no real title available?)
- On the existence of duality gaps for mixed integer programming
- Fréchet subdifferential calculus for interval-valued functions and its applications in nonsmooth interval optimization
- Interval variational inequalities and their relationship with interval optimization problems
- Quantifying outcome functions of linear programs: an approach based on interval-valued right-hand sides
- Complexity issues in interval linear programming
- Absolute value linear programming
- Projected subgradient method for nonsmooth interval optimization problems with application
This page was built for publication: Duality gap in interval linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2302757)
