12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015)
Buy conference proceeding
 Location: Luoyang, China
 Conference date: 2124 Aug. 2015
 ISBN: 9781785610851
 Conference number: CP673
1  20 of 25 items found

A method for generating colorings over graph automorphism
 Author(s): Fei He and H. Nagamochi
 + Show details  Hide details

p.
12 .
(1)
Given a graph G = (V, E) with a set W ⊆ V of vertices, we enumerate colorings to W such that for every two enumerated colorings c and c' the corresponding colored graphs (G, c) and (G, c') are not isomorphic. This problem has an important application in the study of isomers of chemical graphs such as generation of benzen isomers from a treelike chemical graph structure. The number of such colorings can be computed efficiently based on Polya's theorem. However, enumerating each from the set of these colorings without using a large space is a challenging problem in general. In this paper, we propose a method for enumerating these colorings when the automorphisms of G are determined by two axial symmetries, and show that our algorithm can be implemented to run in polynomial delay and polynomial space.

Polynomialspace exact algorithm for TSP in degree5 graphs
 Author(s): N.M. Yunos ; A. Shurbevski ; H. Nagamochi
 + Show details  Hide details

p.
14 .
(1)
The Traveling Salesman Problem (TSP) is one of the most wellknown NPhard optimization problems. Following a recent trend of research which focuses on developing algorithms for special types of TSP instances, namely graphs of limited degree, and thus alleviating a part of the time and space complexity, we present a polynomialspace branching algorithm for the TSP in graphs with degree at most 5, and show that it has a running time of O*(2.4723n). To the best of our knowledge, this is the first exact algorithm specialized to graphs of such high degree. While the base of the exponent in the running time bound is greater than two, our algorithm uses space merely polynomial in an input instance size, and thus by far outperforms Gurevich and Shelah's O*(4^{n}n^{Iοg n}) polynomialspace exact algorithm for the general TSP (Siam Journal of Computation, Vol. 16, No. 3, pp. 486502, 1987). In the analysis of the running time, we use the measureandconquer method, and we develop a set of branching rules which foster the analysis of the running time.

An Efficient Algorithm for Linear SemiInfinite Programming over Positive Polynomials
 Author(s): Meiling Xu and Zongwei Luo
 + Show details  Hide details

p.
4 .
(1)
This paper describes an efficient implementation of a form of linear semiinfinite programming (LSIP). We look at maximizing (minimizing) a linear function over a set of constraints formed by positive trigonometric polynomials. Previous studies about LSIP are formulated using semidefinite programming (SDP), this is typically done by using the Kalman Yakubovich Popov (KYP) lemma or using a trace operation involving a Grammian matrix, which can be computationally expensive. The proposed algorithm is based on simplex method that directly solves the LSIP without any parameterization. Numerical results show that the proposed LISP algorithm is significantly more efficient than existing SDP solvers using KYP lemma and Grammian matrix, in both execution time and memory.

Computational complexity of inverse word search problem
 Author(s): H. Ito and S. Seki
 + Show details  Hide details

p.
4 .
(1)
Word search is a classical puzzle to search for all given words on a given assignment of letters to a rectangular grid (matrix). This problem is clearly in P. The inverse of this problem is more difficult, which asks to assign letters in a given alphabet to a matrix of given size so that every word in a given wordset can be found horizontally, vertically, or diagonally. This problem is in NP; it admits a trivial polynomialsize certificate. We prove its NPhardness. It turns out to be so even under the following restrictions: 1) the alphabet size is 2 (binary) and 2) all the words to be found are of length at most 2. These results are optimal in the sense that decreasing these bounds 2 to 1 makes the problem be trivially in P.

A method for calculating probability of scores for men's team competition in artistic gymnastics
 Author(s): N. Hirotsu ; M. Harada ; M. Kano
 + Show details  Hide details

