선형 제약 만족 최적화 문제를 위한 정수계획법 기반 지역 탐색 기법

황준하(Jun-Ha Hwang),김성영(Sung-Young Kim) 한국컴퓨터정보학회 2010 韓國컴퓨터情報學會論文誌 Vol.15 No.9

선형 제약 만족 최적화 문제는 선형식으로 표현 가능한 목적함수 및 복잡한 제약조건을 포함하는 조합 최적화 문제를 의미한다. 정수계획법은 이와 같은 문제를 해결하는 데 매우 효과적인 기법으로 알려져 있지만 문제의 규모가 커질 경우 준최적해를 도출하기까지 매우 많은 시간과 메모리를 요구한다. 본 논문에서는 지역 탐색과 정수계획법을 결합하여 탐색 성능을 향상할 수 있는 방안을 제시한다. 기본적으로 대상 문제의 해결을 위해 지역 탐색의 가장 단순한 형태인 단순 언덕오르기 탐색을 사용하되 이웃해 생성 시 정수계획법을 적용한다. 또한 부가적으로 초기해 생성을 위해 제약 프로그래밍을 활용한다. N-Queens 최대화 문제를 대상으로 한 실험 결과, 본 논문에서 제시한 기법을 통해 다른 탐색 기법들보다 훨씬 더 좋은 해를 도출할 수 있음을 확인할 수 있었다. Linear constraint satisfaction optimization problem is a kind of combinatorial optimization problem involving linearly expressed objective function and complex constraints. Integer programming is known as a very effective technique for such problem but require very much time and memory until finding a suboptimal solution. In this paper, we propose a method to improve the search performance by integrating local search and integer programming. Basically, simple hill-climbing search, which is the simplest form of local search, is used to solve the given problem and integer programming is applied to generate a neighbor solution. In addition, constraint programming is used to generate an initial solution. Through the experimental results using N-Queens maximization problems, we confirmed that the proposed method can produce far better solutions than any other search methods.

Mixed Integer Linear Programming을 이용한 온칩 크로스바 네트워크 토폴로지 합성

전민제(Minje Jun),정의영(Eui-Young Chung) 대한전자공학회 2013 전자공학회논문지 Vol.50 No.1

다선택 다차원 배낭 문제를 위한 정수 계획법 기반 지역 탐색

황준하(Junha Hwang) 한국컴퓨터정보학회 2018 韓國컴퓨터情報學會論文誌 Vol.23 No.12

The multiple-choice multidimensional knapsack problem (MMKP) is a variant of the well known 0-1 knapsack problem, which is known as an NP-hard problem. This paper proposes a method for solving the MMKP using the integer programming-based local search (IPbLS). IPbLS is a kind of a local search and uses integer programming to generate a neighbor solution. The most important thing in IPbLS is the way to select items participating in the next integer programming step. In this paper, three ways to select items are introduced and compared on 37 well-known benchmark data instances. Experimental results shows that the method using linear programming is the best for the MMKP. It also shows that the proposed method can find the equal or better solutions than the best known solutions in 23 data instances, and the new better solutions in 13 instances.

정찰 임무 수행을 위한 혼합 정수계획법 기반의 다중 무인기 협업 기법

이중현,김현진 한국항공우주학회 2015 한국항공우주학회 학술발표회 논문집 Vol.2015 No.11

