선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 이 절에서는 다면체 F의 구조를 분석하여 (ZP) 의 표현에 사용된 부등식이 facet에 해당하는지를 밝힌다. 또한 새로운 유효부등식 (valid inequalities)을 도출하고, 도출된 부 등 식이 facet이 되기 위한 조건을 제시하기로 한다. 특수한 경우를 배제하기 위하여 모든 emE에 대해서 七罚인 것으로 가정한다.
- 본 연구에서는 네트워크 단절 문제의 특성을 추가로 규명하고 이를 이용하여 실행 가능 해를 도출하는 새로운 휴리스틱을 제시하며, 수리계획모형의 선형계획완화를 이용하여 상한을 도출할 때 유효부둥식을 이용하여 개선된 상한을 구하는 방법을 제시하기로 한다. 아 울러 충분한 계산실험을 통하여 개발된 휴리스틱의 성능을 평가하기로 한다.
- 명영 수와 김 현준 [2] 은 네트워크 단절문제 의 정수계획모형을 수립하고 선형계획 완화 문제를 이용하여 상한을 구하는 방법을 제시하였다. 본 연구에서는 수리계획모형의 실행 가능 영역을 구성하는 다면체의 구조를 분석하고, 선형계획완화를 이용하여 상한을 도출할 때 유효부둥식을 이용하여 개선된 상한을 구하는 방법을 제시하기로 한다.
- 제 약식 (6) 에 해당하는 분리 문제를 위해서 보호 노드 집합을 어떻게 구할 수 있는지 고려해 보자. 보조:! 래프 h—(k, a)를 정의하자.
가설 설정
- 특수한 경우를 배제하기 위하여 모든 emE에 대해서 七罚인 것으로 가정한다. 그리고, 사전처리 과정을 거친 후이므로 모든 径气에 대해서 c0(&.))<& 가 성립하는 것으로 가정한다. 여기서는 규명된 사실들을 증명은 생략하고 결과만을 제시하기로 한다.
- 네트워크 단절 문제는 다음과 같이 정의된다. 무방향 네트워크(undirected network), 사전에 정해진 원천노드(source node), 각 에지 (edge)마다 에지를 제거하는데 드는 비용, 에지를 제거하는데 사용할 수 있는 예산 및, 각 노드별 가중치가 주어져 있다고 가정하자. 네트워크 단절 문제의 목적은 원천노드와 연결이 끊어지는 노드들의 가중치의 합이 최대가 되 도록 에지를 제거하는 것이다.
- 두 경우 모두 NP hard에 속하는 문제이다. 본 논문에서는 무방향의 네트 워크를 가정하는데 실제로 본 논문에서 제시된 내용은 유방 향의 네트워크에도 약간의 변형을 통해서 그대로 적용이 가능하다.
- 로 표시한다. 사전에 정해진 원천노드는 노드 1로 가정한다. 두 노드 疟 y와 , 隹μ에 걸쳐 있는 에지를 e — QJ)로 표시 하 기로 하고 두 노드 f와 7.
- 원천노드를 제외한 노드들의 집합을 표시하기 위하여 比- V\{1} 을 사용한다. 주어진 그래프 G에 는 두 노드를 동일한 종단 노드로 하는 복수의 링크(multiple link)는 존재할 수 있으나 동일한 노드를 종단 노드로 하는 링크(self loop)는 존재하지 않는 것으로 가정한다. 각 에지 kE 마다 에지를 제거하는데 드는 비용을 에지를 제거하는데 사용할 수 있는 예산을 3, 각 노드의 가중치를 皿로 표시하기로 한다.
- 또한 새로운 유효부등식 (valid inequalities)을 도출하고, 도출된 부 등 식이 facet이 되기 위한 조건을 제시하기로 한다. 특수한 경우를 배제하기 위하여 모든 emE에 대해서 七罚인 것으로 가정한다. 그리고, 사전처리 과정을 거친 후이므로 모든 径气에 대해서 c0(&.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.