Cutting-plane Generation Methods for Binary Knapsack Problem with Generalized Upper Bounds and Chance-constrained Binary Knapsack Problem

Abstract

Optimization problems with binary decision variables, known as binary integer programs, can represent a wide range of decision-making problems in various industries. Recent algorithmic advancements in general-purpose optimization solvers have significantly improved the ability to solve a binary integer program, making it a viable computational tool for addressing real-world operational issues. One of the critical factors in this success is the use of cutting planes for the binary knapsack problem. These cutting planes enhance the formulations of problems, providing tighter relaxation for the feasible solution sets by refining the solution space. Therefore, cutting planes improve the performance of relaxation-based optimization methods such as the branch-and-bound method.

However, as industries progress rapidly, more challenging issues have arisen, which can be represented by complicated binary integer programs. The current state-of-the-art solvers may not be sufficient to handle these problems, necessitating further improvements in their capabilities. These challenges have prompted studies on variants of the binary knapsack problem, such as those involving additional or nonlinear constraints, to derive more effective cutting planes and their generation methods that can be used in solving the binary integer programs.

In this thesis, we propose efficient cutting-plane generation methods for two variants of the binary knapsack problem: the binary knapsack problem with generalized upper bounds (GKP) and the chance-constrained binary knapsack problem (CKP). Our objective is to enhance the capability of solving binary integer programs by utilizing cutting planes generated from our methods.

Firstly, we investigate cutting planes for the GKP, which can be stronger than those for the binary knapsack problem. Specifically, we consider rank-1 Chvátal-Gomory (CG) cuts for the GKP, which are well-known cutting planes that can be defined for general integer linear programs. The separation problem that generates CG cuts is known to be strongly NP-hard for general integer programs. However, we show that it can be solved in pseudo-polynomial time for the GKP. We also devise an efficient heuristic for the separation problem based on its decomposition property. Through extensive computational tests, we demonstrate that the rank-1 CG cuts significantly improve the linear programming relaxation of binary integer linear programs, compared to existing cutting planes for the GKP, within a comparable computation time.

Then, we present a novel method to strengthen rank-1 CG cuts for binary integer linear programs, improving the formulation-enhancing effect of the CG cuts. We first reveal the relationship between rank-1 CG cuts for binary integer linear programs and lifted cover inequalities for binary knapsack problems. Based on this result, our strengthening method derives a stronger cutting plane from a given rank-1 CG cut for binary integer linear programs by utilizing a lifting function of cover inequalities for binary knapsack problems. We extend the method to rank-1 CG cuts for binary integer linear programs with generalized upper bounds. Through theoretical comparison, we show that the cutting plane derived through the proposed strengthening method is stronger than those obtained through existing CG cut strengthening methods. Furthermore, computational test results show that the proposed methods can provide more enhanced formulations defined with fewer cutting planes and reduce the total computation time required to obtain the formulations.

Finally, we consider the CKP, which arises in the chance-constrained programming approach for optimization problems under uncertainty. We assume that the item weights are independently normally distributed. Then the CKP is formulated as a binary integer nonlinear program where the cutting planes for the binary knapsack problem are not valid. For the CKP, we propose an efficient lifting heuristic for its well-known cutting planes, the probabilistic cover inequalities. We first introduce a non-convex continuous relaxation for the CKP, represented as a non-convex optimization problem, and show that the relaxation provides tighter upper bounds than the existing continuous relaxations. In general, non-convex optimization problems are computationally hard to solve; however, we show that the non-convex relaxation can be solved in polynomial time. Subsequently, we devise a heuristic procedure for lifting probabilistic cover inequalities using the exact polynomial-time algorithm for the non-convex continuous relaxation for the CKP. Computational test results demonstrate that the proposed lifting heuristic outperforms the existing methods in terms of computational efficiency, while the effectiveness of the resulting lifted probabilistic cover inequalities remains competitive.

다양한 산업에서 발생하는 의사결정문제는 이진정수최적화 문제로 모형화할 수 있으며, 지난 수십년간에 걸친 그 해법의 발전은 현실의 최적화 이슈들을 해결하는데 크게 공헌해왔다. 이진정수최적화 문제의 해법을 개선시킨 주요 요인 중 하나는 이진배낭문제에 대한 절단평면(cutting plane)들의 활용이다. 이러한 절단평면들은 주어진 문제의 완화된 해집합을 더욱 정교하게 정제하여, 완화(relaxation) 기반 최적화 알고리듬의 성능을 향상시킨다. 그러나, 급격한 산업의 발전은 더욱 복잡한 이진정수최적화 문제로 모형화되는 도전적인 운영 이슈들을 발생시키고 있으며, 그 문제들에 대응하기 위한 개선된 해법들이 요구되고 있다. 이에 대한 한 가지 해결책으로써 이진정수최적화 문제에 대한 더욱 효과적인 절단평면과 그 생성 기법들을 도출하기 위해 이진배낭문제의 변형에 대한 연구들이 활발히 진행되고 있다.

