Structure of solutions for continuous linear programs with constant coefficients

DOI10.1137/140971725MaRDI QIDQ5501227zbMATH OpenOpenAlexFDO

Authors Evgeny Shindin, Gideon Weiss

Publication date 3 August 2015

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.2186

zbMATH Keywords

continuous linear programmingoptimal sequence of basesoptimization in the space of measuresstrong dualitystructure of solutionssymmetric dual

Mathematics Subject Classification ID

Duality theory (optimization) (49N15) Numerical methods for mathematical programming, optimization and variational techniques (65K99) Programming in abstract spaces (90C48)

Abstract: We consider Continuous Linear Programs over a continuous finite time horizon $T$, with linear cost coefficient functions, linear right hand side functions, and a constant coefficient matrix, as well as their symmetric dual. We search for optimal solutions in the space of measures or of functions of bounded variation. These models generalize the Separated Continuous Linear Programming models and their various duals, as formulated in the past by Anderson, by Pullan, and by Weiss. In a recent paper we have shown that under a Slater type condition, these problems possess optimal strongly dual solutions. In this paper we give a detailed description of optimal solutions and define a combinatorial analog to basic solutions of standard LP. We also show that feasibility implies existence of strongly dual optimal solutions without requiring the Slater condition. We present several examples to illustrate the richness and complexity of these solutions.

Recommendations

• Symmetric strong duality for a class of continuous linear programs with constant coefficients
• A Duality Theory for Separated Continuous Linear Programs
• A simplex-type algorithm for continuous linear programs with constant coefficients
• An Algorithm for a Class of Continuous Linear Programs
• Some Properties of a Class of Continuous Linear Programs

Cites work

• A class of continuous linear programming problems
• A continuous-time network simplex algorithm
• A Duality Theory for Separated Continuous Linear Programs
• A new continuous model for job-shop scheduling
• A simplex based algorithm to solve separated continuous linear programs
• An Algorithm for a Class of Continuous Linear Programs
• Bottleneck Problems and Dynamic Programming
• Convergence of a General Class of Algorithms for Separated Continuous Linear Programs
• Existence and duality theory for separated continuous linear programs
• Forms of Optimal Solutions for Separated Continuous Linear Programs
• scientific article; zbMATH DE number 4029251 (Why is no real title available?)
• scientific article; zbMATH DE number 3069634 (Why is no real title available?)
• Symmetric Duality for Continuous Linear Programs
• Symmetric strong duality for a class of continuous linear programs with constant coefficients

Cited in

(6)

• On the form of solutions to the linear continuous time programming problem and a conjecture by Tyndall
• Numerical method for solving the continuous-time linear programming problems with time-dependent matrices and piecewise continuous functions
• A simplex-type algorithm for continuous linear programs with constant coefficients
• Symmetric strong duality for a class of continuous linear programs with constant coefficients
• Some Properties of a Class of Continuous Linear Programs
• Forms of Optimal Solutions for Separated Continuous Linear Programs

This page was built for publication: Structure of solutions for continuous linear programs with constant coefficients

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501227)