Piecewise-linear programming: The compact (CPLP) algorithm (Q3754440)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4001877
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Piecewise-linear programming: The compact (CPLP) algorithm |
scientific article; zbMATH DE number 4001877 |
Statements
Piecewise-linear programming: The compact (CPLP) algorithm (English)
0 references
1986
0 references
degeneracy
0 references
compact algorithm
0 references
convex piecewise-linear programming
0 references
linear constraints
0 references
simplex method
0 references
line search
0 references
0 references
0.8444186449050903
0 references
0.8415961265563965
0 references
0.8359418511390686
0 references
0.8344126343727112
0 references
0.8211243748664856
0 references
A compact algorithm is presented for solving the convex piecewise-linear programming problem, formulated by means of a separable convex piecewise- linear objective function (to be minimized) and a set of linear constraints. This algorithm consists of a finite sequence of cycles, derived from the simplex method, characteristic of linear programming, and the line search, characteristic of nonlinear programming. Both the required storage and amount of calculation are reduced with respect to the usual approach, based on a linear-programming formulation with an expanded tableau. The tableau dimensions are \(m\times (n+1)\), where m is the number of constraints and n the number of the (original) structural variables, and they do not increase with the number of breakpoints of the piecewise-linear terms constituting the objective function.
0 references