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     

Minimal concave cost rebalance of a portfolio to the efficient frontier

One usually constructs a portfolio on the efficient frontier, but it may not be efficient after, say three months since the efficient frontier will shift as the elapse of time. We then have to rebalance the portfolio if the deviation is no longer acceptable. The method to be proposed in this paper is to find a portfolio on the new efficient frontier such that the total transaction cost required for this rebalancing is minimal. This problem results in a nonconvex minimization problem, if we use mean-variance model. In this paper we will formulate this problem by using absolute deviation as the measure of risk and solve the resulting linearly constrained concave minimization problem by a branch and bound algorithm successfully applied to portfolio optimization problem under concave transaction costs. It will be demonstrated that this method is efficient and that it leads to a significant reduction of transaction costs. Key words.portfolio optimization – rebalance – mean-absolute deviation model – concave cost minimization – optimization over the efficient set – global optimizationMathematics Subject Classification (1991):20E28, 20G40, 20C20     

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     

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     

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     

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     

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.     

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.     

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     

A finite element approximation of the Griffith’s model in fracture mechanics

Summary. The Griffith model for the mechanics of fractures in brittle materials is consider in the weak formulation of SBD spaces. We suggest an approximation, in the sense of –convergence, by a sequence of discrete functionals defined on finite elements spaces over structured and adaptive triangulations. The quasi-static evolution for boundary value problems is also taken into account and some numerical results are shown. Mathematics Subject Classification (2000):65N30     

Tight, not semi–fillable contact circle bundles

Extending our earlier results, we prove that certain tight contact structures on circle bundles over surfaces are not symplectically semi–fillable, thus confirming a conjecture of Ko Honda.Mathematics Subject Classification (2000)57R57, 57R17Partially supported by MURST and member of EDGE, Research Training Network HPRN-CT-2000-00101, supported by The European Human Potential ProgrammePartially supported by OTKA T034885     

Uniform error estimates for a class of intermediate cylindrical shell problems

Summary. A uniform in thickness error estimate is obtained for a particular class of intermediate Koiter shell problems, solved with a classical conforming finite element method. The model problem is that of a cylinder under a class of irregular loads which, due to particular symmetries, allow a simplified reformulation on a one dimensional domain. The result is an almost h^s error behavior in the H^–1 dual norm, were s>0 depends on the load regularity. Such estimate is believable to be sharp (this additional claim is supported by some numerical tests). Mathematics Subject Classification (2000):65N30Received: 17, October 2001     

Self-similar fragmentations derived from the stable tree I

The basic object we consider is a certain model of continuum random tree, called the stable tree. We construct a fragmentation process (F ^– (t),t0) out of this tree by removing the vertices located under height t. Thanks to a self-similarity property of the stable tree, we show that the fragmentation process is also self-similar. The semigroup and other features of the fragmentation are given explicitly. Asymptotic results are given, as well as a couple of related results on continuous-state branching processes. Research supported in part by NSF Grant DMS-0071448. Mathematics Subject Classification (2000):60J25, 60G52, 60J80     

Global well-posedness for an inhomogeneous LSW–model in unbounded domains

The LSW–theory of domain coarsening describes the evolution of the size distribution of a system of particles evolving by diffusional mass exchange to reduce their total surface area. We prove existence and uniqueness of solutions to an inhomogeneous extension of the LSW–model in unbounded domains. This model arises naturally as a homogenization limit of the underlying free boundary problem in the case of a system of particles for which the screening length (the effective range of particle interactions) is smaller than the system size. The crucial ingredients in the analysis are, first, to establish the screening property by showing that the corresponding Greens function decreases exponentially over the relevant distances. Second, we have to control the mass fluxes between different regions to prevent aggregation of mass in few particles which would result in blow–up of the solution.Mathematics Subject Classification (2000):82C26, 35Q72, 35D05Received: 16, December 2001     

Constraint Propagation and Problem Decomposition: A Preprocessing Procedure for the Job Shop Problem

In recent years, constraint propagation techniques have been shown to be highly effective for solving difficult scheduling problems. In this paper, we present an algorithm which combines constraint propagation with a problem decomposition approach in order to simplify the solution of the job shop scheduling problem. This is mainly guided by the observation that constraint propagation is more effective for small problem instances. Roughly speaking, the algorithm consists of deducing operation sequences that are likely to occur in an optimal solution of the job shop scheduling problem (JSP).The algorithm for which the name edge-guessing procedure has been chosen – since with respect to the job shop scheduling problem (JSP) the deduction of machine sequences is mainly equivalent to orienting edges in a disjunctive graph – can be applied in a preprocessing step, reducing the solution space, thus speeding up the overall solution process. In spite of the heuristic nature of edge-guessing, it still leads to near-optimal solutions. If combined with a heuristic algorithm, we will demonstrate that given the same amount of computation time, the additional application of edge-guessing leads to better solutions. This has been tested on a set of well-known JSP benchmark problem instances.     

Linear programming with entropic perturbation

In this paper, we derive an unconstrained convex programming approach to solving standard form linear programs through an entropic perturbation. The whole duality theory is established by using only one simple inequality lnz z –1 forz > 0. A curved search algorithm is also proposed for obtaining a pair of primal and dual-optimal solutions. The proposed algorithm is proven to be globally convergent with a quadratic rate of convergence. Computational results are included in support of theoretic findings.The work is partially supported by the North Carolina Supercomputing Center, the Cray Research Award, and the National Science Council of the Republic of China # NSC 81-0415-E-007-10.     

The left-definite Legendre type boundary problem

The left-definite Legendre type boundary problem concerns the study of a fourth-order singular differential expressionM _k [–] in a weighted Sobolev spaceH generated by a Dirichlet inner product. The fourth-order differential equation

On the parallel factorization of matrices over principal ideal rings

We describe all the factorizations A=BC (up to associates) of a matrix A over a commutative principal ideal domain parallel to the factorization D^A= of its canonical diagonal form D^A ( and are diagonal matrices), that is, the factorizations such that the matrices B and C are equivalent to the matrices and respectively.Translated fromMatematichni Metodi ta Fiziko-Mekhanichni Polya, Vol. 40, No. 4, 1997, pp. 96–100.