Optimization Lab

This article proposes an efficient pegging algorithm for solving separable continuous nonlinear knapsack problems with box constraints. A well-known pegging algorithm for solving this problem is the Bitran-Hax algorithm, a preferred choice for large-scale problems. However, at each iteration, it must calculate an optimal dual variable and update all free primal variables, which is time consuming. The proposed algorithm checks the box constraints implicitly using the bounds on the Lagrange multiplier without explicitly calculating primal variables at each iteration as well as updating the dual solution in a more efficient manner. Results of computational experiments have shown that the proposed algorithm consistently outperforms the Bitran-Hax in all baseline testing and two real-time application models. The proposed algorithm shows significant potential for many other mathematical models in real-world applications with straightforward extensions.

This research proposes a solving approach for the v-support vector machine (SVM) for classification problems using the modified matrix splitting method and incomplete Cholesky decomposition. With a minor modification, the dual formulation of the v-SVM classification becomes a singly linearly constrained convex quadratic program with box constraints. The Kernel Hessian matrix of the SVM problem is dense and large. The matrix splitting method combined with the projection gradient method solves the subproblem with a diagonal Hessian matrix iteratively until the solution reaches the optimum. The method can use one of several line search and updating alpha methods in the projection gradient method. The incomplete Cholesky decomposition is used for the calculation of the large scale Hessian and vectors. The newly proposed method applies for a real world classification problem of the credit prediction for small-sized Korean companies. (C) 2012 Elsevier Ltd. All rights reserved.

Customer response is a crucial aspect of service business. The ability to accurately predict which customer profiles are productive has proven invaluable in customer relationship management. An area that has received little attention in the literature on direct marketing is the class imbalance problem (the very low response rate). We propose a customer response predictive model approach combining recency, frequency, and monetary variables and support vector machine analysis. We have identified three sets of direct marketing data with a different degree of class imbalance (little, moderate, high) and used random undersampling method to reduce the degree of the imbalance problem. We report the empirical results in terms of gain values and prediction accuracy and the impact of random undersampling on customer response model performance. We also discuss these empirical results with the findings of previous studies and the implications for industry practice and future research.

In this research, we apply a scenario aggregation approach to solving the supply chain contract model formulated by two-stage stochastic programming problem. The supply chain contract can achieve the coordination between the buyer and the supplier. We formulate the stochastic programming model for a quantity-flexibility contract. The scenario aggregation method called the progressive hedging method is used to solve this problem. Experimental results show the convergence behaviour of the algorithm and the sensitivity of parameters.

The optimal control of inventory in supply chains plays a key role in the competiveness of a corporation. The inventory cost can account for half of company's logistics cost. The classical inventory models, e.g., newsvendor and EOQ models, assume either a single or infinite planning periods. However, these models may not be applied to perishable products which usually have a certain shelf life. To optimize the total logistic cost for perishable products, this paper presents a multi-period newsvendor model, and the problem is formulated as a multi-stage stochastic programming model with integer recourse decisions. We extend the progressive hedging method to solve the model efficiently. A numerical example and its sensitivity analysis are demonstrated. (C) 2014 Elsevier Ltd. All rights reserved.

The manufacturing sector as a whole has undergone remarkable changes in terms of scale, complexity and technology over the past decades and thi s applies across most modern high-technology manufacturing such as elect ronics, semiconductor, aerospace and automotive industries. In order to remain competitive, manufacturers have to produce high-quality products at low cost, and at the same time retain sufficient flexibility and to meet rapidly changing customer demands. Production planning and control (PPC) is a key role which enables the manufacturer to gain visibility a nd control over all aspects of manufacturing activities. PPC in itselff orms a subject of study, within which simulation techniques have proven themselves to be one of the most practical methodologies available to i nvestigate and evaluate manufacturing issues. In this review paper, we f ocus on state-of-the art applications of simulation techniques in PPC to demonstrate their applicability to modern manufacturing issues. The rev iew reports on academicpublications on simulation applications in manuf acturing from 2002 to 2014, incorporating surveys of peer-reviewed liter ature. The review covers three types of simulation techniques (system dy namic, discrete event simulation and agent-based simulation) and eight P PC issues (facility resource planning, capacity planning, job planning, process planning, scheduling, inventory management, production and proc ess design, purchase and supply management). Literature survey is analys ed on the basis of simulation application to PPC problems which can give a guideline for simulation technique selection and also can help for si mulation modellingin PPC problems.

