Abstract: The selection and development of high-end weapon equipment is a strategic issue for nations. High-end weapon equipment portfolio selection (HWEPS) has attracted much attention because it is closely related to the production, deployment, and operation of weapons, which is a crucial factor determining the outcome of a war. This paper presents a united framework called capability-oriented weapon system portfolio selection (CWSPS) to solve the HWEPS problem based on a heterogeneous combat network. Specifically, the concept of an operation loop is introduced and a heterogeneous combat network model is proposed, with consideration of the different types of functional entities and information flows of high-end weapon equipment systems. Based on this, a new measure called the operational capability evaluation index (OCEI) is first proposed to assess the operational execution capability of a portfolio of high-end equipment systems. Then, a portfolio selection model is established by maximizing the cost-OCEI efficiency of high-end weapon equipment, with capability demand and the budget restriction as constraints. Finally, both an empirical case of missile defense system and numerical experiments are taken to demonstrate the reliability and effectiveness of CWSPS, and results show that our method can achieve very good performance in solving the HWEPS problem. PubDate: 2020-12-01

Abstract: This paper investigates a parallel-machine group scheduling problem where non-identical jobs with arbitrary sizes and inclusive processing set restrictions can be either processed on in-house parallel machines in the form of serial batch or outsourced with cost. The objective of our study is aimed at minimizing the weighted sum of the in-house makespan and the total outsourcing cost for a platform manufacturing enterprise. Some structural properties are identified for the optimal solution in some special cases of the studied problem, which contribute to the optimal solution for the studied problem. Further, based on these properties, a novel hybrid algorithm VNS–NKEA is proposed to solve the studied problem, which integrates neighborhood knowledge-based evolutionary algorithm (NKEA) and variable neighborhood search (VNS). To demonstrate the better performance including solution quality and the convergence speed of the proposed algorithm, computational experiments are conducted to evaluate its performance by comparing with other proposed algorithms. The experiment results show that the hybrid algorithm performs quite better than other compared algorithms for each instance, which reflect that the hybrid algorithm can solve the studied problem effectively. PubDate: 2020-12-01

Abstract: In this paper, we consider a large scale portfolio selection problem with and without a sparsity constraint. Neutral constraints on industries are included as well as investment styles. To develop fast algorithms for the use in the real financial market, we shall expose the special structure of the problem, whose Hessian is the summation of a diagonal matrix and a low rank modification. Specifically, an interior point algorithm taking use of the Sherman–Morrison–Woodbury formula is designed to solve the problem without any sparsity constraint. The complexity in each iteration of the proposed algorithm is shown to be linear with the problem dimension. In the occurrence of a sparsity constraint, we propose an efficient three-block alternating direction method of multipliers, whose subproblems are easy to solve. Extensive numerical experiments are conducted, which demonstrate the efficiency of the proposed algorithms compared with some state-of-the-art solvers. PubDate: 2020-12-01

Abstract: Parallel-batching processing and job deterioration are universal in the real industry. Scholars have deeply investigated the problem of parallel-batching scheduling and the problem of scheduling with deteriorating jobs separately. However, the situations where both parallel-batching processing and job deterioration exist simultaneously were seldom considered. This paper studies the parallel-batching scheduling problem with nonlinear processing times on a single machine, and proposes several structural properties and an optimal algorithm to solve it. Based on the above properties and optimal algorithm for the single machine setting, we further study the problem of parallel-batching scheduling with nonlinear processing times under the unrelated parallel machine setting. Since the unrelated parallel machines scheduling problem is NP-hard, a hybrid SFLA-VNS algorithm combining Shuffle Frog Leap Algorithm (SFLA) with Variable Neighborhood Search Algorithm (VNS) is proposed. Computational experiments and comparison are finally conducted to demonstrate the effectiveness of the proposed algorithm. PubDate: 2020-12-01

Abstract: This paper aims to present improvable and computable approximation approaches for solving the two-stage robust optimization problem, which arises from various applications such as optimal energy management and production planning. Based on sampling finite number scenarios of uncertainty, we can obtain a lower bound approximation and show that the corresponding solution is at least \({\varepsilon }\) -level feasible. Moreover, piecewise linear decision rules (PLDRs) are also introduced to improve the upper bound that obtained by the widely-used linear decision rule. Furthermore, we show that both the lower bound and upper bound approximation problems can be reformulated into solvable saddle point problems and consequently be solved by the mirror descent method. PubDate: 2020-12-01