본 논문에서는 특정 지역을 다수 또는 단일의 무인기가 정찰해야하는 상황에서 다중 무인기 시스템이 지속적인 정찰 임무를 수행하는 문제를 정식화 하고, 혼합 정수계획법을 통해 접근한다. 정찰 임무에 대한 기존 연구들이 동일한 중요도를 갖는 지역들만을 고려한 반면, 본 논문에서는 중요도가 각기 다르며 시간과 정찰 현황에 따라 변화하는 지역들을 고려하여 무인기들을 할당하고 경로를 계획하는 기법을 사용하였다. 또한 무인기들의 협업을 필요로 하는 특수 임무를 위한 협업 프로토콜을 설계하였다. 각 지역에 정의된 불확실도가 높을 때 해당 지역의 중요도가 높아지며 이 불확실도는 정찰을 통해 감소된다고 설정하고, 지역 전체의 불확실도 합을 최소화시키는 조건으로 환경을 탐색/정찰하는 임무 시뮬레이션 수행하였다. 이를 통해 협업 프로토콜이 적절히 동작하여 지역 전체의 불확실도 값이 시간이 지남에 따라 0으로 수렴하는 결과를 얻을 수 있었다. In the past years, cooperative operation of multiple UAVs has attracted considerable research interests for coverage and search of broad and complex areas. Unlike other complete coverage problems, in this surveillance problem, each location in the environment has different priority that also changes through surveillance. The uncertainty level of each location determines priority and it decreases with surveillance. In this paper, we propose a cooperative path planning algorithm for an efficient surveillance operation of multiple UAVs using mixed integer linear programming. The cost function to be minimized is the uncertainty level over the whole region and the protocols for the cooperative movements are designed. Simulation results show that the task allocation works appropriately and the uncertainty level converges to zero.

시간대별 차등요금제에서 정수선형계획을 이용한 부하계획법

김광원(Gwang Won Kim) 한국조명·전기설비학회 2020 조명·전기설비학회논문지 Vol.34 No.4

Load scheduling is a kind of demand response. It is useful for saving electricity bill and for protection of the environment as well. This paper presents a linear programming based load scheduling method under time-of-use rate; all the decision variables are integer and can be 0 or 1. In the proposed method, practical time-related conditions among loads are sincerely considered and another condition of power limit is considered also. The number of decision variables is not much, which is helpful to understand the proposed idea and to get optimal results by integer linear programming. In the case study, the proposed method is applied to a realistic problem considering various situations to show its effectiveness. The proposed method is expected to be applied usefully to energy management system(EMS) for home or factory as well.

정수 선형 계획법을 이용한 주택용 부하 균등화 최적 스케쥴링

성백섭,최상봉 조선대학교 공학기술연구원 2024 공학기술논문지 Vol.17 No.2

In this paper, we propose an optimal power demand scheduling algorithm for residential load equalization in a smart grid using integer linear programming. The purpose of the proposed algorithm is to equalize the daily hourly load by minimizing the hourly peak load. In addition, the proposed algorithm first divides residential loads into shiftable loads and non-shiftable loads, and secondly, the shiftable loads are again power-shiftable and time-shiftable. By classifying the load into possible loads, a scheduling was established to optimize each power load and power use time. As a result of applying this optimization algorithm to each electrical device in the residential load, it was analyzed that the result was obtained by minimizing the hourly peak load and reducing the daily hourly peak load.

Multi-UAV Routing with Priority using Mixed Integer Linear Programming

Youkyung Hong,Sunggoo Jung,Suseong Kim,Jihun Cha 제어로봇시스템학회 2020 제어로봇시스템학회 국제학술대회 논문집 Vol.2020 No.10

This study proposes a new mission planning method to perform routing with multiple quadrotors. Unlike conventional routing missions, this study considers the specialized routing mission for quadrotors where there is a visit priority between nodes, and there is a task to be performed at the node. One of our contributions is that a multi-layered hierarchical architecture is designed for mission planning itself at the top level, and for interworking with path planning and flight control required at the lower levels. In mission planning, to determine the optimal pair between agents and visiting nodes and the optimal order of nodes, the optimization problem is designed and solved based on mixed-integer linear programming. Furthermore, we evaluate our method by performing MATLAB and Gazebo co-simulation in a ROS environment.

Clustering Algorithm of Hierarchical Structures in Large-Scale Wireless Sensor and Actuator Networks

Pham Tran Anh Quang,김동성 한국통신학회 2015 Journal of communications and networks Vol.17 No.5

