Asia-Pacific Journal of Operational Research

In this paper, we consider a class of optimal control problems involving continuous control and state inequality constraints where the control is almost smooth. We first employ the control parametrization technique via approximating the control signal by a piecewise linear function. Then, we develop a time scaling transformation procedure for transforming the approximate problem into an equivalent problem that can be solved readily using conventional methods. On this basis, a novel exact penalty function method is constructed by appending penalized constraint violations to the cost function. The gradient formulas and convergent properties ensure that the transformed unconstrained optimal parameter selection problems can be solved by existing optimization algorithms or software packages. Finally, an example is solved showing the effectiveness and applicability of the approach proposed.

Cloud/ fog computing resource pricing is a new paradigm in the blockchain mining scheme, as the participants would like to purchase the cloud/ fog computing resource to speed up their mining processes. In this paper, we propose a novel two-stage game to study the optimal price-based cloud/ fog computing resource management, in which the cloud/fog computing resource provider (CFP) is the leader, setting the resource price in Stage I, and the mining pools act as the followers to decide their demands of the resource in Stage II. Since mining pools are bounded rational in practice, we model the dynamic interactions among them by an evolutionary game in Stage II, in which each pool pursues its evolutionary stable demand based on the observed price, through continuous learning and adjustments. Backward induction method is applied to analyze the sub-game equilibrium in each stage. Specifically in Stage II, we first build a general study framework for the evolutionary game model, and then provide a detailed theoretical analysis for a two-pool case to characterize the conditions for the existence of different evolutionary stable solutions. Referring to the real world, we conduct a series of numerical experiments, whose results validate our theoretical findings for the case of two mining pools. Additionally, the impacts from the size of mining block, the unit transaction fee and the price of token on the decision makings of participants are also discussed.

In this paper, we consider nonseparable convex minimization models with quadratic coupling terms arised in many practical applications. We use a majorized indefinite proximal alternating direction method of multipliers (iPADMM) to solve this model. The indefiniteness of proximal matrices allows the function we actually solved to be no longer the majorization of the original function in each subproblem. While the convergence still can be guaranteed and larger stepsize is permitted which can speed up convergence. For this model, we analyze the global convergence of majorized iPADMM with two different techniques and the sublinear convergence rate in the nonergodic sense. Numerical experiments illustrate the advantages of the indefinite proximal matrices over the positive definite or the semi-definite proximal matrices.

Credit payment strategies have been implemented widely in the online retail industry. This work studies an online-retail supply chain involving credit period and selling price-dependent demands. The participants of the supply chain form a Stackelberg game where the supplier as a follower sells products to the customers through an online platform provider, who as a leader provides a credit period to customers and charges the supplier based on the quantity of goods sold. We study and compare the supply chains when the online platform provider adopts the cash payment and credit payment strategies, respectively, to investigate the effects of the credit period, the selling price and the default risk on supply chain system performance. We also investigate these supply chains under both the centralized and decentralized settings and provide an example to illustrate a simple allocation mechanism to coordinate the decentralized supply chain. Finally, an extension of the supply chain with credit payment is given.

In this paper, we consider the problem of finding a sparse solution, with a minimal number of nonzero components, for a set of linear inequalities. This optimization problem is combinatorial and arises in various fields such as machine learning and compressed sensing. We present three new heuristics for the problem. The first two are greedy algorithms minimizing the sum of infeasibilities in the primal and dual spaces with different selection rules. The third heuristic is a combination of the greedy heuristic in the dual space and a local search algorithm. In numerical experiments, our proposed heuristics are compared with the weighted-$l_1$ algorithm and DCA programming with three different non-convex approximations of the zero norm. The computational results demonstrate the efficiency of our methods.