This paper proposes a dynamic vehicle routing problem (DVRP) model with nonstationary stochastic travel times under traffic congestion. Depending on the traffic conditions, the travel time between tw o nodes, particularly in a city, may not be proportional to distance and changes both dynamically and stochastically over time. Considering this environment, we propose aMarkov decision process model to solv e this problem and adopt a rollout-based approach to the solution, usi ng approximate dynamic programming to avoid the curse of dimension ality. We also investigate how to estimate the probability distributio n of travel times of arcs which, reflecting reality, are considered to consist of multiple road segments. Experiments are conducted u sing a real-world problem faced by Singapore logistics/delivery compa ny and authentic road traffic information.

This paper proposes a performance analysis method by business unit for i nformatization in public sector, specifically agriculture. Performance of informatization has bee n evaluated by indicators or hierarchies which affect the development or implementation of information systems in private sectors. However, in public sector, informatization projects can be proceed only when the budget for them is assigned. This motivates us to evaluate the performance of informatization by business unit associated with the budget unit. In this paper, we suggest a novel performance measurement by business unit applied to agri cultural informatization for government projects.

Traffic congestion, road conditions, and other factors have increased the complexity of vehicle routing problems in urban areas. Travel time of a vehicle is obtained by the sum of travel times of road segments. However, the travel time of road segments may not be sufficient to estimate the travel time of a route. When a vehicle arrives at a demand site, the final customer may be a distance from the vehicle if the site is a complicated building or has a lack of parking space. In this case, we have to consider the route of persons including drivers or service persons. In this paper, the authors develop integer programming models for the vehicle and pedestrian routing problem. The proposed model provides the strategy to find the optimal route of the vehicle and pedestrians.

This paper proposes a dynamic vehicle routing problem (DVRP) model with fuzzy customer responses and suggests optimal routing strategies. Most DVRP studies have focused on how to create a new route upon the occurrence of dynamic situations such as unexpected demands. However, the customer responses have received little attention. When a pop-up demand is added to one of the planned routes, the service for some optimally planned demands may be delayed. Customers may file complaints or cancel their orders as a result of the delays. As a result, the customer response has a significant impact on current profits as well as future demands. In this research, we consider the customer response in DVRP and address it with a fuzzy number. Changing distances or defining time windows can resolve the problem of customer response. The customer responses are represented by a fuzzy rule. The new routing strategy provides the viability to reduce customer complaints and avoid losing potential customers.

본 연구는 데이터 마이닝을 이용하여 스팸메일을 분류하는 문제에 대한 해법을 제시한다. 인터넷의 보급과 전산화로 인해 이메일을 이용하는 개인이나 단체가 증가하면서 생활의 편리함과 비즈니스에서의 효율성 이 크게 향상이 되었다. 반면에 이러한 변화는 스팸메일을 수신하면서 많은 문제들을 야기시키고 있다. 스팸메일은 광고나 악의적인 목적으로 원하지 않 는 수신자에게 전달되는 이메일을 말한다. 스팸메일은 개인에게는 혼 란과 컴퓨터에 악영향을 미치고, 비즈니스에서는 중요한 업무를 방해하 는 등 악영향을◐“�있다. 이러한 스팸메일을 스팸메일함으로 보내는 방법이 많이 연구되어 왔지만 효과적인 방법에 대한 필요가 여전히 높다. 이러한 문제를 해결하기 위해서 많은 해결 방법론이 연구되어져 왔고 데 이터 마이닝이 우수한 결과를 보여줬다. 하지만 보유하고 있�데이터 의 상태가 불완전한 경우에는 데이터 마이닝 기법을 적용하기 쉽지 않다. 특히 데이터의 클레스에 대한 정보가 한쪽만 가지고 있거나 불확실 한 경우에 대해서는 일반적인 데이터 마이닝 기법은 분류모형을 찾는 것 이 어렵다. 본 논문에서는 이를 해결하기 위해 PU learning을 이용한다. 또 한 기본 데이터 마이닝 기법으로는 Support Vector Machine(SVM)을 적용하였 다. 실험 결과에서는 제시한 방법론이 스팸메일 분류에 대해 좋은 분 류모형을 제시할 수 있다는 것을 보여준다.

