Earticle

The wireless mesh network (WMN) is a next-generation technology for data networking that has the advantage in cost and the flexibility in its construction because of not requiring the infra-structure such as the ethernet. This paper focuses on the optimal link scheduling problem under the wireless mesh network to effectuate real-time streaming by using the constraint programming. In particular, Under the limitation of half-duplex transmission in wireless nodes, this paper proposes a solution method to minimize the makespan in scheduling packet transmission from wireless nodes to the gateway in a WMN with no packet transmission conflicts due to the half-duplex transmission. It discusses the conflicts in packet transmission and deduces the condition of feasible schedules, which defines the model for the constraint programming. Finally it comparatively shows and discusses the results using two constraint programming solvers, Gecode and the IBM ILOG CP solver.

This paper presents an approach for extending the constraint model defined for conformity testing of a given method of class to its overriding method in subclass using inheritance principle. The main objective of the proposed work is to find the relationship between the test model of an overriding method and its overridden method using the constraint propagation. Our approach shows that the test cases developed for testing an original method can be used for testing its overriding method in a subclass and then the number of test cases can be reduced considerably. The implementation of this approach is based on a random generation of test data and analysis by formal proof.

Decision tree induction has gained its popularity as an effective automated method for data classification mainly because of its simple, easy-to-understand, and noise-tolerant characteristics. The induced tree reveals the most informative attributes that can best characterize training data and accurately predict classes of unseen data. Despite its predictive power, the tree structure can be overly expanded or deeply grown when the training data do not show explicit patterns. Such bushy and deep trees are difficult to comprehend and interpret by humans. We thus propose a logic-based method to query over a complicate tree structure to extract only parts of the tree model that are really relevant to users’ interest. The implementation using ECLiPSe constraint language to perform constrained search over a decision tree model is given in this paper. The illustrative examples on medical domains support our hypothesis regarding simplicity of constrained tree-based patterns.

The course timetabling problem is a problem assigning a set of subjects to the given classrooms and different timeslots, while satisfying various hard constraints and soft constraints. This problem is defined as a constraint satisfaction optimization problem and is known as an NP-complete problem. Various methods has been proposed such as integer programming, constraint programming and local search methods to solve a variety of course timetabling problems. In this paper, we propose an iterative improvement search method to solve the problem based on constraint programming. First, an initial solution satisfying all the hard constraints is obtained by constraint programming, and then the solution is repeatedly improved using constraint programming again by adding new constraints to improve the quality of the soft constraints. Through experimental results, we confirmed that the proposed method can find far better solutions in a shorter time than the manual method.

Resource Constrained Dynamic Multi-Projects Scheduling (RCDMPS) is intended to schedule activities of two or more projects sequentially arriving at die shop under restricted resources. The aim of this paper is to develop a new problem solving method for RCDMPS to make an effect schedule based by constraint programming. The constraint-based scheduling method employs ILOG Solver which is C++ constraint reasoning library for solving complex resource management problems and ILOG Schedule which is a add-on library to ILOG Solver dedicated to solving scheduling problems. And this method interfaces with ILOG Views so that the result of scheduling displays with Gantt chart. The scheduling method suggested in this paper was applied to a company scheduling problem and compared with the other heuristic methods, and then it shows that the new scheduling system has more preference.

The course timetabling problem is a kind of very complex combinatorial optimization problems, which is known as an NP-complete problem. Sometimes a given course timetabling problem can be accompanied by many constraints. At this time, even if only one constraint is violated, it can be an infeasible timetable. Therefore, it is very difficult to make an automated course timetabling system for a complex real-world course timetabling problem. This paper introduces an automated course timetabling system using constraint programming. The target problem has 26 constraints in total, and they are expressed as 24 constraints and an objective function in constraint programming. Currently, we are making a timetable through this system and applying the result to the actual class. Members' satisfaction is also much higher than manual results. We expect this paper can be a guide for making an automated course timetabling system.

This paper extends existing research on building-volume optimization (BVO), evaluating the potential of the models practical implementation. It undertakes and discusses a representative building-volume design to examine the implementation of the BVO model as possible decision-support at an early design stage. In order to determine its usefulness to develop sustainable building designs, it focuses minimizing their foreseen life cycle cost (LCC), validating that, with the help of a proposed search strategy, the suggested BVO model can generate cost-effective and site-specific building-volume designs. In doing so, the approach underlines the ability to serve as a meaningful decision-support tool that allows designers to consider building-volume design alternatives at a design phase where design decisions in reference to their implied LCC are difficult to achieve. Results also confirmed the potential strengths of creating building-volume solutions, which can be used as a reference for ongoing development of architectural designs.

