## Abstract

Simplicial decomposition is an important form of decomposition for large non-linear programming problems with linear constraints. Von Hohenbalken has shown that if the number of retained extreme points is n + 1, where n is the number of variables in the problem, the method will reach an optimal simplex after a finite number of master problems have been solved (i.e., after a finite number of major cycles). However, on many practical problems it is infeasible to allocate computer memory for n + 1 extreme points. In this paper, we present a version of simplicial decomposition where the number of retained extreme points is restricted to r, 1 ≤ r ≤ n + 1, and prove that if r is sufficiently large, an optimal simplex will be reached in a finite number of major cycles. This result insures rapid convergence when r is properly chosen and the decomposition is implemented using a second order method to solve the master problem.

Original language | English (US) |
---|---|

Pages (from-to) | 125-130 |

Number of pages | 6 |

Journal | Operations Research Letters |

Volume | 4 |

Issue number | 3 |

DOIs | |

State | Published - Oct 1985 |

## All Science Journal Classification (ASJC) codes

- Software
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics