Mathematical programming has been used to solve many real-world problems successfully and most of them deal with situations where there is only one decision maker. In recent years, a lot of practical problems where multiple decision makers exist have been raised. A characteristic of these problems is that an action of one decision maker can influence or be influenced by other decision makers' actions. Due to the structure of these problems, it is difficult to deal with these problems with classical mathematical programming directly. If decision makers act sequentially (not simultaneously), such a decision process can be modeled as a Stackelberg game. In a Stackelberg game, the former acts first, and then the latter acts in consideration of previous actions. For a two-player Stackelberg game, decision makers are called the leader and the follower.
Multilevel programming, especially bilevel programming, has been extensively studied recently since it can model the Stackelberg games. There are many optimization problems where bilevel programming structure appears: network problems such as the max-flow problem, the shortest path problem, and the traveling salesman problem and combinatorial optimization problems such as the knapsack problem, the clique problem, and the matching problem. Among them, bilevel programming problems related to the knapsack problem have received considerable attention because the knapsack problem is fundamental to integer programming and frequently appears as a constraint for other complex problems. The bilevel knapsack problem with interdiction constraints is the most famous one among the bilevel programming problems related to the knapsack problem Therefore, in this thesis, we consider generalizations and variants of the bilevel knapsack problem.
First, we consider a generalization of the bilevel knapsack problem with interdiction constraints. Bilevel knapsack problem with interdiction constraints is a well-known bilevel knapsack problem where the leader wants to reduce the knapsack profit of the follower by interdicting a subset of items. Interdicted items cannot be selected by the follower. However, the assumption that the interdicted items cannot be selected makes it difficult to use the model for more general situations. There may exist situations where the interdicted items still can be selected by the follower with a decreased profit value. To reflect this situation, we generalize the bilevel knapsack problem with interdiction constraints in a way that the effect of interdiction is partial profit reduction of the interdicted item. Since the algorithm for the bilevel knapsack problem with interdiction constraints cannot be applied directly to solve the proposed problem, we extend the algorithm so that partial profit reductions can be handled. The algorithm is tested on randomly generated instances. Computational experiments showed the effectiveness of the proposed algorithm.
Second, we study a variant of the bilevel knapsack problem with interdiction constraint called the Stackelberg knapsack problem with weight selection. In the problem, the leader decides the weights of the leader's items instead of interdicting the items. The goal of the leader is to maximize the sum of the weights of the leader's items included in the follower's knapsack solution. There has been no exact algorithm known for the Stackelberg knapsack problem with weight selection. We derive a strict inequality system with exponentially many constraints whose feasibility can be used to obtain an optimal solution to SKPW. To overcome the difficulties in dealing with the strict inequalities, we propose two approaches. One is based on an equivalent linear inequality system with exponentially many constraints and the other is a linear programming problem with exponentially many variables which is derived using a theorem of the alternative. The resulting problems are solved using cutting planes and column generation, respectively. We present the computational experiments, comparing the optimal value obtained by the proposed algorithm and the value obtained by one of the heuristic algorithms proposed earlier in the literature. The results showed that the exact algorithm provides better solutions than the heuristic algorithm.
Third, we consider a bilevel version of the 0-1 knapsack problem with setups. The 0-1 knapsack problem with setups is a variant of the 0-1 knapsack problem, where each item belongs to one of the disjoint families of subsets and an item can be selected only if the corresponding family is selected. In the proposed problem, which we call the bilevel 0-1 knapsack problem with setups and interdiction constraints, the leader can interdict a subset of families instead of a subset of items. We observed that an optimal solution of the 0-1 knapsack problem with setups is also very similar to the critical solution in the situation where the families have already been selected. This allows us to use the property of the critical solution in our problem as well. However, it is impossible to use the critical solution directly because there exist families in 0-1 knapsack problem with setups. We introduce a new metric called family ratio to sort items and families as well. Using the family ratio, we present a problem that can give a good bound to bilevel knapsack problem with setups. The classical cutting plane method applicable to the interdiction problems and the proposed algorithm were compared through randomly generated instances. Through the experiments, it has been shown that the proposed algorithm is more effective as the number of the families interdicted increases.
수리계획법은 많은 실제 문제를 성공적으로 해결해 왔으며, 대부분의 경우 의사결정자가 한 명만 있는 상황을 다루었다. 최근에는 여러 의사결정자가 존재하는 문제들이 많이 제기되고 있다. 이러한 문제들의 특징은 한 의사결정자의 행동이 다른 의사결정자의 행동에 영향을 미치거나, 영향을 받을 수 있다는 점이다. 따라서 고전적인 수리계획법을 그대로 적용하는 것은 어려움이 따른다. 의사결정자들이 동시에 행동하는 것이 아니라 정해진 순서대로 행동한다면, 이 문제들은 Stackelberg 게임으로 모형화가 가능하다. Stackelberg 게임에서는 전자가 먼저 행동을 하고, 후자는 이전의 행동들을 고려하여 의사결정을 한다. 2인 Stackelberg 게임의 경우, 의사결정자는 리더와 팔로워로 나뉜다.
Stackelberg 게임을 해결할 수 있는 다단계 계획법, 특히 2단계 계획법이 최근 광범위하게 연구되고 있다. 다양한 2단계 계획법 문제들이 있는데, 대표적으로 최대 흐름 문제, 최단 경로 문제, 그리고 외판원 문제와 같은 네트워크 문제들과 배낭 문제, 클릭 문제, 그리고 매칭 문제와 같은 조합 최적화 문제들이 있다. 그중에서도 배낭 문제와 관련된 2단계 계획법 문제는 정수계획법의 기본이 되고, 많은 복잡한 문제의 제약으로 자주 나타난다는 점에서 관심이 높아지고 있다. 배낭 문제와 관련된 2단계 계획법 문제 중에서는 방해 제약이 있는 2단계 배낭 문제가 가장 유명하다. 본 논문에서는 방해 제약이 있는 2단계 배낭 문제의 일반화된 문제들과 변형된 문제들의 알고리즘을 연구한다.
방해 제약이 있는 2단계 배낭 문제의 일반화를 고려한다. 방해 제약이 있는 2단계 배낭 문제는 리더가 아이템의 일부를 방해하여 팔로워의 배낭 이익을 줄이는 문제이다. 이때 팔로워는 방해된 아이템을 선택할 수 없다. 하지만 방해된 아이템을 선택할 수 없다는 가정 때문에 해당 문제가 더 일반적인 상황을 다루지는 못 하게 된다. 간단한 예로, 아이템을 방해하는 것이 해당 아이템을 선택할 수는 있지만 그 가치가 감소되는 경우도 충분히 존재할 수 있기 때문이다. 이를 반영하기 위해 아이템을 방해하는 효과가 부분적인 이익 감소가 되도록 문제를 일반한다. 원래 문제에 대한 알고리즘을 일반화한 문제에 그대로 적용하기는 어렵기 때문에 해당 알고리즘을 이용하되 제안한 문제에 적용할 수 있도록 확장한다. 무작위로 생성된 예제로 알고리즘을 실험하고 실험을 통해 제안한 알고리즘의 효과를 보였다.
다음으로는 방해 제약이 있는 2단계 배낭 문제의 변형인 아이템의 무게를 정하는 Stackelberg 배낭 문제를 연구한다. 이 문제에서는 리더의 아이템들과 팔로워의 아이템들이 구분되어 있으며, 리더는 아이템을 방해하는 대신 리더의 아이템들의 무게를 정할 수 있다. 리더가 리더의 아이템들의 무게를 정하면 팔로워는 리더와 팔로워의 모든 아이템들을 고려하여 배낭 문제의 최적해를 구한다. 리더의 목적은 리더의 아이템들이 팔로워의 배낭 문제에서 선택되는 총 무게를 최대화하는 것이다. 아직까지는 이 문제를 해결하는 알고리즘이 알려져 있지 않다. 우리는 가능해의 존재여부가 Stackelberg 배낭 문제를 푸는데 이용될 수 있는 선형 부등식 시스템을 제안한다. 이 선형 부등식 시스템은 Strict 부등식을 포함하고 제약 식의 수가 기하급수적으로 많기 때문에 가능해가 존재하는지를 확인하는 것이 쉽지 않다. 이를 해결하기 위해 두 가지 방법을 제시한다. 하나는 기존 시스템과 동등하지만 Strict 부등식이 없는 선형 부등식 시스템을 제안한다. 다른 하나는 대안 이론을 이용해 변수의 수가 기하급수적으로 많은 선형계획법 문제를 제안한다. 각각을 풀기 위해 절단평면법과 열생성기을 사용하는 알고리즘을 제안한다. 제안한 알고리즘과 기존의 휴리스틱 알고리즘 중 하나를 이용해 얻은 목적함수 값을 비교하는 실험을 수행하였다. 실험을 통해 제안한 알고리즘이 휴리스틱 알고리즘이 찾아낸 해보다 더 우수한 해를 구할 수 있음을 확인하였다.
마지막으로 셋업이 있는 이진 배낭 문제의 2단계 버전을 고려한다. 셋업이 있는 이진 배낭 문제는 이진 배낭 문제의 일반화 중 하나로, 각 아이템은 분리된 패밀리 중 하나에 속하고 해당 패밀리가 선택된 경우에만 아이템을 선택할 수 있다. 제안한 문제에서 리더는 아이템의 일부 대신 패밀리의 일부를 방해할 수 있다. 셋업이 있는 이진 배낭 문제도 그 최적 해가 패밀리가 이미 선택된 상황에서는 크리티컬 해와 아주 유사함을 관찰하였다. 이를 통해 크리티컬 해로 2단계 배낭 문제를 효과적으로 해결하는 방법을 차용한다. 다만 셋업이 있는 이진 배낭 문제는 패밀리까지 고려해야 하기 때문에 기존의 정렬방식만으로는 크리티컬 해를 이용하는 것이 불가능하다. 우리는 패밀리 비율이라는 새로운 척도를 소개하고, 이를 이용하여 셋업이 있는 2단계 배낭 문제에 대해 좋은 경계값을 줄 수 있는 문제를 제시한다. 방해 문제에 적용할 수 있는 고전적인 절단 평면법과 제안한 알고리즘을 무작위로 생성된 예제를 통해 비교하였다. 실험을 통해 방해할 수 있는 패밀리의 수가 커질수록 제안한 알고리즘의 효과적임을 보였다.
