Table of Content

30 March 2020, Volume 8 Issue 1

Previous Issue    Next Issue

A Survey of Hidden Convex Optimization

Yong Xia

2020, 8(1):  1-28.  doi:10.1007/s40305-019-00286-5

Asbtract ( 551 )   PDF  

References | Related Articles | Metrics

Motivated by the fact that not all nonconvex optimization problems are difficult to solve, we survey in this paper three widely used ways to reveal the hidden convex structure for different classes of nonconvex optimization problems. Finally, ten open problems are raised.

An Introduction to the Computational Complexity of Matrix Multiplication

Yan Li, Sheng-Long Hu, Jie Wang, Zheng-Hai Huang

2020, 8(1):  29-43.  doi:10.1007/s40305-019-00280-x

Asbtract ( 485 )   PDF  

References | Related Articles | Metrics

This article introduces the approach on studying the computational complexity of matrix multiplication by ranks of the matrix multiplication tensors. Basic results and recent developments in this area are reviewed.

The Aviation Technology Two-Sided Matching with the Expected Time Based on the Probabilistic Linguistic Preference Relations

Bo Li, Yi-Xin Zhang, Ze-Shui Xu

2020, 8(1):  45-77.  doi:10.1007/s40305-019-00274-9

Asbtract ( 401 )   PDF  

References | Related Articles | Metrics

The two-sided matching has been widely applied to the decision-making problems in the field of management. With the limited working experience, the two-sided agents usually cannot provide the preference order directly for the opposite agent, but rather to provide the preference relations in the form of linguistic information. The preference relations based on probabilistic linguistic term sets (PLTSs) not only allow agents to provide the evaluation with multiple linguistic terms, but also present the different preference degrees for linguistic terms. Considering the diversities of the agents, they may provide their preference relations in the form of the probabilistic linguistic preference relation (PLPR) or the probabilistic linguistic multiplicative preference relation (PLMPR). For two-sided matching with the expected time, we first provide the concept of the time satisfaction degree (TSD). Then, we transform the preference relations in different forms into the unified preference relations (u-PRs). The consistency index to measure the consistency of u-PRs is introduced. Besides, the acceptable consistent u-PRs are constructed, and an algorithm is proposed to modify the unacceptable consistent u-PRs. Furthermore, we present the whole two-sided matching decisionmaking process with the acceptable consistent u-PRs. Finally, a case about aviation technology suppliers and demanders matching is presented to exhibit the rationality and practicality of the proposed method. Some analyses and discussions are provided to further demonstrate the feasibility and effectiveness of the proposed method.

Trade Credit Policy Between Supplier-Manufacturer-Retailer for Ameliorating/Deteriorating Items

Vandana Rai

2020, 8(1):  79-103.  doi:10.1007/s40305-018-0203-9

Asbtract ( 445 )   PDF  

References | Related Articles | Metrics

This paper is related to the advancement of the inventory models for ameliorating items and focused on the real-life business situation as with the time the deterioration rate of ameliorating items is increased. In the global world, every supply chain entities as suppliers/manufacturers/retailers want to increase the consumption of their goods without any losses. For this, he/she tries to lure manufacturer/retailers by offering some discounts, i.e. credit period for settling the account. The problem states that the manufacturer purchases the ameliorating items from the supplier, where the supplier offers his/her credit period to settle the account. The manufacturer purchases ameliorating items(like pigs,fishes,ducklings, etc.)and take those items as raw material; when the livestock matures the manufacturer sells it to the retailer and offer credit time for settling the account. Reason to propose the model is when the quantities of livestock become larger, then the manufacturer faces difficulty in maintaining all the livestock. In such a situation, the traditional method (without offering credit period) fails to provide the maximum profit to the manufacturer. Therefore, in order to get maximum profit, the manufacturer needs some more realistic scientific outlook for making decisions. The proposed model provides a more realistic assumption of business markets, by offering credit policy. In the introduced model, manufacturer faces amelioration and deterioration rate simultaneously due to the growth and the death of livestock. The amelioration and deterioration rates are assumed as the Weibull distribution type. Shortages allowed only for the retailer, which is partially backlogged. The main goal of this paper is to minimize the total relevant inventory cost for both the manufacturer and the retailers, by finding the optimal replenishment policy. The mathematical formulation with optimal solutions for manufacturer and retailers are given. Convexity and existence of the proposed model via numerical examples and graphical representations are explained. Finally, the conclusions with some future research direction are discussed.

Connectivity of Minimum Non-5-injectively Colorable Planar Cubic Graphs

Jing Jin, Bao-Gang Xu

2020, 8(1):  105-116.  doi:10.1007/s40305-018-0214-6

Asbtract ( 383 )   PDF  

References | Related Articles | Metrics

Suppose that G is a planar cubic graph with χ_i(G)> 5. We show that if χ_i(H) <χ_i(G) for each planar cubic graph H of order less than G, then G is either a 3-connected simple planar cubic graph, or a planar graph obtained from a simple cubic 3-connected planar graph by adding some earrings. This shows that a minimum non-5-injectively colorable simple planar cubic graph must be 3-connected.