In this study, we propose a clustering algorithm to enhance the performance of wireless sensor and actuator networks (WSANs). In each cluster, a multi-level hierarchical structure can be applied to reduce energy consumption. In addition to the cluster head, some nodes can be selected as intermediate nodes (INs). Each IN manages a subcluster that includes its neighbors. INs aggregate data from members in its subcluster, then send them to the cluster head. The selection of intermediate nodes aiming to optimize energy consumption can be considered high computational complexity mixed-integer linear programming. Therefore, a heuristic lowest energy path searching algorithm is proposed to reduce computational time. Moreover, a channel assignment scheme for subclusters is proposed to minimize interference between neighboring subclusters, thereby increasing aggregated throughput. Simulation results confirm that the proposed scheme can prolong network lifetime inWSANs.

Optimizing Adaptive QoS for Data Transfers in Software-Defined Networks

Eun-Sung Jung(정은성) 대한전자공학회 2021 전자공학회논문지 Vol.58 No.10

워크플로우 분할에 기반한 복합 웹 서비스의 빠른 선택

장재호(Jae-Ho Jang),신동훈(Dong-Hoon Shin),이경호(Kyong-Ho Lee) 한국정보과학회 2007 정보과학회논문지 : 소프트웨어 및 응용 Vol.34 No.5

복합 웹 서비스 선택은 서비스의 기능만을 명시한 추상 워크플로우에 바인딩 정보를 추가하여 주어진 QoS 요구사항을 만족하는 복합 웹 서비스를 구성하는 과정이다. 웹 서비스의 급격한 증가와 QoS가 동적으로 변하는 웹 서비스 환경을 고려할 때 주어진 QoS 요구사항을 만족하는 복합 웹 서비스의 빠른 선택이 중요하다. 본 논문은 워크플로우 분할에 기반하여 복합 웹 서비스를 빠르게 선택하는 방법을 제안한다. 제안된 방법은 추상 워크플로우를 두 개의 서브 워크플로우로 분할하여 선택 과정에서 고려되는 후보 서비스의 수를 줄인다. 분할된 워크플로우의 QoS 요구사항은 원래의 QoS 요구사항을 분해함으로서 생성한다. QoS 요구사항의 분해는 휴리스틱에 기반하기 때문에 워크플로우 분할 시 적절한 복합 웹 서비스를 선택하지 못할 가능성이 있다. 이러한 실패를 줄이기 위해 주어진 QoS 요구사항의 제약정도를 정의하고 적절한 제약정도를 가지는 요구사항에 한해 워크플로우를 분할한다. 서비스 선택은 mixed integer linear programming을 이용하여 해결한다. 실험 결과 제안된 워크플로우 분할 방법은 99% 이상의 성공률을 보였다. 특히 워크플로우 분할 시 모든 경우에 대해서 복합 웹 서비스를 보다 빠르게 선택하였으며 이때 선택된 복합 웹 서비스의 QoS는 최적 서비스와 5%미만의 차이를 보였다. Executable composite Web services are selected by binding a given abstract workflow with the specific Web services that satisfy given QoS requirements. Considering the rapidly increasing number of Web services and their highly dynamic QoS environment, the fast selection of composite services is important. This paper presents a method for quality driven comosite Web services selection based on a workflow partition strategy. The proposed method partitions an abstract workflow into two sub-workflows to decrease the number of candidate services that should be considered. The QoS requirement is also decomposed for each partitioned workflow. Since the decomposition of a QoS requirement is based on heuristics, the selection might fail to find composite Web services. To avoid such a failure, the tightness of a QoS requirement is defined and a workflow is determined to be partitioned according to the tightness. A mixed integer linear programming is utilized for the efficient service selection. Experimental results show that the success rate of partitioning is above 99%. Particularly, the proposed method performs faster and selects composite services whose qualities are not significantly different (less than 5%) from the optimal one.