p.
4 .
(1)
In this paper, we propose a method for calculating probability of scores for men's team competition in artistic gymnastics. We here assume each gymnast's score as a normal distribution and provide a mathematical formulation for 654 format in the team competition. By setting the different mean and standard deviation (SD) of the normal distribution, we calculate the distributions of the team score, and obtain the relationship between the mean and SD of each gymnast and the expected number of the team score. We demonstrate an application of this method in the selection of five gymnasts to compete in each event.

Replacement first and last for a parallel system with constant and random units
 Author(s): Xufeng Zhao ; Cunhua Qian ; S. Nakamura ; T. Nakagawa
 + Show details  Hide details

p.
5 .
(1)
This paper observes optimal replacement times for a parallel system with n units, when it is operating for successive jobs with a random working cycle. The classical approach of “whichever occurs first” and the newly proposed approach of “whichever occurs last” are respectively employed for replacements scheduled at time T and at working cycle Y , whose policies are called replacement first and replacement last. Two cases when the number of units for this parallel system is a given constant value and a random variable with estimated distribution are considered into modelings. We obtain their expected replacement cost rates and optimal solutions analytically. Further, comparisons of replacement first and replacement last are described in detail to determine which policy could save more replacement cost rate.

Research on the task assignment problem of warehouse robots in the smart warehouse
 Author(s): Zhenping Li ; Wenyu Li ; Lulu Jiang
 + Show details  Hide details

p.
5 .
(1)
The task assignment problem of warehouse robots in the smart warehouse (TAWRSW) based on cargotoperson is investigated. Firstly, the sites of warehouse robots and the order picking tasks are given, and the task assignment problem for picking one order is formulated into a mathematical model to minimize the total operation cost. Then a heuristic algorithm is designed to solve the task assignment problem for picking multiple orders. Finally, simulations are done by using the orders data of online bookstore A. The feasibility and validity of the model and algorithm are verified. The model and algorithm in this paper provide a theoretical basis to solve the TAWRSW.

An inventory routing problem with soft time windows
 Author(s): Zhenping Li ; Chongyu Jiang ; Lulu Jiang
 + Show details  Hide details

p.
5 .
(1)
Inventory routing problem (IRP) which is a problem integrated with inventory control and vehicle routing is a typical NPhard problem, and also is the key of inventory and distribution coordinated optimization in the vendor managed inventory (VMI). An IRP of petrol secondary delivery system on the background of petroleum and petrochemical enterprise is investigated. Given a set of homogeneous vehicles with capacity constraint, which can be used for fuel distribution from one depot to a set of petrol stations that have deterministic fuel consumption, to minimize the total cost of the system, a mixed integer linear programming model of the inventory routing problem with soft time window (IRPSTW) is established. The model is solved by Lingo software. Simulations are done on an example. Based on solutions with different weight coefficients, we analyse the impact on the total cost by vehicle assignment cost and travel cost. The results of this paper provide a theoretical basis to solve the petrol secondary distribution problem of multiple terminal stations.

Analysis of a Markovian queue with two heterogenous servers and a threshold assignment policy
 Author(s): Dequan Yue ; Hui Li ; Guoxi Zhao ; Wuyi Yue
 + Show details  Hide details

p.
5 .
(1)
This paper considers a parallel queuing system with two heterogeneous servers where the task is dispatched to the two servers. The threshold assignment policy dispatches the tasks according to the number of customers in server 1. Firstly, we obtain the stationary condition of the system. Secondly, we give the stationary performance indices by using a matrixgeometric solution theory. Finally, we develop the average cost function and analyze the effect of the parameters on the average cost function by using numerical examples.

Melanocytic globules detection in skin lesion images
 Author(s): L.A. Nowak ; K. GrzesiakKopeć ; M.J. Ogorzałek
 + Show details  Hide details

p.
5 .
(1)
In this paper a method is presented for detection of melanin globules often present in melanocytic skin lesions images. The detection is done by performing image analysis similar to the one used in clinical evaluation. The method uses multistage image filtering to extract objects present in the dermoscopic image that match globule structure pattern. Classification of the found objects is made based on shape and size of globule structure. The classification is problematic task due to color and scale differences between dermatologic images and is related to differences between image acquisition equipment used in dermatoscopy. First we describe characteristic of globule structure needed for correct classification, along with method for calculating those characteristic. Next we presented a method for globules detection that is a part of computeraided diagnostic process of melanocytic skin lesions. Evaluation of such lesions is a basis for early detection of malignant lesions.

