Table of Content

30 September 2023, Volume 11 Issue 3

Previous Issue    Next Issue

Variable Metric Method for Unconstrained Multiobjective Optimization Problems

Jian Chen, Gao-Xi Li, Xin-Min Yang

2023, 11(3):  409-438.  doi:10.1007/s40305-022-00447-z

Asbtract ( 108 )   PDF  

References | Related Articles | Metrics

In this paper, we propose a variable metric method for unconstrained multiobjective optimization problems (MOPs). First, a sequence of points is generated using different positive definite matrices in the generic framework. It is proved that accumulation points of the sequence are Pareto critical points. Then, without convexity assumption, strong convergence is established for the proposed method. Moreover, we use a common matrix to approximate the Hessian matrices of all objective functions, along which a new nonmonotone line search technique is proposed to achieve a local superlinear convergence rate. Finally, several numerical results demonstrate the effectiveness of the proposed method.

Gallai's Conjecture on Path Decompositions

Geng-Hua Fan, Jian-Feng Hou, Chui-Xiang Zhou

2023, 11(3):  439-449.  doi:10.1007/s40305-022-00435-3

Asbtract ( 54 )   PDF  

References | Related Articles | Metrics

Gallai's conjecture asserts that every connected graph on n vertices can be decomposed into at most $\frac{{n + 1}}{2}$ paths. The E-subgraph of a graph G, denoted by $ G_e $, is the subgraph induced by the vertices of even degree in G. A triangle pair is a graph consisting of two triangles with exactly one vertex in common. In this paper, it is proved that Gallai's conjecture is true for graphs G in which $ G_e $ contains no triangle pair and each block of $ G_e $ has maximum degree at most 3.

Extremal P₈-Free/P₉-Free Planar Graphs

Yong-Xin Lan, Yong-Tang Shi

2023, 11(3):  451-457.  doi:10.1007/s40305-021-00385-2

Asbtract ( 53 )   PDF  

References | Related Articles | Metrics