Abstract: The weapon target assignment (WTA) problem, which has received much attention in the literature and is of continuing relevance, seeks within an air defense context to assign interceptors (weapons) to incoming missiles (targets) to maximize the probability of destroying the missiles. Kline et al. (J Heuristics 25:1–21, 2018) developed a heuristic algorithm based upon the solution to the Quiz Problem to solve the WTA. This heuristic found solutions within 6% of optimal, on average, for smaller problem instances and, when compared to a leading WTA heuristic from the literature, identified superlative solutions for larger instances within hundredths of a second, in lieu of minutes or hours of computational effort. Herein, we propose and test an improvement to the aforementioned heuristic, wherein a modified implementation iteratively blocks exiting assignments to an initial feasible solution, allowing superior solutions that would otherwise be prevented via a greedy selection process to be found. We compare these results to the optimal solutions as reported by a leading global optimization solver (i.e., BARON) and find solutions that are, at worst, within 2% of optimality and, at best, up to 64% better than the solutions reported to be optimal by BARON. To wit, the developed metaheuristic outperformed BARON in 25% of all instances tested, as BARON reported a suboptimal solution as being optimal for 21.1% of the instances, and it could not identify an optimal solution for the remaining 6.67% of the instances within 2 h of CPU time, a liberally imposed time limit that far exceeds practical usage considerations for this application. PubDate: 2020-12-01

Abstract: Motivated by the fact that pay-per-use rentals require firms to be responsible for the the operational costs of products and service support network, we establish a pay-per-use rental model where a firm strategically sets the availability of products for rentals to achieve the trade-off between production quantity and operational costs. Furthermore, based on the traditional sale model, we also propose a combined model of sale and pay-per-use rental. The objective is to maximize firm’s profits under three models: the sale model, the pay-per-use rental model, and the hybrid model of sale and rental. The approach of backward induction is adopted to obtain the firm’s optimal decisions on pricing and production volume. Through comparative analysis, we provide the firm’s global optimal strategic solution, and the corresponding solutions in different market environments are developed, respectively, due to the variance of polling effects and costs. The results show that under the no-pooling case where customers’ requests overlap completely, the hybrid model always show higher profitability than the pay-per-use rental model, and it performs better than the sales model only when the per-unit operational and production costs are low. Under the perfect-pooling case where customers’ requests do not overlap, the hybrid model is always the optimal strategy. Numerical experiments are also conducted to illustrate the results under the general pooling case. PubDate: 2020-12-01

Abstract: Recently, there are much interests in studying smoothing Newton method for solving montone second-order cone complementarity problem (SOCCP) or SOCCPs with Cartesian \(P/P_0\) -property. In this paper, we propose a smoothing quasi-Newon method for solving general SOCCP. We show that the proposed method is well-defined without any additional assumption and has global convergence under standard conditions. Moreover, under the Jacobian nonsingularity assumption, the method is shown to have local superlinear or quadratic convergence rate. Our preliminary numerical experiments show the method could be very effective for solving SOCCPs. PubDate: 2020-11-24

Abstract: We introduce the conditional p-dispersion problem (c-pDP), an incremental variant of the p-dispersion problem (pDP). In the c-pDP, one is given a set N of n points, a symmetric dissimilarity matrix D of dimensions \(n\times n\) , an integer \(p\ge 1\) and a set \(Q\subseteq N\) of cardinality \(q\ge 1\) . The objective is to select a set \(P\subset N\setminus Q\) of cardinality p that maximizes the minimal dissimilarity between every pair of selected vertices, i.e., \(z(P\cup Q) {:}{=}\min \{D(i, j), i, j\in P\cup Q\}\) . The set Q may model a predefined subset of preferences or hard location constraints in incremental network design. We adapt the state-of-the-art algorithm for the pDP to the c-pDP and include an ad-hoc acceleration mechanism designed to leverage the information provided by the set Q to further reduce the size of the problem instance. We perform exhaustive computational experiments and show that the proposed acceleration mechanism helps reduce the total computational time by a factor of five on average. We also assess the scalability of the algorithm and derive sensitivity analyses. PubDate: 2020-11-21

