Asia-Pacific Journal of Operational Research

A co-evolutionary algorithm based on particle swarm optimization (PSO) and ant colony optimization (ACO) is given to solve the bound constrained mixed-integer programming problem (BCMIP). For the specificity of the problem, the hybrid coding includes the real coding and the integer coding. The real coding part is evolved by PSO while the integer coding part is evolved by ACO. The entire population is co-evolved by PSO and ACO. Numerical experiments show that the proposed algorithm is feasible and effective to solve BCMIP. We also obtain satisfactory result to solve MIP when the proposed algorithm is combined with penalty function method.

In this paper, we propose a smoothing penalized sample average approximation (SAA) method for solving a stochastic minimization problem with second-order dominance constraints. The basic idea is to use sample average to approximate the expected values of the underlying random functions and then reformulate the discretized problem as an ordinary nonlinear programming problem with finite number of constraints. An exact penalty function method is proposed to deal with the latter and an elementary smoothing technique is used to tackle the nonsmoothness of the plus function and the exact penalty function. We investigate the convergence of the optimal value obtained from solving the smoothed penalized sample average approximation problem as sample size increases and show that with probability approaching to one at exponential rate with the increase of sample size the optimal value converges to its true counterpart. Some preliminary numerical results are reported.

In this paper, we introduce a geometric model for linear symmetric eigenvalue problem, which is motivated by the fact that any eigenvalue of a symmetric positive definite matrix A is the reciprocal of the square length of an axis of the ellipsoid x^TAx = 1. Hence, to find the largest eigenvalue is equivalent to calculate the shortest axis of the corresponding ellipsoid. Two sequential subspace projection algorithms based on this idea are proposed, and we establish the global convergence and local linear convergence rate of our proposed algorithms. Numerical experiments demonstrate that our algorithm outperforms the MATLAB built-in solver "EIGS" which calls the famous package "ARPACK".

This note deals with the optimality conditions of set-valued unconstraint optimization problem in real normed linear spaces. Based upon the concept of contingent epiderivative, the unified necessary and sufficient optimality conditions for global proper efficiency in vector optimization problem involving cone-arcwise connected set-valued mapping are presented.

In this paper, an adaptive gradient algorithm (AGM) for box constrained optimization is developed. The algorithm is based on an active set identification technique and consists of a nonmonotone gradient projection step, a conjugate gradient step and a rule for branching between the two steps. We show that the method is globally convergent under appropriate conditions. Numerical experiments are presented using bound constrained problems in the CUTEr test problem library.

This paper considers the general Spatial Price Equilibrium (SPE) problem under constraints of supply-guarantee at demand markets and, in the meantime, protecting the scarce resources at supply markets. We first formulate the equilibrium problem as a variational inequality (VI) problem with partially unknown mapping. Then, we propose a progressive equilibration algorithm for solving the problem under consideration. The global convergence of the proposed method is proved under suitable assumptions. Some preliminary numerical results demonstrate the reliability of the proposed algorithm.

In this paper, we use matrix multisplitting with weighting parameters as the preconditioner of A. The optimal weighting parameters are determined by the approaching theory, and the scale of approaching is defined by F-norm, 2-norm, and ∞-norm, respectively. Base on these three minimize models, three algorithms are presented and the convergence theories are established. Finally, numerical examples show that the preconditioner with the optimal weighting parameters, which are obtained from minimize F-norm and 2-norm models, can improve the condition number of A effectively. Besides, general weighting parameters are more effective than non-negative weighting parameters.

In this paper we propose the generalized mirrored scheme for scheduling double round robin tournaments (DRRTs), a common topic in sports scheduling, to deal with the conflicting constraints of breaks and separation. In practice, usually a small number of breaks and a large separation are desirable, but typical methods of scheduling DRRTs cannot obtain both a minimum number of breaks and a positive separation. We firstly consider DRRTs by this scheme with a separation of two slots and a minimum number of breaks. In case the number of teams is a multiple of four, we show that such DRRTs could be generated by a constructive method; we also propose a model and find such DRRTs for any other numbers of teams up to 90. Secondly, we consider those with a separation of more than two. We show that if a minimum number of breaks is required, DRRTs with a separation of any number of slots could be obtained by a constructive method, for some large number of teams; otherwise, a tradeoff for a large separation at the cost of only four additional breaks exists for any number of teams.

We consider a chance-constrained quadratic knapsack problem (CQKP) where each item has a random size that is finitely distributed. We present a new convex 0-1 quadratic program reformulation for CQKP. This new reformulation improves the existing reformulation for general 0-1 quadratic program based on diagonal perturbation in the sense that the continuous relaxation of the new reformulation is tighter than or at least as tight as that of the existing reformulation. The improved reformulation is derived from a general matrix decomposition of the objective function and piecewise linearization of 0-1 variables. We show that the optimal parameters in the improved reformulation can be obtained by solving an SDP problem. Extension to k-item probabilistic quadratic knapsack problems is also discussed. Preliminary comparison results are reported to demonstrate the effectiveness of the improved reformulation.

The low-rank matrix recovery (LMR) arises in many fields such as signal and image processing, quantum state tomography, magnetic resonance imaging, system identification and control, and it is generally NP-hard. Recently, Majumdar and Ward [Majumdar, A and RK Ward (2011). An algorithm for sparse MRI reconstruction by Schatten p-norm minimization. Magnetic Resonance Imaging, 29, 408–417]. had successfully applied nonconvex Schatten p-minimization relaxation of LMR in magnetic resonance imaging. In this paper, our main aim is to establish RIP theoretical result for exact LMR via nonconvex Schatten p-minimization. Carefully speaking, letting be a linear transformation from ℝ^m×n into ℝ^s and r be the rank of recovered matrix X ∈ ℝ^m×n, and if satisfies the RIP condition for a given positive integer k ∈ {1, 2, …, m – r}, then r-rank matrix can be exactly recovered. In particular, we obtain a uniform bound on restricted isometry constant for any p ∈ (0, 1] for LMR via Schatten p-minimization.

The conic model proposed by Davidon (1980) [Davidon, WC (1980). Conic approximations and collinear scalings for optimizers. SIAM Journal on Numerical Analysis, 17, 268–281.] is an extension of quadratic model incorporating more information than quadratic model. In this paper, we propose a conic affine scaling dogleg method for bound constrained optimization. Under some mild conditions, the sequence generated by our algorithm converges to a stationary point. Numerical tests on a series of standard testing problems confirm the efficiency of the method.

Recently, Kitahara, and Mizuno derived an upper bound for the number of different solutions generated by the primal simplex method with Dantzig's (the most negative) pivoting rule. In this paper, we obtain an upper bound with any pivoting rule which chooses an entering variable whose reduced cost is negative at each iteration. The upper bound is applied to a linear programming problem with a totally unimodular matrix. We also obtain a similar upper bound for the dual simplex method.

In this paper, we first present a discrete fixed point theorem for contraction mappings from the product set of integer intervals into itself, which is an extension of Robert's discrete fixed point theorem. Next, we derive an existence theorem of a pure-strategy Nash equilibrium for a noncooperative n-person game from our fixed point theorem. Finally, we show that Kuhn's theorem for a game in expansive form can be explained by our existence theorem.

We study a three-player cooperative game with transferable utility where the players may form different coalition structures. A new concept of stability of a coalition is introduced, and the existence of a stable coalition is proven. Based on this stability concept, a novel approach is given to determine sensible allocations in a grand coalition of three players. We also compare our result with classical core solution and implement our theory on a specific price model.