AN EXACT SEARCH FOR THE SOLUTION OF THE SURROGATE DUAL OF THE 0-1 BIDIMENSIONAL KNAPSACK-PROBLEM

被引：28

作者：

FREVILLE, A ^{[1
]}

PLATEAU, G ^{[1
]}

机构：

[1] UNIV PARIS 13,INST GALILEE,CNRS,URA 1507,LAB INFORMAT PARIS NORD,F-93430 VILLETANEUSE,FRANCE

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1993年 / 68卷 / 03期

关键词：

0-1 BIDIMENSIONAL KNAPSACK PROBLEM; DICHOTOMIC SEARCH; SURROGATE DUAL;

D O I：

10.1016/0377-2217(93)90197-U

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The surrogate dual of the 0-1 bidimensional knapsack problem is exactly solved by an algorithm with a modified dichotomic search. The primal (or dual) optimality is proved with a finite number of iterations. A lot of numerical experiments show the efficiency of our method: its reduced number of iterations is revealed to be independent of the size of the instances.

引用

页码：413 / 421

页数：9

共 16 条

[1]

BOURGEOIS P, 1991, LIPN912 RES REP

[2] CALCULATING SURROGATE CONSTRAINTS [J].

DYER, ME .

MATHEMATICAL PROGRAMMING, 1980, 19 (03) :255-278

[3] ALGORITHMUS 47 - AN ALGORITHM FOR THE SOLUTION OF THE 0-1 KNAPSACK-PROBLEM [J].

FAYARD, D ;

PLATEAU, G .

COMPUTING, 1982, 28 (03) :269-287

[4]

FISCHER ML, 1974, SIAM J APPL MATH, V27, P31

[5]

FREVILLE A, 1992, GRAPHS OPTIMIZATION

[6]

FREVILLE A, IN PRESS RAIRO

[7]

Garfinkel R. S., 1972, INTEGER PROGRAMMING

[8] EFFICIENT ALGORITHMS FOR SOLVING MULTICONSTRAINT ZERO-ONE KNAPSACK-PROBLEMS TO OPTIMALITY [J].

GAVISH, B ;

PIRKUL, H .

MATHEMATICAL PROGRAMMING, 1985, 31 (01) :78-105

[9]

Geoffrion A., 1974, MATH PROGRAMMING STU, V2, DOI [10.1007/BFb0120690, DOI 10.1007/BFB0120686]

[10]

GLOVER F, 1965, OPER RES, V18, P924

← 1 2 →