A simplex-type algorithm for continuous linear programs with constant coefficients

DOI10.1007/S10107-018-1353-6MaRDI QIDQ2297646zbMATHOpenAlexWikidataFDO

Authors Evgeny Shindin, Gideon Weiss

Publication date 20 February 2020

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

optimal controlcontinuous linear programmingsimplex-type algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Linear optimal control problems (49N05)

Abstract: We consider continuous linear programs over a continuous finite time horizon $T$, with a constant coefficient matrix, linear right hand side functions and linear cost coefficient functions, where 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 previous papers we have shown that these problems possess optimal strongly dual solutions. We also have presented a detailed description of optimal solutions and have defined a combinatorial analogue to basic solutions of standard LP. In this paper we present an algorithm which solves this class of problems in a finite bounded number of steps, using an analogue of the simplex method, in the space of measures.

Recommendations

• Structure of solutions for continuous linear programs with constant coefficients
• A simplex based algorithm to solve separated continuous linear programs
• Some Properties of a Class of Continuous Linear Programs
• Symmetric strong duality for a class of continuous linear programs with constant coefficients
• On the Solutions of a Class of Continuous Linear Programs

Cites work

• scientific article; zbMATH DE number 4029251 (Why is no real title available?)
• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 3069634 (Why is no real title available?)
• A Duality Theorem for a Class of Continuous Linear Programming Problems
• A Duality Theory for Separated Continuous Linear Programs
• A New Algorithm for State-Constrained Separated Continuous Linear Programs
• A class of continuous linear programming problems
• A class of infinite dimensional linear programming problems
• A continuous-time network simplex algorithm
• A method of solution for quadratic 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
• An Extended Duality Theorem for Continuous Linear Programming Problems
• Bimatrix Equilibrium Points and Mathematical Programming
• Bottleneck Problems and Dynamic Programming
• Continuous-time generalized fractional programming problems. II: an interval-type computational procedure
• Continuous-time generalized fractional programming problems. Part I: Basic theory
• Convergence of a General Class of Algorithms for Separated Continuous Linear Programs
• Decomposition Principle for Linear Programs
• Efficient Algorithms for Separated Continuous Linear Programs: The Multicommodity Flow Problem with Holding Costs and Extensions
• Efficient continuous-time dynamic network flow algorithms
• Equilibrium Points of Bimatrix Games
• Existence and duality theory for separated continuous linear programs
• Forms of Optimal Solutions for Separated Continuous Linear Programs
• Linear programming. Foundations and extensions
• Near optimal control of queueing networks over a finite time horizon
• On duality theory of conic linear problems.
• Polynomial approximations for continuous linear programs
• Quickest Flows Over Time
• Separated continuous conic programming: strong duality and an approximation algorithm
• Structure of solutions for continuous linear programs with constant coefficients
• Symmetric Duality for Continuous Linear Programs
• Symmetric strong duality for a class of continuous linear programs with constant coefficients
• The quickest transshipment problem

Cited in

(5)

• scientific article; zbMATH DE number 5022963 (Why is no real title available?)
• Structure of solutions for continuous linear programs with constant coefficients
• Forms of Optimal Solutions for Separated Continuous Linear Programs
• Symmetric strong duality for a class of continuous linear programs with constant coefficients
• A simplex based algorithm to solve separated continuous linear programs

This page was built for publication: A simplex-type algorithm 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 Q2297646)