본 연구는 공급업체 선정문제에 대한 해법을 다룬다. 대부분의 제조업체는 공급업체 또는 공급자라고 부르는 다른 업체로부터 원재료나 曠걋� 구매하여 제품을 생산한다. 일반적으로 제조업체는 검증이 된 업체 중에서 하나나 그 이상의 공급업체를 선정하게 된다. 제품의 품질이 공급 업체와 직접적인 관련을 가지기 때문에, 공급업체 선정은 공급사슬관리에 서 중요한 문제이다. 공급업체를 선정求�것은 크게 세 가지 단계로 구성된 다: 선정기준 정의, 자격있는 업체 선정, 최종업체 선정. 첫 번째 단 계는 공급업체를 평가할 요소들을 정의하는 것인데, 기업의 정책에 좌 우된다. 두 번째 단계는 가능한 업체 중에서 자격이 있는 업체를 선정하는 문제로 분류문제라고 할 수 있다. 마지막 단계는 자격있는 업체 중에 서 최종으로 주문량을 할당하여 최종 공급업체를 선정하는 단계이다. 본 연구는 분류문제인 두 번째 문제에 중점을 둔다. 우리는 데이터 마 이닝 방법들을 사용하여 공급업체들을 분류하고 이들�성과를 비교하고 분석한다. 특히, 데이터가 균형이 맞지 않은 경우에는 support vector mac hine의 경우에 성능에서 많은 차이가 생길 수 있다.

의사결정문제는 개인적인 일 뿐만 아니라 기업이나 국가 등 많은 부분에서 일어난다. 의사결정을 하는 주체가 다양한 것처럼 의사결정을위한 기준도 다양하다. 하나의 기준으로 의사결정을 하는 경우도 있지만 대부분의 경우 여러 가지 기준을 갖고 의사결정을 하게 된다. 이것을 다기준 의사결정이라고 한다. 다기준 의사결정의 경우에는 다양한 기 준들이 의사결정에 영향을 미치게홱� 하지만 기준들이 단위가 서 로 다르고 범위도 다르기 때문에 기준들에 대한 영향도를 나타내기 위 해서는 서로 다른 단위들을淪朗臼�비교를 해야 하기 때문에 어려움이 있다 . 이러한 어려움을 해결하기 위한 다기준 의사결정 방법 중에 요구사 항 우선순위기법(TOPSIS)이 있다. TOPSIS는 매트릭스를 이용하 여 다기준을 갖는 의사결정문제에 대한 해법을 제시한다. 본 연구는 TOPSIS를 이용하여 배송채널을 선택하는 문제를 다룬다. 공급사슬과 마케팅에 서 중요한 기능을 하는 배송채널은 생산에서 최종 소비자까지의 경로를 말하 며, 최근에는 고객의 요구사항 증대와 기술의 발달에 따라 배송채널은 더욱 복잡하고 다양해졌다. 본 연구�배송채널 선택문제에 TOPSIS가 적용되는 방법과 계산방법을 소개하고 의의

이 연구는 수요정보가 점진적으로 드러나는 생산계획 문제에 대한 수리모형에 대해 논의한다. 세 가지 수리모형이 불확실성을 갖는 문제를 풀기위해 적용된다. 이들 모델링 방법들은 선형계획법, 확률론적 계획법, 동적계획법이다. 수요 불확실성에는 두 가지 형태가 있다. 하나는 수요의 변동에 대한 불확실성이고, 다른 한 가지는 수요정보가 들어나는 시점에 대한 것이다. 이 논문에서는 이들 두 가지 형태의 불확실성에 대해 다룬다. 예를 들어, 생산공정에서 수요에 대한 정보는 다른 시점들에 얻을 수 있다. 이들 시점은 원자재를 구매할 때, 제품을 생산할 때, 제품을 판매할 때이다. 이러한 두 가지 불확실성을 갖는 문제에 세 가지 수리모형을 적용한다. 선형계획법은 만일 문제가 확정적이면 최적해를 정확히 찾아준다. 확정적 선형계획법은 불확실성을 처리할 수 없다. 확률론적 계획법은 랜덤인 상황을 갖는 문제를 시나리오 기반의 접근법으로 최적해를 찾을 수 있다. 하지만 시나리오 부문제들을 많이 풀어야 하는 단점이 있다. 동적계획법은 연속적인 의사결정을 해야 하는 문제를 효과적으로 모형화 한다. 반면에 동적계획법 모형은 시나리오로 분리되기 어려운 문제에 대해서는 어려움이 있다. 이 논문은 간단한 생산계획 문제를 가지고 세 가지 모형에 대한 해를 구하는 성능을 논의한다.

