A subproblem-centric model and approach to the nurse scheduling problem

The number of hospitals in Japan exceeds 10,000, and every month nurses are scheduled to shifts in about 30,000 units in total. There is serious demand for automating this scheduling task. In this paper, we introduce a mathematical programming formulation of the nurse scheduling problem in Japan, and develop a meta-heuristic approach to solve the problem. This scheduling problem is a hard combinatorial problem due to tight constraints involving such factors as the skill level of a team, the need to balance workload among nurses, and the consideration of nurses' preferences, even though the number of the nurses to be scheduled is not large, at between 20 and 40. The performance of our approach is demonstrated by the successful solution of data taken from actual scheduling problems. The proposed model and approach can be adapted for the majority of hospitals in Japan, as well as for some hospitals in other countries, and is likely applicable to many other scheduling problems in the fields of business and logistics. Key words.nurse scheduling – block-angular problem – subproblem – integer programming – relaxation – tabu search – branch-and-boundMathematics Subject Classification (1991):20E28, 20G40, 20C20     

Local search algorithms for the rectangle packing problem with general spatial costs

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms. Key words.rectangle packing – sequence pair – general spatial cost – dynamic programming – metaheuristicsMathematics Subject Classification (1991):20E28, 20G40, 20C20     

Optimality and duality theory for stochastic optimization problems with nonlinear dominance constraints

We consider a new class of optimization problems involving stochastic dominance constraints of second order. We develop a new splitting approach to these models, optimality conditions and duality theory. These results are used to construct special decomposition methods.This research was supported by the NSF awards DMS-0303545 and DMS-0303728.Key words.Stochastic programming – stochastic ordering – semi-infinite optimized – decomposition     

Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints

We will propose a branch and bound algorithm for calculating a globally optimal solution of a portfolio construction/rebalancing problem under concave transaction costs and minimal transaction unit constraints. We will employ the absolute deviation of the rate of return of the portfolio as the measure of risk and solve linear programming subproblems by introducing (piecewise) linear underestimating function for concave transaction cost functions. It will be shown by a series of numerical experiments that the algorithm can solve the problem of practical size in an efficient manner. Received: July 15, 1999 / Accepted: October 1, 2000?Published online December 15, 2000     

Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank

We consider primal-dual algorithms for certain types of infinite-dimensional optimization problems. Our approach is based on the generalization of the technique of finite-dimensional Euclidean Jordan algebras to the case of infinite-dimensional JB-algebras of finite rank. This generalization enables us to develop polynomial-time primal-dual algorithms for ``infinite-dimensional second-order cone programs.' We consider as an example a long-step primal-dual algorithm based on the Nesterov-Todd direction. It is shown that this algorithm can be generalized along with complexity estimates to the infinite-dimensional situation under consideration. An application is given to an important problem of control theory: multi-criteria analytic design of the linear regulator. The calculation of the Nesterov-Todd direction requires in this case solving one matrix differential Riccati equation plus solving a finite-dimensional system of linear algebraic equations on each iteration. The number of equations and unknown variables of this algebraic system is m+1, where m is a number of quadratic performance criteria. Key words.polynomial-time primal-dual interior-point methods – JB-algebras – infinite-dimensional problems – optimal control problemsThis author was supported in part by DMS98-03191 and DMS01-02698.This author was supported in part by the Grant-in-Aid for Scientific Research (C) 11680463 of the Ministry of Education, Culture, Sports, Science and Technology of Japan.Mathematics Subject Classification (1991):90C51, 90C48, 34H05, 49N05     

Global Optimization Versus Integer Programming in Portfolio Optimization under Nonconvex Transaction Costs

This paper is concerned with a portfolio optimization problem under concave and piecewise constant transaction cost. We formulate the problem as nonconcave maximization problem under linear constraints using absolute deviation as a measure of risk and solve it by a branch and bound algorithm developed in the field of global optimization. Also, we compare it with a more standard 0–1 integer programming approach. We will show that a branch and bound method elaborating the special structure of the problem can solve the problem much faster than the state-of-the integer programming code.     

On the shape–from–moments problem and recovering edges from noisy Radon data

