기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
고정비용 0-1 배낭문제에 대한 크바탈-고모리 부등식의 분리문제에 관한 연구
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 고정비용 0-1 배낭문제에 대한 크바탈-고모리 부등식의 분리문제에 관한 연구
  • On the Separation of the Rank-1 Chvatal-Gomory Inequalities for the Fixed-Charge 0-1 Knapsack Problem
저자명
박경철,이경식,Park. Kyung-Chul,Lee. Kyung-Sik
간행물명
韓國經營科學會誌
권/호정보
2011년|36권 2호|pp.43-50 (8 pages)
발행정보
한국경영과학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

We consider the separation problem of the rank-1 Chvatal-Gomory (C-G) inequalities for the 0-1 knapsack problem with the knapsack capacity defined by an additional binary variable, which we call the fixed-charge 0-1 knapsack problem. We analyze the structural properties of the optimal solutions to the separation problem and show that the separation problem can be solved in pseudo-polynomial time. By using the result, we also show that the existence of a pseudo-polynomial time algorithm for the separation problem of the rank-1 C-G inequalities of the ordinary 0-1 knapsack problem.