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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references