An H-free graph is a graph not containing the given graph H as a subgraph. It is well known that the Turán number $ \mathrm{{ex}}_{}(n,H) $ is the maximum number of edges in an H-free graph on n vertices. Based on this definition, we define $ \mathrm{{ex}}_{_\mathcal {P}}(n,H) $ to restrict the graph classes to planar graphs, that is, $ \mathrm{{ex}}_{_\mathcal {P}}(n,H)=\max \{|E(G)|: G\in {\mathcal {G}} $, where $ {\mathcal {G}} $ is a family of all H-free planar graphs on n vertices. Obviously, we have $ \mathrm{{ex}}_{_{\mathcal {P}}}(n,H)=3n-6 $ if the graph H is not a planar graph. The study is initiated by Dowden (J Graph Theory 83:213–230, 2016), who obtained some results when H is considered as $ C_4 $ or $ C_5 $. In this paper, we determine the values of $ \mathrm{{ex}}_{_{\mathcal {P}}}(n,P_k) $ with $ k\in \{8,9\} $, where $ P_k $ is a path with k vertices.

A Multi-server Queue in a Multi-phase Random Environment with Waiting Servers and Customers' Impatience Under Synchronous Working Vacation Policy

Meriem Houalef, Amina Angelika Bouchentouf, Lahcene Yahiaoui

2023, 11(3):  459-487.  doi:10.1007/s40305-021-00384-3

Asbtract ( 42 )   PDF  

References | Related Articles | Metrics

In this paper, we develop an M/M/c queueing system in a Markovian environment with waiting servers, balking and reneging, under both synchronous single and multiple working vacation policies. When the system is in operative phase j, $ j=\overline{1,K}, $ customers are served one by one. Once the system is empty, the servers have to wait a random period of time before leaving, causing the system to move to vacation phase 0 at which new arrivals can be served at lower rate. Using the method of the probability generating functions, we establish the steady-state analysis of the system. Special cases of the queueing model are presented. Then, explicit expressions of the useful system characteristics are derived. In addition, a cost model is constructed to define the optimal values of service rates, simultaneously, to minimize the total expected cost per unit time via a quadratic fit search method. Numerical examples are provided to display the impact of different system characteristics.

Approximations for a Queueing Game Model with Join-the-Shortest-Queue Strategy

Qi-Hui Bu, Li-Wei Liu, Jia-Shan Tang, Yi-Qiang Q. Zhao

2023, 11(3):  489-504.  doi:10.1007/s40305-021-00382-5

Asbtract ( 45 )   PDF  

References | Related Articles | Metrics

This paper investigates a partially observable queueing system with N nodes in which each node has a dedicated arrival stream. There is an extra arrival stream to balance the load of the system by routing its customers to the shortest queue. In addition, a reward-cost structure is considered to analyse customers' strategic behaviours. The equilibrium and socially optimal strategies are derived for the partially observable mean field limit model. Then, we show that the strategies obtained from the mean field model are good approximations to the model with finite N nodes. Finally, numerical experiments are provided to compare the equilibrium and socially optimal behaviours, including joining probabilities and social benefits for different system parameters.

Sufficiency and Duality for Nonsmooth Interval-Valued Optimization Problems via Generalized Invex-Infine Functions

Izhar Ahmad, Krishna Kummari, S. Al-Homidan

2023, 11(3):  505-527.  doi:10.1007/s40305-021-00381-6

Asbtract ( 46 )   PDF  

References | Related Articles | Metrics

In this paper, a new concept of generalized-affineness type of functions is introduced. This class of functions is more general than some of the corresponding ones discussed in Chuong (Nonlinear Anal Theory Methods Appl 75:5044–5052, 2018), Sach et al. (J Global Optim 27:51–81, 2003) and Nobakhtian (Comput Math Appl 51:1385–1394, 2006). These concepts are used to discuss the sufficient optimality conditions for the interval-valued programming problem in terms of the limiting/Mordukhovich subdifferential of locally Lipschitz functions. Furthermore, two types of dual problems, namely Mond–Weir type and mixed type duals are formulated for an interval-valued programming problem and usual duality theorems are derived. Our results improve and generalize the results appeared in Kummari and Ahmad (UPB Sci Bull Ser A 82(1):45–54, 2020).

Taguchi Analysis for Improving Optimization of Integrated Forward/Reverse Logistics

Elham Behmanesh, Jürgen Pannek

2023, 11(3):  529-552.  doi:10.1007/s40305-021-00380-7

Asbtract ( 34 )   PDF  

References | Related Articles | Metrics

The distribution–allocation problem is known as one of the most comprehensive strategic decisions. In real-world cases, it is impossible to solve a distribution–allocation problem completely in acceptable time. This forces the researchers to develop efficient heuristic techniques for the large-term operation of the whole supply chain. These techniques provide near optimal solution and are comparably fast particularly for large-scale test problems. This paper presents an integrated supply chain model which is flexible in the delivery path. As solution methodology, we apply a memetic algorithm with a novelty in population presentation. To identify the optimum operating condition of the proposed memetic algorithm, Taguchi method is adopted. In this study, four factors, namely population size, crossover rate, local search iteration and number of iteration, are considered. Determining the best level of the considered parameters is the outlook of this research.

Strategyproof Facility Location with Limited Locations

Zhong-Zheng Tang, Chen-Hao Wang, Meng-Qi Zhang, Ying-Chao Zhao

2023, 11(3):  553-567.  doi:10.1007/s40305-021-00378-1

Asbtract ( 36 )   PDF  

References | Related Articles | Metrics

We study the mechanism design of facility location problems. The problem is to design mechanisms to select a set of locations on which to build a set of facilities, aiming to optimize some system objective and achieve desirable properties based on the strategic agents' locations. The agents might have incentives to misreport their private locations, in order to minimize the costs (i.e., the distance from the closest facility). We study the setting with limited locations, that is, the facilities can only be built on a given finite set of candidate locations, rather than the whole space. For locating a single facility and two facilities on a real line, we propose strategyproof mechanisms with tight approximation ratios, under the objectives of minimizing the total cost and the maximum cost. Further, we consider the problem of locating an obnoxious facility from which the agents want to stay as far away as possible, and derive tight bounds on the approximation ratio of strategyproof mechanisms.

Two-Level Linear Relaxation Method for Generalized Linear Fractional Programming

Hong-Wei Jiao, You-Lin Shang

2023, 11(3):  569-594.  doi:10.1007/s40305-021-00375-4

Asbtract ( 32 )   PDF  

References | Related Articles | Metrics

This paper presents an efficient algorithm for globally solving a generalized linear fractional programming problem. For establishing this algorithm, we firstly construct a two-level linear relaxation method, and by utilizing the method, we can convert the initial generalized linear fractional programming problem and its subproblems into a series of linear programming relaxation problems. Based on the branch-and-bound framework and linear programming relaxation problems, a branch-and-bound algorithm is presented for globally solving the generalized linear fractional programming problem, and the computational complexity of the algorithm is given. Finally, numerical experimental results demonstrate the feasibility and efficiency of the proposed algorithm.

Regularized Methods for a Two-Stage Robust Production Planning Problem and its Sample Average Approximation

Jie Jiang, Zhi-Ping Chen

2023, 11(3):  595-625.  doi:10.1007/s40305-021-00373-6

Asbtract ( 28 )   PDF  

References | Related Articles | Metrics

In this paper, we consider a two-stage robust production planning model where the first stage problem determines the optimal production quantity upon considering the worst-case revenue generated by the uncertain future demand, and the second stage problem determines the possible demand of consumers by using a utility-based model given the production quantity and a realization of the random variable. We derive an equivalent single-stage reformulation of the two-stage problem. However, it fails the convergence analysis of the sample average approximation (SAA) approach for the reformulation directly. Thus we develop a regularized approximation of the second stage problem and derive its closed-form solution. We then present conditions under which the optimal value and the optimal solution set of the proposed SAA regularized approximation problem converge to those of the single-stage reformulation problem as the regularization parameter shrinks to zero and the sample size tends to infinity. Finally, some preliminary numerical examples are presented to illustrate our theoretical results.

The GI/M/1 Queue in a Multi-phase Service Environment with Working Vacations and Bernoulli Vacation Interruption

Jian-Jun Li, Li-Wei Liu

2023, 11(3):  627-656.  doi:10.1007/s40305-021-00371-8

Asbtract ( 34 )   PDF  

References | Related Articles | Metrics

In this paper, we consider a GI/M/1 queue operating in a multi-phase service environment with working vacations and Bernoulli vacation interruption. Whenever the queue becomes empty, the server begins a working vacation of random length, causing the system to move to vacation phase 0. During phase 0, the server takes service for the customers at a lower rate rather than stopping completely. When a vacation ends, if the queue is non-empty, the system switches from the phase 0 to some normal service phase i with probability $ q_i $, $ i = 1,2, \cdots ,N $. Moreover, we assume Bernoulli vacation interruption can happen. At a service completion instant, if there are customers in a working vacation period, vacation interruption happens with probability p, then the system switches from the phase 0 to some normal service phase i with probability $ q_i $, $ i = 1,2, \cdots ,N $, or the server continues the vacation with probability $ 1-p $. Using the matrix geometric solution method, we obtain the stationary distributions for queue length at both arrival epochs and arbitrary epochs. The waiting time of an arbitrary customer is also derived. Finally, several numerical examples are presented.

Remarks on Component Factors

Wei Gao, Wei-Fan Wang

2023, 11(3):  657-666.  doi:10.1007/s40305-021-00357-6

Asbtract ( 29 )   PDF  

References | Related Articles | Metrics

In this remark, we first simply survey the important results on component factors in graphs. Then, we focus on the binding number condition of component factors in some special settings. The main contributions in this remark are two folded: (1) we reveal that the existence of some special component factors is equal to some specific binding number conditions; (2) the parameter conditions for a graph G with a $ P_{\tiny {\geqslant 3}} $-factor are determined.

Degree Conditions on Copies of Forests in Graphs

Xiao-Dong Chen, Shuai-Jun Chen, Ming-Chu Li

2023, 11(3):  667-672.  doi:10.1007/s40305-022-00404-w

Asbtract ( 49 )   PDF  

References | Related Articles | Metrics

For a graph G, let $ \mu (G)=\min \{\max \{{d}(x),{d}(y)\}:x\ne y,xy\notin E(G), x,y\in V(G)\} $ if G is non-complete, otherwise, $ \mu (G)=+\infty. $ For a given positive number s, we call that a graph G satisfies Fan-type conditions if $ \mu (G)\geqslant s. $ Suppose $ \mu (G)\geqslant s, $ then a vertex v is called a small vertex if the degree of v in G is less than s. In this paper, we prove that for a forest F with m edges, if G is a graph of order $ n\geqslant |F| $ and $ \mu (G)\geqslant m $ with at most $ \max \{n-2m,0\} $ small vertices, then G contains a copy of F. We also give examples to illustrate both the bounds in our result are best possible.

Approximate Weak Minimal Solutions of Set-Valued Optimization Problems

S. Khoshkhabar-amiranloo

2023, 11(3):  673-692.  doi:10.1007/s40305-022-00401-z

Asbtract ( 49 )   PDF  

References | Related Articles | Metrics

This paper deals with approximate weak minimal solutions of set-valued optimization problems under vector and set optimality criteria. The relationships between various concepts of approximate weak minimal solutions are investigated. Some topological properties and existence theorems of these solutions are given. It is shown that for set-valued optimization problems with upper (outer) cone-semicontinuous objective values or closed objective maps the approximate weak minimal and strictly approximate lower weak minimal solution sets are closed. By using the polar cone and two scalarization processes, some necessary and sufficient optimality conditions in the sense of vector and set criteria are provided.

Single-Machine Preemptive Scheduling with Release Dates Involving the Total Weighted Late Work Criterion

Zhi-Chao Geng, Yuan Zhang

2023, 11(3):  693-706.  doi:10.1007/s40305-022-00403-x

Asbtract ( 43 )   PDF  

References | Related Articles | Metrics

This paper investigates the preemptive scheduling with release dates on a single machine to minimize the total weighted late work. We firstly present an $ O(n\log n) $-time algorithm for the single-agent problem with disagreeable weights and due dates. And then, we extendedly study the two-agent Pareto-scheduling problem with jobs having a common due date to minimize each agent's total weighted late work, and give a polynomial-time algorithm that is based on the parameters analysis to generate the Pareto frontier.