We consider the problem of reconstructing a planar convex set from noisy observations of its moments. An estimation method based on pointwise recovering of the support function of the set is developed. We study intrinsic accuracy limitations in the shape–from–moments estimation problem by establishing a lower bound on the rate of convergence of the mean squared error. It is shown that the proposed estimator is near–optimal in the sense of the order. An application to tomographic reconstruction is discussed, and it is indicated how the proposed estimation method can be used for recovering edges from noisy Radon data.Mathematics Subject Classification (2000):62C20, 62G20, 94A12     

Coderivatives in parametric optimization

We consider parametric families of constrained problems in mathematical programming and conduct a local sensitivity analysis for multivalued solution maps. Coderivatives of set-valued mappings are our basic tool to analyze the parametric sensitivity of either stationary points or stationary point-multiplier pairs associated with parameterized optimization problems. An implicit mapping theorem for coderivatives is one key to this analysis for either of these objects, and in addition, a partial coderivative rule is essential for the analysis of stationary points. We develop general results along both of these lines and apply them to study the parametric sensitivity of stationary points alone, as well as stationary point-multiplier pairs. Estimates are computed for the coderivative of the stationary point multifunction associated with a general parametric optimization model, and these estimates are refined and augmented by estimates for the coderivative of the stationary point-multiplier multifunction in the case when the constraints are representable in a special composite form. When combined with existing coderivative formulas, our estimates are entirely computable in terms of the original data of the problem. Key words.parametric optimization – variational analysis – sensitivity – Lipschitzian stability – generalized differentiation – coderivativesThis research was partly supported by the National Science Foundation under grant DMS-0072179.     

Convex approximations for complete integer recourse models

We consider convex approximations of the expected value function of a two-stage integer recourse problem. The convex approximations are obtained by perturbing the distribution of the random right-hand side vector. It is shown that the approximation is optimal for the class of problems with totally unimodular recourse matrices. For problems not in this class, the result is a convex lower bound that is strictly better than the one obtained from the LP relaxation.This research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences.Key words.integer recourse – convex approximationMathematics Subject Classification (1991):90C15, 90C11     

Portfolio optimization under D.C. transaction costs and minimal transaction unit constraints

This paper addresses itself to a portfolio optimization problem under nonconvex transaction costs and minimal transaction unit constraints. Associated with portfolio construction is a fee for purchasing assets. Unit transaction fee is larger when the amount of transaction is smaller. Hence the transaction cost is usually a concave function up to certain point. When the amount of transaction increases, the unit price of assets increases due to illiquidity/market impact effects. Hence the transaction cost becomes convex beyond certain bound. Therefore, the net expected return becomes a general d.c. function (difference of two convex functions). We will propose a branch-and-bound algorithm for the resulting d.c. maximization problem subject to a constraint on the level of risk measured in terms of the absolute deviation of the rate of return of a portfolio. Also, we will show that the minimal transaction unit constraints can be incorporated without excessively increasing the amount of computation.     

Portfolio selection with a minimax measure in safety constraint

In this paper, we attempt to design a portfolio optimization model for investors who desire to minimize the variation around the mean return and at the same time wish to achieve better return than the worst possible return realization at every time point in a single period portfolio investment. The portfolio is to be selected from the risky assets in the equity market. Since the minimax portfolio optimization model provides us with the portfolio that maximizes (minimizes) the worst return (worst loss) realization in the investment horizon period, in order to safeguard the interest of investors, the optimal value of the minimax optimization model is used to design a constraint in the mean-absolute semideviation model. This constraint can be viewed as a safety strategy adopted by an investor. Thus, our proposed bi-objective linear programming model involves mean return as a reward and mean-absolute semideviation as a risk in the objective function and minimax as a safety constraint, which enables a trade off between return and risk with a fixed safety value. The efficient frontier of the model is generated using the augmented -constraint method on the GAMS software. We simultaneously solve the ratio optimization problem which maximizes the ratio of mean return over mean-absolute semideviation with same minimax value in the safety constraint. Subsequently, we choose two portfolios on the above generated efficient frontier such that the risk from one of them is less and the mean return from other portfolio is more than the respective quantities of the optimal portfolio from the ratio optimization model. Extensive computational results and in-sample and out-of-sample analysis are provided to compare the financial performance of the optimal portfolios selected by our proposed model with that of the optimal portfolios from the existing minimax and mean-absolute semideviation portfolio optimization models on real data from S&P CNX Nifty index.     

A note on the complexity of determining optimal strategies in games with common payoffs