Scheduling of a block assembly line in a shipyard is commonly known as the Permutation Flow-shop Scheduling Problem (PFSP) in Operation Research (OR), which has been extensively studied in various papers since the 1950s. However, existing solutions often involve simplifying real-world problems with certain assumptions, limiting their practical applicability. In recent times, Constraint Programming (CP) has emerged as a strong alternative to exact algorithms and has been successfully applied to various PFSP problems, addressing the limitations of exact algorithms. In light of this, our study proposes a two-step optimization process to overcome these limitations. First, a new PFSP problem, Multi-Objective PFSP with hard due date constraint (MOPFSP-hd) is introduced. The problem is solved with CP algorithm. Next, the feasibility and objective value of the optimized solution is validated using Discrete-Event Simulation (DES). Two industrial cases are conducted to evaluate the performance of our proposed framework. The experimental results from both cases demonstrated a significant improvement in makespan compared to manually planned schedule. Additionally, the solutions derived from our proposed model are reported to be feasible, while the manually planned schedules are often infeasible by not satisfying all the constraints or encountering delays. Finally, the difference between the objectives calculated from CP and DES model is analyzed quantitatively using Critical Path Method (CPM).

Locomotive scheduling in railway systems experiences many difficulties because of the complex interrelations among resources, knowledge and various constraints. Artificial intelligence technology has been applied to solve these scheduling problems. These technologies have proved to be efficient in representing knowledge and rules for complex scheduling problems. In this paper, we have applied the CSP (Constraints Satisfaction Problems) programming technique, one of the AI techniques, to solve the problems associated with locomotive scheduling. This method is more effective at solving complex scheduling problems than available mathematical programming techniques. The advanced locomotive scheduling system using the CSP programming technique is realized based on the actual timetable of the Saemaul type train on the Kyong-bu line. In this paper, an overview of the CSP programming technique is described, the modeling of domain and constraints is represented and the experimental results are compared with the real-world existing schedule. It is verified that the scheduling results by CSP programming are superior to existing scheduling performed by human experts. The executing time for locomotive scheduling is remarkably reduced to within several decade seconds, something requiring several days in the case of locomotive scheduling by human experts.

다목적(多目的) 산지이용(山地利用)은 산지이용(山地利用)의 효율성(效率性)을 제고(提高)하기 위한 경제학(經濟學)의 한 응용분야로서, 외국(外國)에서 임업경영(林業經營)에 널리 사용(使用)하는 기법(技法)이다. 본고(本稿)에서는 다목적(多目的) 경영(經營)을 위해 사용(使用)되는 수리계획법(數理計劃法)의 일종인 STEM과 제약조건법(制約條件法)을 임업분야(林業分野)에 도입 적용하여 가상자료에 의거 이들 방법간(方法間)의 장(長) 단점(短點)을 비교(比較) 검토(檢討)하였다.

The idea of multiple-use of forest land is tile one field of economics to improve the efficiency of forest land, and is the famous management technique widely used in the developed forestry country. This paper introduces the STEM and the constraint method, which is one kind of mathematical programming techniques used for multiple forest Land use, and discusses the differences between these two methods by using the hypothetical data.

본 논문에서는 강의 시간표 최적화를 위한 제약 프로그래밍의 적용 방안을 제시한다. 제약 프로그래밍은 제약 만족 문제를 해결하기 위한 기법으로 대상 문제를 결정 변수, 도메인, 제약조건으로 표현한다. 본 논문에서는 시간표 작성 최적화 문제의 결정 변수로 강의실, 요일, 교시를 사용하였으며, 추가로 요일과 교시를 결합한 변수를 사용함으로써 보다 쉽게 제약 조건을 표현할 수 있도록 하였다. 또한 제약 프로그래밍에 의해 도출된 초기해를 또 다시 제약 프로그래밍을 통해 반복적으로 개선함으로써 더 좋은 강의 시간표를 작성할 수 있도록 하였다. 특정 학과의 강의 시간표 문제를 대상으로 한 실험 결과, 본 논문에서 제안한 방법을 통해 보다 빠른 시간 내에 초기해를 도출할 수 있을 뿐 아니라 최종적으로 더 좋은 해의 도출이 가능함을 확인하였다.