Latent Local Feature Extraction for Low-Resolution Virus Image Classification

Zhi-Jie Wen, Zhi-Hu Liu, Yi-Chen Zong, Bao-Jun Li

2020, 8(1):  117-132.  doi:10.1007/s40305-018-0212-8

Asbtract ( 383 )   PDF  

References | Related Articles | Metrics

Virus image classification is a significant and challenging issue in both clinical virology and medical image processing. Due to the low-resolution virus images in the original dataset, there is tricky difficulty in extracting useful features from this kind of poor quality images adopting the traditional feature extraction methods. In this paper, we propose an effective and robust method, which eliminates the drawbacks of traditional local feature extraction methods and conducts latent local texture feature extraction thus to promote the accuracy of virus image classification. Firstly, the multi-scale principal component analysis (PCA) filters are learned from all original images. Then, it establishes a scale space for each PCA-filtered image by 2D Gaussian function. Finally, some typical feature descriptors are employed to extract texture features from all images, which include the original image and its filtered images by PCA and Gaussian filters. Aiming at the classification of low-resolution images, the proposed method solves the difficulty in extracting the essential feature from the original image and captures its latent and principal texture information from different perspectives in different filtered images. Experimental results show that the classification accuracy of the proposed method is much higher than state-of-the-art methods in the same low-resolution virus dataset, reaching 88.00%.

Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery

Ru-Bing Chen, Ling-Fa Lu, Jin-Jiang Yuan, Li-Qi Zhang

2020, 8(1):  133-143.  doi:10.1007/s40305-018-0210-x

Asbtract ( 447 )   PDF  

References | Related Articles | Metrics

This paper considers the integrated production and delivery scheduling on a serial batch machine, in which split is allowed in the delivery of the jobs. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. Lu et al. (Theor Comput Sci 572:50-57, 2015) showed that this problem is strongly NP-hard, and presented a 3/2-approximation algorithm. In this paper, we present an improved 4/3-approximation algorithm for this problem. We also present a polynomial-time algorithm for the special case when all jobs have the identical weight.

A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization

Mohammad Pirhaji, Maryam Zangiabadi, Hossien Mansouri, Ali Nakhaei, Ali Shojaeifard

2020, 8(1):  145-164.  doi:10.1007/s40305-018-0219-1

Asbtract ( 357 )   PDF  

References | Related Articles | Metrics

In this paper, we propose an interior-point algorithm based on a wide neighborhood for convex quadratic semidefinite optimization problems. Using the Nesterov-Todd direction as the search direction, we prove the convergence analysis and obtain the polynomial complexity bound of the proposed algorithm. Although the algorithm belongs to the class of large-step interior-point algorithms, its complexity coincides with the best iteration bound for short-step interior-point algorithms. The algorithm is also implemented to demonstrate that it is efficient.

On Scheduling a Deteriorating Rate-Modifying Activity to Minimize the Number of Tardy Jobs

Wen-Chang Luo

2020, 8(1):  165-175.  doi:10.1007/s40305-018-0207-5

Asbtract ( 361 )   PDF  

References | Related Articles | Metrics

We investigate a single-machine scheduling problem, where a deteriorating rate-modifying activity can be performed on the machine to reduce the processing times of jobs.The objective is to minimize the number of tardy jobs.Under the assumption that the duration of the rate-modifying activity is a nonnegative and nondecreasing functionon its starting time,we propose an optimal polynomial time algorithm running in O(n³) time.

An Objective Penalty Method for Optimistic Bilevel Programming Problems

June Liu, Tao Zhang, Yu-Xin Fan, Bing Han, Yue Zheng

2020, 8(1):  177-187.  doi:10.1007/s40305-018-0205-7

Asbtract ( 449 )   PDF  

References | Related Articles | Metrics

In this paper, we consider an optimistic nonlinear bilevel programming problem. Under some conditions, we first show that the sequence of solutions to penalty problems converges to the optimal solution of the original bilevel programming problem.We then present an objective penalty method to solve such a problem.Finally, some numerical experiments are performed to illustrate its feasibility.

Two-Agent Scheduling on a Bounded Parallel-Batching Machine with Makespan and Maximum Lateness Objectives

Qi Feng, Wei-Ping Shang, Cheng-Wen Jiao, Wen-Jie Li

2020, 8(1):  189-196.  doi:10.1007/s40305-019-00258-9

Asbtract ( 381 )   PDF  

References | Related Articles | Metrics

This paper studies the two-agent scheduling on a bounded parallel-batching machine. In the problem, there are two agents A and B each having their own job sets with the restriction that the processing times of jobs of agent B are equal. The jobs of different agents can be processed in a common batch. Moreover, each agent has its own objective function to be minimized. The objective function of agent A is the makespan of its jobs, and the objective function of agent B is the maximum lateness of its jobs. We present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.