지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- 한국경영과학회 Management Science and Financial Engineering International Journal of Management Science Vol.10 No.1
- 발행연도
- 2004.5
- 수록면
- 97 - 106 (10page)
이용수
초록· 키워드
오류제보하기
In this paper, we propose an effective cut generation method based on the Chvatal-Gomory procedure for a variable-capacity (0,1)-Knapsack problem with two general invariables. We first derive a class of valid inequalities for the problem using Chvatal-Gomory procedure, then analyze the associated separation problem. Based on the results, we show that there exists a pseudo-polynomial time algorithm to solve the separation problem. By analyzing the theoretical strength of the inequalities which can be generated by the proposed cut generation method, we show that generated inequalties define facets under mild conditions. We also extend the result to the case in which a nontrivial upper bound is imposed on a general integer variable.
목차
ABSTRACT
1. INTRODUCTION
2. A CUTTING-PLANE GENERATION METHOD
3. STRENGTH OF THE GENERATED INEQUALITIES
4. AN EXTENSION
5. CONCLUDING REMARKS
REFERENCES
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
유한 정수 변수를 포함한 가변용량 (0, 1)-배낭문제에 대한 절단평면
한국경영과학회 학술대회논문집
2004 .02
-
On the Separation of the Rank-1 Chvatal-Gomory Inequalities for the Fixed-Charge 0-1 Knapsack Problem
한국경영과학회지
2011 .06
-
Notes on Reducing Mixed Integer Knapsack Problems
한국경영과학회지
1992 .06
-
Fractional Surrogate-Knapsack Cuts for Integer Progrms
Management Science and Financial Engineering
2002 .11
-
용량이 변화하는 ( 0 , 1 ) - 배낭문제에 대한 절단평면 생성방안 ( A Cut Generation Method for the ( 0 , 1 ) - Knapsack problem with a Variable Capacity )
한국경영과학회지
2000 .09
-
Cover Inequalities for the Robust Knapsack Problem
Management Science and Financial Engineering
2008 .05
-
Multiple Choice Knapsack-based Heuristic Algorithm for Paper Cutting Optimization
한국경영과학회 학술대회논문집
2013 .05
-
An Analysis of the Relationship between Problem Characteristics and Algorithm Performance : A Case Study on 0-1 Knapsack Problems
한국경영과학회지
2006 .03
-
Lifting Cover Inequalities for the Precedence - Constrained Knapsack Problem
한국경영과학회 학술대회논문집
1994 .01
-
Computational Study of Cutting Planes for a Lot-Sizing Problem in Branch-and-Cut Algorithm
한국경영과학회지
2015 .08
-
On the Stochastic Knapsack Value Function for Random Items of Multiple Classes
한국경영과학회 학술대회논문집
1993 .01
-
FPTAS and pseudo-polynomial separability of integral hull of generalized knapsack problem
한국경영과학회 학술대회논문집
2004 .11
-
[A1 최적화] 혼합정수계획법을 위한 분지한계법의 효율적인 구현
한국경영과학회 학술대회논문집
2002 .06
-
A Solution Approach for Cardinality Constrained Knapsack Problem
한국경영과학회 학술대회논문집
2012 .05
-
Gilmore & Gomory의 2차원 평면절단 기법의 효율화에 관한 연구
한국경영과학회 학술대회논문집
1994 .01
-
[Session B1 생산일정/수리계획]About fully polynomial approximability of the generalized knapsack problem
한국경영과학회 학술대회논문집
2003 .11
-
An Interactive Method for Multicriteria Simulation Optimization with Integer Variables
한국경영과학회 학술대회논문집
1994 .01
-
Separation of Lifted Inequalities for 0-1 Mixed-Integer Bilinear Covering Sets
한국경영과학회 학술대회논문집
2018 .04
-
균형할당 설비 입지 결정 문제 해결을 위한 알고리즘 개발
한국경영과학회 학술대회논문집
2011 .05
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-325-014011008