The number of social individuals who interact with their friends through social networks is increasing, leading to an undeniable fact that word-of-mouth marketing has become one of the useful ways to promote sale of products. The Constrained Profit Maximization in Attribute network (CPMA) problem, as an extension of the classical influence maximization problem, is the main focus of this paper. We propose the profit maximization in attribute network problem under a cardinality constraint which is closer to the actual situation. The profit spread metric of CPMA calculates the total benefit and cost generated by all the active nodes. Different from the classical Influence Maximization problem, the influence strength should be recalculated according to the emotional tendency and classification label of nodes in attribute networks. The profit spread metric is no longer monotone and submodular in general. Given that the profit spread metric can be expressed as the difference between two submodular functions and admits a DS decomposition, a three-phase algorithm named as Marginal increment and Community-based Prune and Search(MCPS) Algorithm frame is proposed which is based on Louvain algorithm and logistic function. Due to the method of marginal increment, MPCS algorithm can compute profit spread more directly and accurately. Experiments demonstrate the effectiveness of MCPS algorithm.

In this paper, we concentrate on studying the $k$-means problem with a matroid or a knapsack constraint. In the matroid means problem, given an observation set and a matroid, the goal is to find a center set from the independent sets to minimize the cost. By using the linear programming $\mathrm{\text{(LP)}}$-rounding technology, we obtain a constant approximation guarantee. For the knapsack means problem, we adopt a similar strategy to that of matroid means problem, whereas the difference is that we add a knapsack covering inequality to the relaxed LP in order to decrease the unbounded integrality gap.

In this paper, we propose a so-called capacitated min–max correlation clustering model, a natural variant of the min–max correlation clustering problem. As our main contribution, we present an integer programming and its integrality gap analysis for the proposed model. Furthermore, we provide two approximation algorithms for the model, one of which is a bi-criteria approximation algorithm and the other is based on LP-rounding technique.

Clustering is one of the most important problems in the fields of data mining, machine learning, and biological population division, etc. Moreover, robust variant for $k$-means problem, which includes $k$-means with penalties and $k$-means with outliers, is also an active research branch. Most of these problems are NP-hard even the most classical problem, $k$-means problem. For the NP-hard problems, the heuristic algorithm is a powerful method. When the quality of the output can be guaranteed, the algorithm is called an approximation algorithm.

In this paper, combining two types of robust settings, we consider $k$-means problem with penalties and outliers ($k$-MPO). In the $k$-MPO, we are given an $n$-point set $U\subset {ℝ}^d$, a penalty cost $p_v\ge 0$ for each $v\in U$, an integer $k\le n$, and an integer $z\le n$. The target is to find a center subset $S\subseteq {ℝ}^d$ with $\left|S\right|\le k$, a penalty subset $P\subseteq U$ and an outlier subset $Z\subseteq U$ with $\left|Z\right|\le z$, such that the sum of the total costs, including the connection cost and the penalty cost, is minimized. We offer an approximation algorithm using a heuristic local search scheme. Based on a single-swap manipulation, we obtain $274$-approximation algorithm.

Multi-source Weber problem (MWP) is an important model in facility location, which has wide applications in various areas such as health service management, transportation system management, urban planning, etc. The location-allocation algorithm is a well-known method for solving MWP, which consists of a location phase and an allocation phase at each iteration. In this paper, we consider more general and practical case of MWP–the constrained multi-source location problem (CMSLP), i.e., the location of multiple facilities with considering interactive transportation between facilities, locational constraints on facilities and the gauge for measuring distances. A variational inequality approach is contributed to solving the location subproblem called the constrained multi-facility location problem (CMFLP) in location phase, which leads to an efficient projection-type method. Then a new location-allocation algorithm is developed for CMSLP. Global convergence of the projection-type method as well as local convergence of new location-allocation algorithm are proved. The efficiency of proposed methods is verified by some preliminary numerical results.

In this paper, we consider the parallel-machine scheduling with step-deteriorating jobs. The actual processing time of each job deteriorates as a step function if its starting time is beyond a given deteriorating date. We focus on the case of the common job deteriorating date. For the minimization problem of total completion time, we first show that the problem is NP-hard in the strong sense. Then we propose one property of any optimal schedule. Furthermore, we prove that two special cases of common normal processing time or common penalty are polynomially solvable. For the minimization problem of total weighted completion time, we analyze the NP-hardness and present a polynomial time optimal algorithm for the case of common normal processing time and common penalty.

