Asia-Pacific Journal of Operational Research

This paper unified Wolfe and Mond–Weir-type higher-order symmetric dual multiobjective programs over arbitrary cones. The usual duality theorems are proved for unified dual programs under the assumptions of higher-order $K$-$\eta$-convexity. Several known results are obtained as special cases. An example is given to show how higher-order Wolfe and Mond–Weir-type symmetric duals can be extracted from our model. An example is presented to show the existence of higher-order $K$-$\eta$-convex functions.

In this paper, we study the problem of estimating the principal eigenspace over an online data stream. First-order optimization methods are appealing choices for this problem thanks to their high efficiency and easy implementation. The existing first-order solvers, however, require either per-step orthonormalization or matrix inversion, which empirically puts pressure to the parameter tuning, and also incurs extra costs of rank augmentation. To get around these limitations, we introduce a penalty-like term controlling the distance from the Stiefel manifold into matrix Krasulina’s method, and propose the first orthonormalization- and inversion-free incremental PCA scheme (Domino). The Domino is shown to achieve the computational speed-up, and own the ability of automatic correction on the numerical rank. It also maintains the advantage of Krasulina’s method, e.g., variance reduction on low-rank data. Moreover, both of the asymptotic and non-asymptotic convergence guarantees are established for the proposed algorithm.

We address in this paper a variant of the scheduling-location (ScheLoc) problem on tree networks with interval edge lengths where the total deviation of the uncertain data cannot exceed a threshold. We further use the minmax regret concept to deal with the corresponding uncertainty. In order to solve the problem, we investigate the structure of the schedule which leads to the maximum regret value at a fixed point. Then we consider the machine location belonging to a specific edge of the tree and partition the underlying edge into regions with linear maximum regret function. Finally, we develop a combinatorial algorithm that solves the minmax regret ScheLoc problem in polynomial time based on a finite dominating set approach.

The phenomenon of deterioration effects can reduce production efficiency caused by extended start time or other factors. Based on it, this paper considers the scheduling situations of the common due date assignment in a no-idle flow shop scheduling environment. Under the given four dominating relationships (i.e., increasing, decreasing, increasing-decreasing and decreasing-increasing dominating machines, correspondingly expressed as idm, ddm, idm–ddm and ddm–idm) between machines, the objective functions are, respectively, to minimize (1) the weighted sum of common due date and total earliness; and (2) the weighted sum of common due date, total earliness and total penalty factors of tardy jobs. It is verified that these problems can be solved in polynomial time under four dominating relationships.

Conventional Data Envelopment Analysis (DEA) models assume real-valued input-output data and ignore the collaboration among decision-making units (DMUs) in the analysis of efficiency. This paper proposes a novel DEA production technology that is capable of dealing with the collaboration concept and resource sharing for both integer and real-valued data in the efficiency measurement and target setting. This is accomplished by way of a mixed integer linear programming (MILP) efficiency analysis model. We also deal with the computational aspect of the proposed model and invent a MILP with the computational complexity of $O(n+m-p)$ rather than $O(2^n+m-p)$. We explain the proposed models by numerical examples and graphical illustrations. We apply our models for efficiency analysis of 15 governmental (public) hospitals in Mashhad City in Iran and demonstrate the practical relevance and advanced future of the proposed methods.

In this paper, we study the Minimum Cost Submodular Cover ($\mathcal{ℳ}\mathcal{𝒞}\mathcal{𝒮}\mathcal{𝒞}$) problem over the ground set of size $n$, which aims at finding a subset with the minimal cost required so that the utility submodular function exceeds a given threshold. The problem has recently attracted a lot of attention due to its applications in various domains of operations research and artificial intelligence. However, the existing algorithms for this problem may not be easy to parallelize because of their costly adaptive complexity. However, the existing algorithms for this problem may not be effectively parallelized because of their costly adaptive complexity. This paper proposes an efficient parallel algorithm that returns a $(1-\lambda ,(1+𝜖)(1+log\frac{1}{\lambda }))$-bicriteria approximation solution within $O(logn)$ adaptive complexity, where $\lambda ,𝜖$ are fixed parameters. Our algorithm requires $O(n^2{log}^{2}n)$ query complexity, however, it can reduce to $O(n{log}^{3}n)$ instead while retaining a low adaptive complexity of $O({log}^{2}n)$. Therefore, our algorithm not only achieves the same approximation guarantees as the state of the art but also significantly improves the best-known low adaptive complexity algorithm for the above problem.

In this paper, we first introduce the higher-order lower and upper radial Hadamard directional derivatives for set-valued maps, which can capture the global information of concerning maps, and discuss the relationships with other existed higher-order derivatives. Second, based on the introduced derivatives, we establish optimality conditions for Henig efficient solutions of a set-valued equilibrium problem with constraints. Particularly, the optimality conditions hold in the case where the derivatives of objective and constraint functions are separated. Finally, we give some duality theorems for a mixed type of primal-dual set-valued equilibrium problem. The main results of this paper are illustrated by several concrete examples.

The placement stage of the physical design of very large-scale integrated circuits (VLSI) specifies the arrangement and order of standard cells and devices within an area, and the effectiveness of the placement result directly affects the chip’s performance. The advancement of process standards and reduction in the size of features size have dramatically increased the complexity of placement design. The realization of placement algorithms to deal with millions of cells has thus become an important issue in the automation of integrated circuit electronic design. In this paper, we first segment the digital integrated circuits into VLSI design styles and review them from the perspectives of practical placement problems, placement design ideas, and placement optimization methods. The discussion around traditional circuits focuses on the essence of the placement problem, placement steps, and classification of placement algorithms. In modern circuit placement, the discussion focuses on the impact of technical constraints on design. After identifying the essence of the placement problem, solutions to the packing problem are reviewed, and we then summarize our representative placement algorithms. Finally, based on the development of VLSI placement design, the optimization bottlenecks of existing placement design are summarized, and suggestions for future research are made based on the latest research topics and methodologies.