CUTTING PLANE METHODS WITHOUT NESTED CONSTRAINT SETS

Abstract

General conditions are given for the convergence of a class of cutting-plane algorithms without requiring that the constraint sets for the subproblems be sequentially nested. Conditions are given under which inactive constraints may be dropped after each subproblem. Procedures for generating cutting-planes include that of Kelley and a generalization of that used by Zoutendisk and Veinott. For algorithms with nested constraint sets, these conditions reduce to a special case of those of Zangwill for such problems and include as special cases the algorithms of Kelley and Veinott. An arithmetic convergence rate is given.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1969
Accession Number
AD0694457

Entities

People

  • Donald M. Topkis

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Arithmetic
  • California
  • Convergence
  • Convex Sets
  • Engineering
  • Hypotheses
  • Industrial Engineering
  • Military Research
  • Nonlinear Programming
  • Operations Research
  • Theorems
  • United States
  • United States Government
  • Universities

Fields of Study

  • Mathematics

Readers

  • Operations Research