Abstract: Papadimitriou and Yannakakis (Proceedings of the 41st annual IEEE symposium on the Foundations of Computer Science (FOCS), pp 86–92, 2000) show that the polynomial-time solvability of a certain auxiliary problem determines the class of multiobjective optimization problems that admit a polynomial-time computable \((1+\varepsilon , \dots , 1+\varepsilon )\) -approximate Pareto set (also called an \(\varepsilon \) -Pareto set). Similarly, in this article, we characterize the class of multiobjective optimization problems having a polynomial-time computable approximate \(\varepsilon \) -Pareto set that is exact in one objective by the efficient solvability of an appropriate auxiliary problem. This class includes important problems such as multiobjective shortest path and spanning tree, and the approximation guarantee we provide is, in general, best possible. Furthermore, for biobjective optimization problems from this class, we provide an algorithm that computes a one-exact \(\varepsilon \) -Pareto set of cardinality at most twice the cardinality of a smallest such set and show that this factor of 2 is best possible. For three or more objective functions, however, we prove that no constant-factor approximation on the cardinality of the set can be obtained efficiently. PubDate: 2020-11-18

Abstract: We study distributionally robust chance-constrained programming (DRCCP) optimization problems with data-driven Wasserstein ambiguity sets. The proposed algorithmic and reformulation framework applies to all types of distributionally robust chance-constrained optimization problems subjected to individual as well as joint chance constraints, with random right-hand side and technology vector, and under two types of uncertainties, called uncertain probabilities and continuum of realizations. For the uncertain probabilities (UP) case, we provide new mixed-integer linear programming reformulations for DRCCP problems. For the continuum of realizations case with random right-hand side, we propose an exact mixed-integer second-order cone programming (MISOCP) reformulation and a linear programming (LP) outer approximation. For the continuum of realizations (CR) case with random technology vector, we propose two MISOCP and LP outer approximations. We show that all proposed relaxations become exact reformulations when the decision variables are binary or bounded general integers. For DRCCP with individual chance constraint and random right-hand side under both the UP and CR cases, we also propose linear programming reformulations which need the ex-ante derivation of the worst-case value-at-risk via the solution of a finite series of linear programs determined via a bisection-type procedure. We evaluate the scalability and tightness of the proposed MISOCP and (MI)LP formulations on a distributionally robust chance-constrained knapsack problem. PubDate: 2020-11-17

Abstract: In this article, we introduce a general splitting method with linearization to solve the split feasibility problem and propose a way of selecting the stepsizes such that the implementation of the method does not need any prior information about the operator norm. We present the constant and adaptive relaxation parameters, and the latter is “optimal” in theory. These ways of selecting stepsizes and relaxation parameters are also practised to the relaxed splitting method with linearization where the two closed convex sets are both level sets of convex functions. The weak convergence of two proposed methods is established under standard conditions and the linear convergence of the general splitting method with linearization is analyzed. The numerical examples are presented to illustrate the advantage of our methods by comparing with other methods. PubDate: 2020-11-06

Abstract: We study the split feasibility problem with multiple output sets in Hilbert spaces. In order to solve this problem we introduce two iterative methods by using an optimization approach. Our iterative methods do not depend on the norm of the transfer operators. PubDate: 2020-11-05

Abstract: In this paper, we study the optimum correction of the absolute value equations through making minimal changes in the coefficient matrix and the right hand side vector and using spectral norm. This problem can be formulated as a non-differentiable, non-convex and unconstrained fractional quadratic programming problem. The regularized least squares is applied for stabilizing the solution of the fractional problem. The regularized problem is reduced to a unimodal single variable minimization problem and to solve it a bisection algorithm is proposed. The main difficulty of the algorithm is a complicated constraint optimization problem, for which two novel methods are suggested. We also present optimality conditions and bounds for the norm of the optimal solutions. Numerical experiments are given to demonstrate the effectiveness of suggested methods. PubDate: 2020-11-05