We consider online parallel-batch scheduling of $f$ incompatible unit-length job families with variable lookahead interval to minimize the maximum completion time, where $f$ is the number of job families which is known in advance. Incompatible job family means that a batch only contains the jobs from the same job family. At any time $t$, an online algorithm can foresee the information of the jobs arriving in the time interval $(t,t+\mathrm{\Delta }(t)]$, where $\mathrm{\Delta }(t)=(\lambda -1)t+\beta$ is variable. When the batch capacity $b=\infty$ and $f\ge 1$, we provide a best possible online algorithm with competitive ratio $1+{\alpha }_f$ for $0\le \beta <1$ and $1\le \lambda \le 1+\beta$, where ${\alpha }_f$ is a positive root of $\lambda f{\alpha }_f^2+(\lambda f+\beta +1-f){\alpha }_f+\beta -f=0$. When the batch capacity $(f<)b<\infty$ and $f\ge 2$, we give an online algorithm with competitive ratio $1+max\{\frac{f}{f{\alpha }_f+f},\frac{f}{\lambda f{\alpha }_f+\beta +1}\}$ for $0\le \beta <1$ and $\lambda \ge 1$, and prove that it is the best possible for $\lambda =1$ and $0\le \beta \le \frac{f+1-\sqrt{f^2+1}}{2}$.

We consider parallel identical machines scheduling problems with deteriorating maintenance activities and the option of job rejection. Each machine has at most one deteriorating maintenance activity. The length of each maintenance activity increases linearly with its starting time. The location of the maintenance activity on each machine needs to be determined. The goal is to find the sequence of jobs to minimize scheduling cost; we further the model by allowing job rejection. A job is either accepted and processed on one of machines, or rejected. The goal is to determine the sequence of the accepted jobs to minimize scheduling cost of the accepted jobs plus total rejection penalty of the rejected jobs. When the scheduling cost is the makespan, we design a pseudo-polynomial time algorithm, a 2-approximation algorithm and a fully polynomial time approximation scheme. When the scheduling cost is the total completion time, we provide a polynomial time algorithm for the problem. When the scheduling costs are the total weighted completion time under the agreeable ratio assumption and the maximum lateness, we present pseudo-polynomial time algorithms to solve these problems, respectively.

In this paper, we consider the spherical $k$-means problem with penalties, a robust model of spherical clusterings that requires identifying outliers during clustering to improve the quality of the solution. Each outlier will incur a specified penalty cost. In this problem, one should detect the outliers and propose a $k$-clustering for the given data set so as to minimize the sum of the clustering and penalty costs. As our main contribution, we present a $(16+8\sqrt{3})$-approximation via single-swap local search and an $(8+2\sqrt{7}+𝜀)$-approximation via multi-swap local search.

Using second-order optimization methods for training deep neural networks (DNNs) has attracted many researchers. A recently proposed method, Eigenvalue-corrected Kronecker Factorization (EKFAC), proposed an interpretation by viewing natural gradient update as a diagonal method and corrects the inaccurate re-scaling factor in the KFAC eigenbasis. What’s more, a new method to approximate the natural gradient called Trace-restricted Kronecker-factored Approximate Curvature (TKFAC) is also proposed, in which the Fisher information matrix (FIM) is approximated as a constant multiplied by the Kronecker product of two matrices and the traces can be kept equal before and after the approximation. In this work, we combine the ideas of these two methods and propose Trace-restricted Eigenvalue-corrected Kronecker Factorization (TEKFAC). The proposed method not only corrects the inexact re-scaling factor under the Kronecker-factored eigenbasis, but also considers the new approximation method and the effective damping technique adopted by TKFAC. We also discuss the differences and relationships among the related Kronecker-factored approximations. Empirically, our method outperforms SGD with momentum, Adam, EKFAC and TKFAC on several DNNs.

In the study of social networks, there exist many uncertainties which were ignored in earlier research efforts. However, they are now getting more and more attentions. Therefore, more and more robust optimization and machine learning approaches are getting involved. In this small survey, we would like to accumulate those uncertainties and related research works in robust optimization and machine learning.