지수귀문도는 18세기 조선 학자 최석정이 고안한 조합 퍼즐이다. 마방진처럼 특정 부분의 합이 같도록 숫자를 배열하는 문제이지만, 배열 모양이 육각형 형태이다. 특정 형태의 지수귀문도는 풀이법이 알려져 있지만, 일반적인 형태의 해는 찾기가 어렵다. 그래서 조합 검색 기법을 시험하는 데 좋은 문제이다. 이 논문은 제약 프로그래밍 기법을 이용하여 지금까지 알려진 것보다 훨씬 큰 지수귀문도의 해를 찾아내는 방법을 소개한다. 그리고 순수 제약 프로그래밍만으로는 한계에 부딪칠 수 밖에 없는 이유를 논의하고, 여기에 기계 학습법을 조합하는 연구 방향을 제시한다.

The hexagonal tortoise (jisuguimundo) is an 18th century Korean combinatorial problem. As in magic square problems, it requires allocating numbers to a tiling, in such a way that specific sums are conserved. Unlike magic squares, however, the tiling is hexagonal. While general solutions for some very specific shapes of tilings are known, in general they are difficult to find, so that the problem becomes a useful playground for combinatorial search methods. We present constraint programming methods which have been able to find solutions an order of magnitude larger than previous methods. We discuss why it will be difficult to extend pure constraint programming methods much further, and propose a research direction combining constraint programming and learning methods.

선석계획 및 크레인 일정계획은 컨테이너 터미널에서 입항하는 선박들의 빈번한 변동상황에 능동적으로 대처하고 유연하면서도 신속한 의사결정이 가능하도록 여러 명의 전문가가 장기적인 계획을 바탕으로 지속적으로 수정 보완해 나가는 방법으로 이루어지고 있다. 본 논문에서는 선사 및 컨테이너 터미널에서 수시로 변경되는 다양한 요구조건을 수용하는 최적의 선석 및 크레인 일정계획 수립을 위하여 제약만족기법과 휴리스틱 교정(Heuristic Repair)기법을 이용하였다. 선석계획 및 크레인 일정 계획문제는 기본적으로 제약조건 만족문제로 정형화할 수 있지만 선박의 접안위치를 결정하는 문제는 목적함수를 가지는 최적화문제이다. 따라서 이 문제는 제약조건 만족문제와 최적화문제가 혼합된 문제(CSOP, Constraint Satisfaction and Optimization Problem)로 볼 수 있다. 이러한 문제를 해결하기 위해서 각 선박의 최적 전압위치를 찾고 최우선 순위 선박의 최적 접안위치로부터 주어진 모든 제약조건을 만족하는 해를 찾는 탐색기법을 활용했고 휴리스틱 교정기법을 사용해서 제약만족기법에서 찾은 해를 교정했다. 우선순위가 가장 높은 선박부터 탐색을 하기 위해 Variable Ordering 기법을 사용했고 그 선박의 최적 접안위치부터 탐색을 해 나가는 Value Ordering 기법을 사용하였다. 실제 부산 신선대 컨테이너 터미널의 선석계획자료를 사용해서 실험을 하였다.

Constraint Programming is an appealing technology for modeling and solving various real-world problems. and metaheuristic is the most successful technique available for solving large real-world vehicle routing problems. Constraint Programming and metaheuristic are complementary to each other. This paper describes how iterative improvement techniques can be used in a Constraint Programming framework(LOG Solver and ILOG Dispatcher) for Vehicle Routing Problem. As local search gets trapped in local solution, the improvement techniques are used in conjunction with metaheuristic method.

The wireless mesh network (WMN) is a next-generation technology for data networking that has the advantage in cost and the flexibility in its construction because of not requiring the infra-structure such as the ethernet. This paper focuses on the optimal link scheduling problem under the wireless mesh network to effectuate real-time streaming by using the constraint programming. In particular, Under the limitation of half-duplex transmission in wireless nodes, this paper proposes a solution method to minimize the makespan in scheduling packet transmission from wireless nodes to the gateway in a WMN with no packet transmission conflicts due to the half-duplex transmission. It discusses the conflicts in packet transmission and deduces the condition of feasible schedules, which defines the model for the constraint programming. Finally it comparatively shows and discusses the results using two constraint programming solvers, Gecode and the IBM ILOG CP solver.

생물학적 서열의 구조 검색은 생물학적 특성을 예측하는데 많은 도움을 주며, 서열에서 나타나는 구조의 패턴은 촘스키의 형식 언어로 기술 가능하다. 본 논문에서는 문맥무관문법의 확장된 표기법인 DCG를 이용하여 구조 검색을 위한 구조 패턴의 생성 규칙을 정의하였다. 또한 구조 검색의 효율향상을 위하여 구조와 관련한 제한(constraint)을 정의하였고 이를 제한 논리 프로그래밍 언어로 구현하였다. 구현된 구조 검색 엔진은 웹 인터페이스를 통하여 접근할 수 있다.