In a recent paper [Int J Game Theory (2001) 30:99–106], Chu and Halpern investigated the problem of finding optimal strategies in certain games with common payoffs. This short technical note answers a computational complexity question that was left open in their paper. Acknowledgement.I thank the referee for a very careful reading of the paper, and for pointing out to me a number of typos and inconsistencies in an earlier version of the paper.     

含有资本结构因子、交易成本和风险偏好的模糊最优化投资模型

建立了含有资本结构因子、交易成本和风险偏好的模糊最优化投资模型,在允许卖空条件下,给出最优投资策略及有效边界;在不允许卖空条件下,给出了确定其有效边界的算法,并分析了风险偏好、无风险利率和交易成本对有效边界的影响,最后通过示例进行了分析.     

Genetic algorithms for portfolio selection problems with minimum transaction lots

Conventionally, portfolio selection problems are solved with quadratic or linear programming models. However, the solutions obtained by these methods are in real numbers and difficult to implement because each asset usually has its minimum transaction lot. Methods considering minimum transaction lots were developed based on some linear portfolio optimization models. However, no study has ever investigated the minimum transaction lot problem in portfolio optimization based on Markowitz’ model, which is probably the most well-known and widely used. Based on Markowitz’ model, this study presents three possible models for portfolio selection problems with minimum transaction lots, and devises corresponding genetic algorithms to obtain the solutions. The results of the empirical study show that the portfolios obtained using the proposed algorithms are very close to the efficient frontier, indicating that the proposed method can obtain near optimal and also practically feasible solutions to the portfolio selection problem in an acceptable short time. One model that is based on a fuzzy multi-objective decision-making approach is highly recommended because of its adaptability and simplicity.     

A Matlab-based rapid method for computing lattice-subspaces and vector sublattices of : Applications in portfolio insurance

This paper provides the construction of a powerful and efficient computational method, that translates Polyrakis algorithm [I.A. Polyrakis, Minimal lattice-subspaces, Trans. Am. Math. Soc. 351 (1999) 4183–4203, Theorem 3.19] for the calculation of lattice-subspaces and vector sublattices in . In the theory of finance, lattice-subspaces have been extensively used in order to provide a characterization of market structures in which the cost-minimizing portfolio is price-independent. Specifically, we apply our computational method in order to solve a cost minimization problem that ensures the minimum-cost insured portfolio.     

Semistrictly quasiconvex mappings and non-convex vector optimization

This paper introduces a new class of non-convex vector functions strictly larger than that of P-quasiconvexity, with P ^m being the underlying ordering cone, called semistrictly ( ^m\ –int P)-quasiconvex functions. This notion allows us to unify various results on existence of weakly efficient (weakly Pareto) optima. By imposing a coercivity condition we establish also the compactness of the set of weakly Pareto solutions. In addition, we provide various characterizations for the non-emptiness, convexity and compactness of the solution set for a subclass of quasiconvex vector optimization problems on the real-line. Finally, it is also introduced the notion of explicit ( ^m\ –int P)-quasiconvexity (equivalently explicit (int P)-quasiconvexity) which plays the role of explicit quasiconvexity (quasiconvexity and semistrict quasiconvexity) of real-valued functions.Acknowldegements.The author wishes to thank both referees for their careful reading of the paper, their comments, remarks, helped to improve the presentation of some results. One of the referee provided the references [5, 6] and indirectly [20].     

Minimal covering problem and redundancy reduction in databases

One of the main problems in efficient organization of a database system is minimization of the redundancy of information. In this paper, we enumerate the causes of redundancy and reduce the problem of redundancy minimization to the minimum covering problem. This requires inclusion in the database management system of a module for aggregation of data elements into larger constructs — segments, records, files. The module can be software or hardware implemented. Regardless of its implementation, the module has the structure of a 0–1 matrix, which can be transformed by the standard methods of block matrices. A compression algorithm is proposed, which reduces the redundancy introduced by the designer or by the users in single and multiuser queries.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 64, pp. 141–144, 1988.     

The conjugacy and isomorphism problems for combable groups

There exist combable groups in which the conjugacy problem is unsolvable. The isomorphism problem is unsolvable for certain recursive sequences of finite presentations of combable groups. Mathematics Subject Classification(2000): 20F67, 20F10, 20F65This research was supported by an EPSRC Advanced Fellowship