의사결정나무 분류는 변수 즉 속성(Attribute)을 노드로 하여 나무를 형성해 가면서 데이터의 패턴과 규칙을 찾는 방법으로 속성인 노드에서 가지를 뻗어 나가는 분할(Splitting)방법과 속성들의 순서를 정하는 것으로 알고리즘이 구성된다. 또한 과적합을 방지하기 위해 의사결정나무의 크기를 줄이는 가지치기(Pruning)를 수행한다. 분할방법에 따라 의사결정나무의 알고리즘이 CART, CHAID, C5.0으로 나뉘고 가지치기를 하기 위한 다양한 옵션이 존재한다. 의사결정나무 분류 방법은 분할방법과 가지치기의 방식에 따라 성능에 차이가 존재한다. 또한 데이터의 종류에 따라 성능이 달라진다. 우리는 본 논문에서 어떠한 분할방법과 가지치기 옵션이 데이터의 형태에 적합한지를 비교 분석하여 데이터 형태에 따른 최적의 분할방법과 가지치기 옵션을 제시한다.즉, 데이터 및 변수를 크기별로 분류하여 어떠한 분할 알고리즘 및 가지치기가 최적조건인지 분석한다. 또한 불균형 데이터에 대해서도 조사하여 불균형 정도를 네 단계로 구분하여 불균형 정도별로 분할 알고리즘과 가지치기에 대한 분석을 실시하여 최적의 조건을 찾는다.본 연구결과는 어떠한 형태의 데이터가 주어질 때 유형에 따라 어떤 분할방법과 가지치기를 사용하는 것이 가장 적절한지 제공할 수 있어 다양한 문제와 분야에 응용될 수 있는 중요한 자료로 사용될 수 있다.

중앙집권적 공급사슬에서는 공급사슬 내에서 변수를 조절하여 최적정책을 찾을 수 있다. 반면에 분산화된 공급사슬에서는 모든 기업들에 대한 최적정책을 찾는 것은 어렵다. 이유는 각 기업들은 각자의 최적정책을 추구하고 이들 최적정책들은 서로 충돌이 일어나기 때문이다. 게임이론은 복수 참가자를 갖는 이러한 형태의 문제에 적용할 수 있고 모든 참가자를 위한 최적정책을 제공한다. 공급사슬에서 중요한 이슈 중에 하나는 가격할인정책이다. 이것은 기업의 매출에 영향을 준다. 두 회사가 있다고 가정하자. 두 회사는 서로 복수의 가격할인정책을 갖고 있고 최적정책을 찾으려고 한다. 또한 두 회사는 상대 회사의 전략이 무엇이 있는지를 알고 있고 그 전략들을 사용하면 어떤 결과가 일어나는지도 알고 있다고 가정한다. 문제는 두 회사가 윈-윈 할 수 있는 가장 좋은 전략을 찾는 것이다. 이 문제는 두 명의 참가자가 있고, 전략이 유한하고, 참가자들이 모두 이성적이라고 가정하고 있다. 따라서, 이 문제는 두 참가자 유한게임으로 모형화 할 수 있다. 이 논문에서 우리는 분산화된 공급사슬에서 두 회사의 가격할인정책에 대한 문제를 두 참가자 유한게임으로 모형화 한다. 반복적 완전열세전략 제거(IESDS) 방법이 이 문제를 위한 해법으로 이용되었다. IESDS는 두 참가자 유한게임에서 두 참가자를 위한 평형점을 찾아준다. 실험결과가 이 모형과 해법의 가능성을 보여준다.