Abstract: We provide analytical results for a static portfolio optimization problem with two coherent risk measures. The use of two risk measures is motivated by joint decision-making for portfolio selection where the risk perception of the portfolio manager is of primary concern, hence, it appears in the objective function, and the risk perception of an external authority needs to be taken into account as well, which appears in the form of a risk constraint. The problem covers the risk minimization problem with an expected return constraint and the expected return maximization problem with a risk constraint, as special cases. For the general case of an arbitrary joint distribution for the asset returns, under certain conditions, we characterize the optimal portfolio as the optimal Lagrange multiplier associated to an equality-constrained dual problem. Then, we consider the special case of Gaussian returns for which it is possible to identify all cases where an optimal solution exists and to give an explicit formula for the optimal portfolio whenever it exists. PubDate: 2020-11-01

Abstract: Choo (Oper Res 32:216–220, 1984) has proved that any efficient solution of a linear fractional vector optimization problem with a bounded constraint set is properly efficient in the sense of Geoffrion. This paper studies Geoffrion’s properness of the efficient solutions of linear fractional vector optimization problems with unbounded constraint sets. By examples, we show that there exist linear fractional vector optimization problems with the efficient solution set being a proper subset of the unbounded constraint set, which have improperly efficient solutions. Then, we establish verifiable sufficient conditions for an efficient solution of a linear fractional vector optimization to be a Geoffrion properly efficient solution by using the recession cone of the constraint set. For bicriteria problems, it is enough to employ a system of two regularity conditions. If the number of criteria exceeds two, a third regularity condition must be added to the system. The obtained results complement the above-mentioned remarkable theorem of Choo and are analyzed through several interesting examples, including those given by Hoa et al. (J Ind Manag Optim 1:477–486, 2005). PubDate: 2020-11-01

Abstract: We consider the optimization of a computer model where each simulation either fails or returns a valid output performance. We first propose a new joint Gaussian process model for classification of the inputs (computation failure or success) and for regression of the performance function. We provide results that allow for a computationally efficient maximum likelihood estimation of the covariance parameters, with a stochastic approximation of the likelihood gradient. We then extend the classical improvement criterion to our setting of joint classification and regression. We provide an efficient computation procedure for the extended criterion and its gradient. We prove the almost sure convergence of the global optimization algorithm following from this extended criterion. We also study the practical performances of this algorithm, both on simulated data and on a real computer model in the context of automotive fan design. PubDate: 2020-11-01

Abstract: This article deals with considering stability properties of Pareto minimal solutions to set optimization problems with the set less order relation in real topological Hausdorff vector spaces. We focus on studying the Painlevé–Kuratowski convergence of Pareto minimal elements in the image space. Employing convexity properties, we study the external stability of Pareto minimal solutions via weak ones. Then, we use converse properties to investigate external stability conditions to such problems where Pareto minimal solution sets and weak/ideal ones are distinct. For the internal stability, we propose a concept of compact convergence in the sense of Painlevé–Kuratowski and use it together with a domination property to analyze stability conditions for the reference problems. PubDate: 2020-11-01

Abstract: In this paper, we give a new penalized semidefinite programming approach for non-convex quadratically-constrained quadratic programs (QCQPs). We incorporate penalty terms into the objective of convex relaxations in order to retrieve feasible and near-optimal solutions for non-convex QCQPs. We introduce a generalized linear independence constraint qualification (GLICQ) criterion and prove that any GLICQ regular point that is sufficiently close to the feasible set can be used to construct an appropriate penalty term and recover a feasible solution. Inspired by these results, we develop a heuristic sequential procedure that preserves feasibility and aims to improve the objective value at each iteration. Numerical experiments on large-scale system identification problems as well as benchmark instances from the library of quadratic programming demonstrate the ability of the proposed penalized semidefinite programs in finding near-optimal solutions for non-convex QCQP. PubDate: 2020-11-01

Abstract: In this paper we present two main situations when the limit of Pareto minima of a sequence of perturbations of a set-valued map F is a critical point of F. The concept of criticality is understood in the Fermat generalized sense by means of limiting (Mordukhovich) coderivative. Firstly, we consider perturbations of enlargement type which, in particular, cover the case of perturbation with dilating cones. Secondly, we present the case of Aubin type perturbations, and for this we introduce and study a new concept of openness with respect to a cone. PubDate: 2020-11-01