Generalized shogi and chess are constanttime testable
 Author(s): H. Ito ; A. Nagao ; Teagun Park
 + Show details  Hide details

p.
6 .
(1)
We present constanttime testing algorithms for the generalized shogi (Japanese chess) and chess. These problems are known to be EXPTIMEcomplete. A testing algorithm (or a tester) for a property accepts an input if it has the property and rejects it if it's far from having the property in high probability (e.g., at least 2/3) by reading only a constant part of the input. A property is said to be testable if there is a tester. The generalized shogi (and chess) problem is, given any position on √n x √n board with O(n) pieces, for testing the property “the player who moves first has a winning strategy.” We present that this property is testable for both shogi and chess. The shogi tester is onesidederror and the chess tester is surprisingly noerror! In the last decade, many problems have been found to be testable. However, almost all of such problems are in class NP. This is the first result on constanttime testability of EXPTIMEcomplete problems.

A signaling pathway analysis method based on information divergence
 Author(s): Hang Wei and HaoRan Zheng
 + Show details  Hide details

p.
6 .
(1)
Abnormal regulation of signaling pathways is the key factor causing disease. For better understanding disease mechanisms, many methods have been proposed to identify the significantly differential pathways between diseases and normal individuals via microarray gene expression datasets. Unlike previous common analysis processes, which is focused on merging gene difference into difference of pathway indirectly. In this paper, the idea of information divergence is introduced and a novel signaling pathway analysis method from a holistic view is presented to improve the detection results. We identify significantly differential pathways directly via computing the KL divergence between real and simulated probability distributions of genegene regulatory ability. We test our method on four human microarray expression datasets. The results illustrate that the capability of our approach in detecting significantly differential pathways between two sample groups is superior to other three classical pathway analysis methods.

An improved algorithm for the machine scheduling problem with job delivery coordination
 Author(s): Yuzhong Zhang ; Qiongyi Zheng ; Jianfeng Ren ; Long Zhang
 + Show details  Hide details

p.
6 .
(1)
A twostage supply chain scheduling problem is considered, where the first stage is job production and the second stage is job delivery. The focus is on the study of the integration of production scheduling with delivery of finished products to customers. In our considered model each job can be processed on either of two identical machines, and then delivered by a vehicle to a customer location. We present an improved algorithm with the worstcase performance ratio 14/9 + ɛ, which improves the known upper bounds of 2 and 5/3 in [Chang, Y.C. and Lee, C.Y., E. J. O. R., 158 (2004), pp. 470487; Zhong, W., Dosa, G. and Tan, Z.Y., E. J. O. R., 182(2007), pp. 10571072].

Employing postDEA method in budget management of health care sectors
 Author(s): XiaoYa Li
 + Show details  Hide details

p.
6 .
(1)
An increasing attention has been paid to efficiency analysis in the health care area. Among the existing efficiency assessment techniques, data envelopment analysis (DEA) plays an important role in a wide range of applications as for measuring the relative efficiency of different health care sectors. This paper focuses on a second stage of the analysis, which is operated after efficiency evaluation and called as postDEA stage, and mainly cope with the budget management problems such as budget allocation and budget prediction. In the postDEA stage, a comprehensive DEA based techniques are adopted to make the budget prediction and allocation based on the outcome of the first stage. A framework of budget management from macro aspect is built, together with corresponding resource allocation and prediction models proposed from micro aspect. The effect of the postDEA method is illustrated by a numerical example with considering 10 hospitals, and with considering elasticity in postDEA method, the outcome leads to an efficiency incentive effect in budget management.

Sufficient optimal conditions for unconstrained quadratic binary problems
 Author(s): Liu Liu ; Chunli Liu ; Qiuling Xie
 + Show details  Hide details