기술 발달과 고객 수요의 변화는 제품의 다양성을 증가시키고 제조 공정에서의 복잡도를 증가시켜 생산운영 전략 수립을 어렵게 하고 있다. 화장품 산업은 고객의 수요에 대한 변화가 빠르고 다양해서 생산계획의 변경이 빈번하다. 일반적인 화장품 생산방식은 화장품 브랜드 기업들이 생산기업에 제품의 생산을 주문하는 OEM/ODM을 이용하고 있는데, 수요의 불확실성으로 인해 생산주문이 자주 변경되는 일이 발생한다. 주문변동은 생산량을 변화시키고 이미 생산한 제품에 대해서는 재고비용과 폐기비용을 유발하여 생산업체에 많은 손실을 가져올 수 있다. 이러한 구매자주문변동은 기업에 따라 차이가 있어 기업들을 분류할 수 있으면 생산업체는 주문업체에 대한 대응도와 생산계획에 큰 도움이 될 것이다. 본 논문은 생산주문업체의 주문변동을 분석하여 생산업체가 주문업체를 유형별로 분류하여 대응도를 높이고 생산을 안정화시키는 해법을 제시한다. 우리는 초기주문을 바꾸는 주문업체들의 데이터를 기반으로 데이터마이닝을 이용한 분석을 통해 주문업체의 주문변동성을 예측하고 주문업체의 유형을 분류하여 업체에 대한 대응도와 주문변동에 대한 대비를 할 수 있는 전략을 제공한다. 데이터분석 결과는 주문변동으로 인한 과잉생산과 재고비용을 줄여 총비용을 최소화 시키고 안정적인 생산운영이 가능하게 한다. 본 논문은 실제 업체의 거래 데이터에 기반한 데이터 분석과 실험결과를 보여준다.

In supply chain, there are a variety of different uncertainties including demand, service time, lead time, and so forth. Theuncertainty of demand has been commonly studied by researchers or practitioners in the field of supply chain. However, theuncertainty of upstream supply chain has also increased. A problem of uncertainty in the upstream supply chain is the fluctuationof the lead time. The stochastic lead time sometimes causes to happen so called the order crossover which is not the samesequences of the order placed and the order arrived. When the order crossover happens, ordinary inventory policies have difficultto find the optimal inventory solutions. In this research, we investigate the lead time distribution in case of the order crossoverand explore the resolutions of the inventory solution with the order crossover.

Transportation in urban area has been getting hard to fulfill the demand on time. There are various uncertainties and obstacles related with road conditions, traffic congestions, and accidents to interrupt the on-time deliveries. With this situation, the last mile logistics has been a keen issue for researchers and practitioners to find the best strategy of the problem. A way to resolve the problem is to use parcel lockers. Parcel locker is a storage that customers can pick up their products. Transportation vehicles deliver the products to parcel lockers instead of all customer sites. Using the parcel lockers, the total delivery costs can be reduced. However, the inconvenience of customer has to increase. Thus, we have to optimal solution to balance between the total delivery costs and customers inconvenience. This paper formulates a mathematical model to find the optimal solution for the vehicle routing problem and the location problem of parcel lockers. Experimental results provide the viability to find optimal strategy for the routing problem as well as the location problem.

Due to the issue of the sustainability in transportation area, the number of electric vehicles has significantly increased. Most automakers have decided or planned to manufacture the electric vehicles rather than carbon fueled vehicles. However, there are still some problems to figure out for the electric vehicles such as long charging time, driving ranges, supply of charging stations. Since the speed of growing the number of electric vehicles is faster than that of the number of charging stations, there are lack of supplies of charging stations for electric vehicles and imbalances of the location of the charging stations. Thus, the location problem of charging stations is one of important issues for the electric vehicles. Studies have conducted to find the optimal locations for the charging stations. Most studies have formulated the problem with deterministic or hierarchical models. In this paper, we have investigated the fluctuations of locations and the capacity of charging stations. We proposed a mathematical model for the location problem of charging stations with the vehicle routing problem. Numerical examples provide the strategy for the location routing problems of the electric vehicles.