AN O(N(3)LOG N) STRONG POLYNOMIAL ALGORITHM FOR AN ISOTONIC REGRESSION KNAPSACK-PROBLEM

被引：3

作者：

BEST, MJ

TAN, RY

机构：

[1] Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario

来源：

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS | 1993年 / 79卷 / 03期

关键词：

KNAPSACK PROBLEMS; ISOTONIC REGRESSION; QUADRATIC PROGRAMS; PARAMETRIC PROGRAMS; OPTIMALITY CONDITIONS; LAGRANGE FUNCTION; LAGRANGE MULTIPLIER; BREAKPOINTS; MAXIMAL CUTS; ACTIVE SETS;

D O I：

10.1007/BF00940553

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We introduce the isotonic regression knapsack problem [GRAPHICS] where each di is positive and each alpha(i), a(i), i = 1,...,n, and c are arbitrary scalars. This problem is the natural extension of the isotonic regression problem which permits a strong polynomial solution algorithm. In this paper, an approach is developed from the Karush-Kuhn-Tucker conditions. By considering the Lagrange function without the inequalities, we establish a way to find the proper Lagrange multiplier associated with the equation using a parametric program, which yields optimality. We show that such a procedure can be performed in strong polynomial time, and an example is demonstrated.

引用

页码：463 / 478

页数：16