A simplex based algorithm to solve separated continuous linear programs
type: Item
instance of: scholarly article
title: A simplex based algorithm to solve separated continuous linear programs
zbMATH Open document ID: 1165.90011
author: Gideon Weiss
published in: Mathematical Programming. Series A. Series B
publication date: 2008-06-30T00:00:00Z
review text: The author develops a simplex based algorithm to solve separated continuous linear programs (SCLP) of the form \[ \max \int_0^T \left(\left(\gamma' + (T-t) c'\right) u(t) + d'x(t)\right) dt \] \[ \text{s.t. } \int_0^t Gu(s)ds + F x(t) \leq \alpha + at \] \[ Hu(t) \leq b \] \[ x(t), u(t) \geq 0 \quad t \in [0,T]. \] A symmetric dual SCLP* is formulated and weak duality and complementary slackness are shown. By construction, as a result of the algorithm, strong duality is proved under feasibility and boundedness assumptions. Under the same assumptions the existence of solutions to SCLP and SCLP* for all \(0<T<\infty\) is shown. Under a nondegeneracy assumption the solution is proved to be unique. The algorithm is based on the characterization of optimal solutions of SCLP and SCLP* as (finite) sequences of bases which correspond to extreme points of the feasible region. The validity region of a base sequence is shown to be a convex polyhedral cone. This allows the definition of neighboring base sequences (those whose validity regions have boundaries with an intersection containing more than the origin) which describe the iterations of the algorithm. The algorithm solves SCLP/SCLP* by a sequence of SCLP steps analogous to the parametric self dual simplex method for LP. The author first gives a simplified version of the algorithm with some assumption that he later removes in the general and extended versions.
reviewed by: Matthias Ehrgott
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 49N05
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 5294511
zbMATH Keywords: continuous linear programming
zbMATH Keywords: simplex algorithm
describes a project that uses: LPbook
MaRDI profile type: Publication
full work available at URL: s10107-008-0217-x
OpenAlex ID: W1987611686
cites work: A new continuous model for job-shop scheduling
cites work: Q3770273
cites work: A continuous-time network simplex algorithm
cites work: Q4873243
cites work: Bottleneck Problems and Dynamic Programming
cites work: Q3241581
cites work: Q3844775
cites work: Q5736638
cites work: Efficient Algorithms for Separated Continuous Linear Programs: The Multicommodity Flow Problem with Holding Costs and Extensions
cites work: Quickest Flows Over Time
cites work: Criss-cross methods: A fresh view on pivot algorithms
cites work: Symmetric Duality for Continuous Linear Programs
cites work: Optimal dynamic routing in communication networks with continuous traffic
cites work: Inexact primal-dual interior point iteration for linear programs in function spaces
cites work: A New Algorithm for State-Constrained Separated Continuous Linear Programs
cites work: An alternative method for a global analysis of quadratic programs in a finite number of steps
cites work: Extreme Points and Basic Feasible Solutions in Continuous Time Linear Programming
cites work: An adaptive discretization algorithm for a class of continuous network programs
cites work: An Algorithm for a Class of Continuous Linear Programs
cites work: Forms of Optimal Solutions for Separated Continuous Linear Programs
cites work: A Duality Theory for Separated Continuous Linear Programs
cites work: Existence and duality theory for separated continuous linear programs
cites work: Convergence of a General Class of Algorithms for Separated Continuous Linear Programs
cites work: An extended algorithm for separated continuous linear programs
cites work: On duality theory of conic linear problems.
cites work: Q4842994
DOI: 10.1007/S10107-008-0217-X
description: scientific article; zbMATH DE number 5294511