정수 선형 분수 계획법 문제에 대한 파라메트릭 접근법

Parametric Approaches to Integer Linear Fractional Programming: Computational Study

본 논문은 목적 함수가 분수로 표현되고 제약 조건의 모든 함수가 선형이며 모든 변수가 이산형인 정수 선형 분수 계획법(Integer Linear Fractional Programming) 문제를 다룬다. 최적해를 도출하기 위해 새로운 파라메트릭(Parametric) 알고리즘을 제안하고 이를 실증적(empirical)으로 분석하였다. 기존의 파라메트릭 알고리즘(예., 뉴턴 알고리즘)은 분수 계획법 문제의 최적 함수 값에 접근하는 한 방향의 (하한) 수열 값을 생성하는 반면, 제안한 파라메트릭 알고리즘은 최적 함수 값에 수렴하는 하한과 상한 수열 값을 같이 생성하는 차이점이 있다. 또한 본 연구에서 제안한 알고리즘이 다양한 생산 및 운영 관리 문제에 효과적으로 적용할 수 있음을 보여주기 위해 잘 알려진 분수 배낭 문제(fractional knapsack problem)를 대상으로 수치적 성능과 그 효율성을 분석했다. 여러 조건을 고려한 실험 환경을 무작위로 생성하고 이러한 다양한 시나리오의 분수 배낭 문제에서 알고리즘의 성능을 뉴턴 알고리즘과 비교했다. 성능 지표로 보조 함수(auxililary function)의 평가 횟수를 측정한 결과, 본 연구에서 제안한 알고리즘이 정수 선형 분수 계획법 문제를 더 빠르고(fast) 안정적(robust)으로 푼다는 것을 알 수 있다. 이러한 알고리즘을 이용해 기존의 생산 및 운영 문제에서 비분수 형태의 목적식이 고려할 수 없었던 상황을 극복하고 새로운 결과와 의미를 도출할 수 있을 것으로 기대한다.

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.