정수 선형 분수 계획법 문제에 대한 파라메트릭 접근법: 전산 성능 연구를 중심으로
Parametric Approaches to Integer Linear Fractional Programming: Computational Study
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문은 목적 함수가 분수로 표현되고 제약 조건의 모든 함수가 선형이며 모든 변수가 이산형인 정수 선형 분수 계획법(Integer Linear Fractional Programming) 문제를 다룬다. 최적해를 도출하기 위해 새로운 파라메트릭(Parametric) 알고리즘을 제안하고 이를 실증적(empirical)으로 분석하였다. 기존의 파라메트릭 알고리즘(예., 뉴턴 알고리즘)은 분수 계획법 문제의 최적 함수 값에 접근하는 한 방향의 (하한) 수열 값을 생성하는 반면, 제안한 파라메트릭 알고리즘은 최적 함수 값에 수렴하는 하한과 상한 수열 값을 같이 생성하는 차이점이 있다. 또한 본 연구에서 제안한 알고리즘이 다양한 생산 및 운영 관리 문제에 효과적으로 적용할 수 있음을 보여주기 위해 잘 알려진 분수 배낭 문제(fractional knapsack problem)를 대상으로 수치적 성능과 그 효율성을 분석했다. 여러 조건을 고려한 실험 환경을 무작위로 생성하고 이러한 다양한 시나리오의 분수 배낭 문제에서 알고리즘의 성능을 뉴턴 알고리즘과 비교했다. 성능 지표로 보조 함수(auxililary function)의 평가 횟수를 측정한 결과, 본 연구에서 제안한 알고리즘이 정수 선형 분수 계획법 문제를 더 빠르고(fast) 안정적(robust)으로 푼다는 것을 알 수 있다. 이러한 알고리즘을 이용해 기존의 생산 및 운영 문제에서 비분수 형태의 목적식이 고려할 수 없었던 상황을 극복하고 새로운 결과와 의미를 도출할 수 있을 것으로 기대한다.
Abstract
In this paper, we focus on the integer linear fractional optimization problem, a special case of fractional programming where all functions in the objective function and constraints are linear and all variables are bounded and discrete. To derive the optimal solution, the parametric algorithms are considered, and the efficiency of the algorithms is investigated computationally. Unlike traditional parametric algorithms such as Newton's method, which create a unidirectional sequence approaching the optimal function value, our proposed algorithm generates both upper and lower bounds converging to this value. To demonstrate its effectiveness across various production and operations management problems, the suggested algorithms are used to solve the fractional knapsack problem by comparison to other algorithms (e.g., Newton’s method) under the randomized experimental conditions. The relative practical performance measured by the number of function calls demonstrates that the proposed algorithms are fast and robust for solving the linear fractional programs with discrete variables. Leveraging this algorithm holds the potential to overcome situations in traditional production and operations problems where non-fractional objective functions were previously unconsidered, thereby expecting to derive new outcomes and significance.
참고문헌 (23)
- 김혜선, "디지털 피킹 시스템을 위한 연관 분석 기반의 상품 배치", 한국생산관리학회지, 34(3), pp.413~434 (2023), 한국생산관리학회
- 이봉현, "조선 블록 조립과 트랜스포터 통합 일정계획 알고리즘 개발", 한국생산관리학회지, 31(4), pp.427~443 (2020), 한국생산관리학회
- 조재혁, "FRLM 기반 다기간 고속도로 화물차 전용 수소충전소 입지 선정 모형", 한국생산관리학회지, 34(3), pp.361~389 (2023), 한국생산관리학회
- Ajagekar, A., "Hybrid classical-quantum optimization techniques for solving mixed-integer programming problems in production scheduling", IEEE Transactions on Quantum Engineering, 3, pp.1~16 (2022)
- Bajalinov, E. B., "Linear-Fractional Programming Theory, Methods, Applications and Software Vol.84" (2013), Springer Science &Business Media
- Burkard, R. E., "The quickest flow problem", Zeitschrift fur Operations Research, 37(1), pp.31~58 (1993)
- Burkard, R. E., "The inverseparametric knapsack problem", European Journal of Operational Research, 83(2), pp.376~393 (1995)
- Chen, Y. F., "Fractional programming approach to two stochastic inventory problems", European Journal of Operational Research, 160(1), pp.63~71 (2005)
- Dinkelbach, W., "On nonlinear fractional programming", Management Science, 13(7), pp.492~498 (1967)
- Elomri A, "Coalition formation and cost allocation for joint replenishment systems", Production and Operations Management, 21(6), pp.1015~1027 (2012)
- Harsha, P., "A practical price optimization approach for omnichannel retailing", INFORMS Journal on Optimization, 1(3), pp.241~264 (2019)
- Ibaraki, T., "Parametric approaches to fractional programs", Mathematical Programming, 26(3), pp.345~362 (1983)
- Jin, Q., "Price discounts and personalized product assortments under multinomial logit choice model : A robust approach", IISE Transactions, 53(4), pp.453~471 (2021)
- Lin, Y. H., "Last-mile delivery : Optimal locker location under multinomial logit choice model", Transportation Research Part E : Logistics and Transportation Review, 142, pp.102059~ (2020)
- Pardalos P. M., "Global optimization of fractional programs", Journal of Global Optimization, 1(2), pp.173~182 (1991)
- Park, C. H., "Supply constrained location-distribution in notfor-profit settings", Production and Operations Management, 29(11), pp.2461~2483 (2020)
- Paul, A., "A green inventory model with the effect of carbon taxation", Annals of Operations Research, 309(1), pp.233~248 (2022)
- Rusmevichientong P, "Dynamic assortment optimization with a multinomial logit choice model and capacity constraint", Operations Research, 58(6), pp.1666~1680 (2010)
- Schaible, S., "Fractional programming. II, on dinkelbach’s algorithm", Management Science, 22(8), pp.868~873 (1976)
- Stancu-Minasian, I. M., "Fractional programming:theory, methods and applications Vol.409" (2012), Springer Science & Business Media
- Subramanian S., "A fractional programming approach for retail category price optimization", Journal of Global Optimization, 48(2), pp.263~277 (2010)
- You F., "Dinkelbach’s algorithm as an efficient method to solve a class of minlp models for largescale cyclic scheduling problems", Computers & Chemical Engineering, 33(11), pp.1879~1889 (2009)
- Yue D., "Planning and scheduling of flexible process networks under uncertainty with stochastic inventory : Minlp models and algorithm", AIChE Journal, 59(5), pp.1511~1532 (2013)