본 논문에서는 그러한 이진배낭문제의 두 가지 변형, 일반화된 상한제약이 있는 이진배낭문제(binary knapsack problem with generalized upper bounds, GKP)와 확률제약이 있는 이진배낭문제(chance-constrained binary knapsack problem, CKP)에 대한 효율적인 절단평면 생성 기법을 개발하여 이진정수최적화 문제에 대한 해결 능력을 제고한다. 먼저, 이진배낭문제보다 더욱 강력한 절단평면을 도출할 수 있는 GKP에 대해서, 일반적인 선형정수최적화 문제에서 정의될 수 있는 크바탈-고모리(Chvátal-Gomory, CG) 절단평면들을 다룬다. 일반적인 선형정수최적화 문제에 대한 CG 절단평면들을 생성하는 분리(separation) 문제는 강성 NP-hard임이 증명되었으나, GKP에 대한 분리 문제는 유사다항시간(pseudo-polynomial time) 내에 해결될 수 있음을 밝힌다. 또한, GKP에 대한 분리 문제의 분해 성질에 기반하여, 효율적으로 CG 절단평면들을 생성하는 휴리스틱 분리 알고리듬도 함께 제안한다. 계산실험결과를 통해, 제안된 분리 알고리듬으로 생성된 CG 절단평면들은 기존에 알려진 GKP의 절단평면들에 비해서 비슷한 시간 내에 선형이진정수최적화문제의 선형 완화를 현저히 개선함을 확인한다.

다음으로, 선형이진정수최적화 문제의 CG 절단평면들을 강화하는 새로운 기법을 제시하여 CG 절단평면들의 모형 강화 효과를 개선한다. 우선 주어진 선형이진정수최적화문제의 CG 절단평면과 이진배낭문제에 대한 커버 부등식(cover inequality) 사이의 관계성을 밝힌다. 이 관계성에 입각하여, 커버 부등식에 대한 리프팅 함수(lifting function)를 활용해, 주어진 선형이진정수최적화문제의 CG 절단평면보다 강한 절단평면을 생성해내는 강화 기법을 제안한다. 제안된 강화 기법은 일반화된 상한제약이 있는 선형이진정수최적화 문제의 CG 절단평면에 대해서 확장된다. 이론적 비교를 통해, 제안된 강화 기법은 기존에 제시된 기법들보다 더욱 강한 절단평면을 생성함을 보인다. 더불어, 계산실험을 통해서, 제안된 강화 기법은 더 적은 절단평면으로 정의된 더욱 강화된 모형을 도출할 수 있으며, 그 모형을 얻을 때까지 소요되는 계산 시간도 감소시킨다는 것을 보인다.

마지막으로, 불확실성이 존재하는 최적화 문제에 대한 확률제약모형(chance-constrained program)에서 나타나는 CKP를 다룬다. 본 논문에서는 아이템들의 무게가 서로 독립인 정규분포를 따른다고 가정하는데, 이러한 CKP는 비선형 이진정수최적화 문제로 모형화된다. 본 논문에서는 이 CKP에 대해 잘 알려진 절단평면인 확률적 커버 부등식(probabilistic cover inequality)의 효율적인 리프팅 휴리스틱을 제시한다. 먼저 CKP에 대한 비볼록 연속 완화(non-convex continuous relaxation)를 제시하고, 기존에 제시된 다른 연속 완화들보다 더 강한 상한을 제공함을 밝힌다. CKP에 대한 비볼록 연속 완화는 일반적으로 풀기 힘든 비볼록 최적화 문제로 표현되지만, 그 완화에 대한 다항 시간 알고리듬을 제시한다. 제안하는 리프팅 휴리스틱은 CKP에 대한 비볼록 연속 완화와 그 다항 시간 알고리듬을 활용한다. 계산실험결과는 제안된 리프팅 휴리스틱이 기존에 제시된 방법들보다 압도적으로 빠른 시간내에 리프팅을 수행을 하는 반면, 그 결과로 생성된 리프팅된 확률적 커버 부등식의 효과성이 여전이 유지됨을 보여준다.