Heuristic and Exact Algorithms for the Disjunctively Constrained Knapsack Problem
スポンサーリンク
概要
- 論文の詳細を見る
We are concerned with a variation of the knapsack problem (KP), where some items are incompatible with some others. As in ordinary KPs, each item is associated with profit and weight, we have a knapsack of a fixed capacity, and the problem is to determine the set of items to be packed into the knapsack. However, the knapsack is not allowed to include incompatible pairs. The knapsack problem with such an additional set of constraints is referred to as the disjunctively constrained knapsack problem (DCKP). We present a heuristic method as well as an implicit enumeration algorithm and an interval reduction method to solve DCKPs to optimality. Combining these, we are able to solve DCKPs with up to 1,000 items.
- 一般社団法人情報処理学会の論文
- 2002-09-15
著者
-
Yamada Takeo
Department Of Internal Medicine Josai Dental University
-
WATANABE Kohtaro
Department of Internal Medicine, Institute of Clinical Medicine, University of Tsukuba
-
Yamada T
Energy Electronic Institute National Institute Of Advanced Inductrial Science And Technology (aist)
-
Yamada Takeo
Energy Electronic Institute National Institute Of Advanced Inductrial Science And Technology (aist)
-
Watanabe Kohtaro
Department Of Computer Science The National Defense Academy
-
Yamada Takeo
Department Of Computer Science The National Defense Academy
-
Yamada Takeo
Department Of Computer Science National Defense Academy
-
KATAOKA SEIJ
Department of Computer Science, The National Defense Academy
-
Watanabe Kohtaro
Department Of Biological Functions And Engineering Kyushu Institute Of Technology
-
Kataoka Seij
Department Of Computer Science The National Defense Academy
-
Kataoka Seiji
Department Of Computer Science National Defense Academy
関連論文
- A Simple Method for Fabrication of Mesoporous Films Using a Rapid Heating Process
- The SPV NO_2 Gas Sensor Fabricated by Mesoporous Tin Oxide Film
- An Application Possibility of Self-Ordered Mesoporous Silicate for Surface Photo Voltage (SPV) Type NO Gas Sensor (II) : Self-Ordered Mesoporous Silicate Incorporated SPV Device and Its Sensing Property Dependence on Mesostructure(Special Issue on Recent
- An Application Possibility of Self-Ordered Mesoporous Silicate for Surface Photo Voltage Type NO Gas Sensor (I) : The Characterization of Nonionic Triblock Copolymer Templated Self-Ordered Mesoporous Silicates and Preparation Their Film for Device Applica
- NO Gas Sensor Based on Surface Photovoltage System Fabricated by Self-Ordered Hexagonal Mesoporous Silicate Film : Atoms, Molecules, and Chemical Physics
- Clinicopathological study of dialysis patients with lupus nephritis
- -P168- STUDY ON MECHANISM OF REOXYGENATION INJURY IN CULTURED MYOCARDIAL CELLS : IN REFERENCE TO Ca^, FREE RADICALS
- -116-DIRECT EFFECT OF PROSTAGLANDINS ON MYOCARDIUM
- THE STUDIES ON HYPERCONTRACTION-INDUCED DAMAGES IN CULTURED MYOCARDIAL CELLS : Cardiac Metabolism : FREE COMMUNICATIONS (II) : PROCEEDINGS OF THE 49th ANNUAL SCIENTIFIC MEETING OF THE JAPANESE CIRCULATION SOCIETY
- PROSTACYCLIN (PGI_2) GENERATION IN THE RABBIT AORTA DURING THE DEVELOPMENT OF ARTERIOSCLEROSIS : PROCEEDINGS OF THE 47th ANNUAL SCIENTIFIC MEETING OF THE JAPANESE CIRCULATION SOCIETY : Myocardial Metabolism Biochemistry
- EFFECTS OF HYPOXIA ON PROSTACYCLIN GENERATION IN RABBIT AORTA : PROCEEDINGS OF THE 46th ANNUAL SCIENTIFIC MEETING OF THE JAPANESE CIRCULATION SOCIETY : Myocardial Metabolism
- THE FORMATION OF PROSTACYCLIN AND THE ACTIVITY OF PROLYLHYDROXYLASE IN EXPERIMENTAL ARTERIOSCLEROSIS : Myocardial metabolism . Biochemistry : 46th Annual Scientific Meeting, Japanese Circulation Society
- MYOCARDIAL ENERGY METABOLISM IN CONGESTIVE AND HYPERTROPHIC STATES OF CARDIOMYOPATHY IN HAMSTERS WITH ELASTASE-INDUCED EMPHYSEMA (2ND REPORT) : Myocardial metabolism . Biochemistry : 46th Annual Scientific Meeting, Japanese Circulation Society
- MYOCARDIAL ENERGY METABOLISM OF CONGESTIVE AND HYPERTROPHIC CARDIOMYOPATHY IN ELASTASE INDUCED EMPHYSEMA HAMSTER : Myocardial metabolism Biochemistry : FREE COMMUNICATIONS (Abstract) : 45 Annual Scientific Meeting, Japanese Circulation Society
- Riemann zeta function and the best constants of five series of Sobolev inequalities (Expansion of Integrable Systems)
- THE BEST CONSTANT OF SOBOLEV INEQUALITY WHICH CORRESPONDS TO SCHRODINGER OPERATOR WITH DIRAC DELTA POTENTIAL
- THE BEST CONSTANT OF SOBOLEV INEQUALITY CORRESPONDING TO DIRICHLET BOUNDARY VALUE PROBLEM FOR (-1)^ M(d/dx)^
- HEAVISIDE CABLE, THOMSON CABLE AND THE BEST CONSTANT OF A SOBOLEV-TYPE INEQUALITY
- THE BEST CONSTANT OF L^P SOBOLEV INEQUALITY CORRESPONDING TO THE PERIODIC BOUNDARY VALUE PROBLEM FOR (-1)^M (D/DX)^
- THE BEST CONSTANT OF SOBOLEV INEQUALITY WHICH CORRESPONDS TO A BENDING PROBLEM OF A STRING WITH PERIODIC BOUNDARY CONDITION
- RIEMANN ZETA FUNCTION, BERNOULLI POLYNOMIALS AND THE BEST CONSTANT OF SOBOLEV INEQUALITY
- THE BEST CONSTANT OF SOBOLEV INEQUALITY IN AN n DIMENSIONAL EUCLIDEAN SPACE
- Time-Frequency Analysis of the Blood Flow Doppler Ultrasound Signal
- Ultrasound Doppler Sinusoidal Shift Signal Analysis by Time-Frequency Distribution with New Kernel
- A Remark on the Regularity of the Coefficient Matrix Appearing in the Charge Simulation Method
- Heuristic and Exact Algorithms for the Disjunctively Constrained Knapsack Problem
- Endovascular Therapeutic Occlusion Following Bilateral Carotid Artery Bypass for Radiation-induced Carotid Artery Blowout:Case Report
- GIAMBELLI'S FORMULA AND THE BEST CONSTANT OF SOBOLEV INEQUALITY IN ONE DIMENSIONAL EUCLIDEAN SPACE
- Racemization-free Monomer : α-Hydroxyisobutyric Acid from Bio-based Lactic Acid
- Representation Formula for the Critical Points of the Tadjbakhsh-Odeh Functional and its Application
- Alteration of Oxidative Phos phorylation in Uremia
- SELECTION OF RELAXATION PROBLEMS FOR A CLASS OF ASYMMETRIC TRAVELING SALESMAN PROBLEM INSTANCES
- Time-Frequency Analysis of the Blood Flow Doppler Ultrasound Signal
- A Simple Synthetic Route for the Preparation of Tetramethylglycolide from Lactic Acid