p.
6 .
(1)
In this article, we present several sufficient optimal conditions for unconstrained quadratic binary problems, which can be applied in algorithms combining with SDP relaxations in branchandbound approaches for the primal problem. These optimal conditions can work for many situations when the Lagrangian duality gap is not zero.

A method for computing a sequence of circumscribing polygons and its analysis
 Author(s): K. Onishi
 + Show details  Hide details

p.
7 .
(1)
In this paper, we propose two methods for computing a sequence of circumscribing polygons for a simple polygon. These methods are based on the greedy method, and are called the naive method and pocket method. The computational complexity of the two methods is O(n^{2}) time and O(n) space for a simple polygon with n vertexes. We applied two methods to sets of simple polygons. We measured the number of intersection checks of two line segments and the execution time of each methods.

A stackelberg game theoretic approach to competitive product portfolio management
 Author(s): Xiaojie Liu ; Gang Du ; Yi Xia
 + Show details  Hide details

p.
7 .
(1)
We are concerned with a product portfolio management problem in which a firm wants to enter a competitive market by offering new products where there are existing products belonging to a competitor. The objective of the new entrant firm is to find out an optimal product portfolio that maximizes its expected shared surplus. The market incumbent firm can react by adjusting its existing product portfolio through offering new products or closing old ones with the aim of maximizing its own expected shared surplus. We formulate a bilevel zeroone integer nonlinear programming model based on the Stackelberg leaderfollower game where the new entrant firm is the leader and the incumbent firm is the follower. In the absence of a closedform solution, the new model is illustrated through a numerical case under different market scenarios and calculated results are compared with Nash equilibrium.

The multiple knapsack problem with compatible bipartite graphs
 Author(s): Jianping Li ; Weidong Li ; Hao Wang
 + Show details  Hide details

p.
7 .
(1)
The multiple knapsack problem is to pack some items into given knapsacks, such that the sum of the knapsack profits is maximized. This paper is concerned with a variant of the multiple knapsack problem, called the multiple knapsack problem with compatible bipartite graph (MKPCBG), where two items can be packed into the same knapsack only if their corresponding vertices are adjacent in the given compatible bipartite graph. Under two different objectives, we prove that the MKPCBG problem is strongly NPhard, design some 1/2approximation algorithms, and design two optimal algorithms for the special case where all knapsacks have the same capacity.

Projection method for support vector machines with indefinite kernels
 Author(s): Hao Jiang ; WaiKi Ching ; Yushan Qiu ; Xiaoqing Cheng
 + Show details  Hide details

p.
7 .
(1)
In this paper, we tackle with indefinite kernels by introducing projection matrix to formulate a positive semidefinite kernel. The projection matrix has a nice property of sharing the same set of eigenvectors with the original kernel. The proposed model can be regarded as a generalized version of spectrum method (denoising method and flipping method) by varying parameter λ. The problem of selecting optimal λ for optimizing the prediction performance is also considered. Using the Bregman matrix divergence theory, one can realize kernel learning by using unconstrained optimization. And our suggested λ in projection matrix helps to exhibit optimal performance for different values of λ.

On classification of biological data using outlier detection
 Author(s): Yushan Qiu ; Xiaoqing Cheng ; Wenpin Hou ; WaiKi Ching
 + Show details  Hide details

p.
7 .
(1)
With the rapid development of information technology, the number of datasets, as well as their complexity and dimension, have been growing dramatically. This dramatic growth of biology data and nonbiological commercial databases becomes a challenging issue in data mining. Classification technique is one of the major tools in the captured research area. However, the performance of classification may be degraded when there exists noise in the captured databases. Therefore, outlier detection becomes an urgent need and the issue of how to integrate outlier detection method and classification techniques is an important and challenging issue. In this paper, we proposed a novel and effective approach based on kmeans clustering to identify outliers in the databases. In particular, we employed one of famous classification techniques, Support Vector Machine (SVM), owing to its ability to handle highdimensional data set. We also compare the classification results with the multivariate outlier detection method. Numerical results on two different data sets indicate that the classification results after removing the outliers by our proposed method are much better than the multivariate outlier detection method.