Solving the Rectangular assignment problem and applications

The rectangular assignment problem is a generalization of the linear assignment problem (LAP): one wants to assign a number of persons to a smaller number of jobs, minimizing the total corresponding costs. Applications are, e.g., in the fields of object recognition and scheduling. Further, we show how it can be used to solve variants of the LAP, such as the k-cardinality LAP and the LAP with outsourcing by transformation. We introduce a transformation to solve the machine replacement LAP.     

On the mathematical formulation of the problem of reassembling fragmented objects: two new theorems

In this paper two new theorems are proved in association with the problem of matching three dimensional solid bodies. Rigorous mathematical criteria are given in order to test if two such bodies actually match in a certain position. Since this problem finds important application to the actual problem of reassembling fragmented objects e.g. archaeological, special care is taken to account for small gaps between matching fragments and fuzziness of the matching parameters.     

A new destructive bounding scheme for the bin packing problem

In this paper, we present a new lower bounding scheme for the one-dimensional bin packing problem based on a destructive approach and we prove its effectiveness to solve hard instances. Performance comparison to other available lower bounds shows the effectiveness of our proposed lower bounds.     

The effective application of a new approach to the generalized orienteering problem

The Orienteering Problem (OP) is an important problem in network optimization in which each city in a network is assigned a score and a maximum-score path from a designated start city to a designated end city is sought that is shorter than a pre-specified length limit. The Generalized Orienteering Problem (GOP) is a generalized version of the OP in which each city is assigned a number of scores for different attributes and the overall function to optimize is a function of these attribute scores. In this paper, the function used was a non-linear combination of attribute scores, making the problem difficult to solve. The GOP has a number of applications, largely in the field of routing. We designed a two-parameter iterative algorithm for the GOP, and computational experiments suggest that this algorithm performs as well as or better than other heuristics for the GOP in terms of solution quality while running faster. Further computational experiments suggest that our algorithm also outperforms the leading algorithm for solving the OP in terms of solution quality while maintaining a comparable solution speed.     

The Lewy–Stampacchia inequality for the obstacle problem with quadratic growth in the gradient

In this paper we prove that at least one solution of the obstacle problem for a linear elliptic operator perturbed by a nonlinearity having quadratic growth in the gradient satisfies the Lewy–Stampacchia inequality.

---

Résumé Nous démontrons dans cet article qu’au moins une solution du problème de l’obstacle pour un opérateur elliptique linéaire perturbé par une non linéarité à croissance quadratique par rapport au gradient vérifie l’inégalité de Lewy–Stampacchia.

---

---

Mathematics Subject Classification (2000) 35J85, 47J20     

The Poincaré series of divisorial valuations in the plane defines the topology of the set of divisors

With a plane curve singularity one associates a multi-index filtration on the ring of germs of functions of two variables defined by the orders of a function on irreducible components of the curve. The Poincaré series of this filtration turns out to coincide with the Alexander polynomial of the curve germ. For a finite set of divisorial valuations on the ring corresponding to some components of the exceptional divisor of a modification of the plane, in a previous paper there was obtained a formula for the Poincaré series of the corresponding multi-index filtration similar to the one associated with plane germs. Here we show that the Poincaré series of a set of divisorial valuations on the ring of germs of functions of two variables defines “the topology of the set of the divisors” in the sense that it defines the minimal resolution of this set up to combinatorial equivalence. For the plane curve singularity case, we also give a somewhat simpler proof of the statement by Yamamoto which shows that the Alexander polynomial is equivalent to the embedded topology.     

A new dispatching rule based genetic algorithm for the multi-objective job shop problem

Hyper-heuristics or “methodologies to choose heuristics” are becoming increasingly popular given their suitability to solve hard real world combinatorial optimisation problems. Their distinguishing feature is that they operate in the space of heuristics or heuristic components rather than in the solution space. In Dispatching Rule Based Genetic Algorithms (DRGA) solutions are represented as sequences of dispatching rules which are called one at a time and used to sequence a number of operations onto machines. The number of operations that each dispatching rule in the sequence handles is a parameter to which DRGA is notoriously sensitive. This paper proposes a new hybrid DRGA which searches simultaneously for the best sequence of dispatching rules and the number of operations to be handled by each dispatching rule. The investigated DRGA uses the selection mechanism of NSGA-II when handling multi-objective problems.     

Martingale Approximation and Optimality of Some Conditions for the Central Limit Theorem

Let (X _i ) be a stationary and ergodic Markov chain with kernel Q and f an L ² function on its state space. If Q is a normal operator and f=(I?Q)^1/2 g (which is equivalent to the convergence of \(\sum_{n=1}^{\infty}\frac{\sum_{k=0}^{n-1}Q^{k}f}{n^{3/2}}\) in L ²), we have the central limit theorem [cf. (Derriennic and Lin in C.R. Acad. Sci. Paris, Sér. I 323:1053–1057, 1996; Gordin and Lif?ic in Third Vilnius conference on probability and statistics, vol. 1, pp. 147–148, 1981)]. Without assuming normality of Q, the CLT is implied by the convergence of \(\sum_{n=1}^{\infty}\frac{\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}}{n^{3/2}}\), in particular by \(\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}=o(\sqrt{n}/\log^{q}n)\), q>1 by Maxwell and Woodroofe (Ann. Probab. 28:713–724, 2000) and Wu and Woodroofe (Ann. Probab. 32:1674–1690, 2004), respectively. We show that if Q is not normal and f∈(I?Q)^1/2 L ², or if the conditions of Maxwell and Woodroofe or of Wu and Woodroofe are weakened to \(\sum_{n=1}^{\infty}c_{n}\frac{\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}}{n^{3/2}}<\infty\) for some sequence c _n ↘0, or by \(\|\sum_{k=0}^{n-1}Q^{k}f\|_{2}=O(\sqrt{n}/\log n)\), the CLT need not hold.     

On Ostrowski’s disk theorem and lower bounds for the smallest eigenvalues and singular values

The paper refines the classical Ostrowski disk theorem and suggests lower bounds for the smallest-in-modulus eigenvalue and the smallest singular value of a square matrix under certain diagonal dominance conditions. A lower bound for the smallest-in-modulus eigenvalue of a product of m ≥ 2 matrices satisfying joint diagonal dominance conditions is obtained. The particular cases of the bounds suggested that correspond to the infinity norm are discussed separately and compared with some known results. Bibliography: 8 titles.     

Verified bounds for singular values,in particular for the spectral norm of a matrix and its inverse

The singular value decomposition and spectral norm of a matrix are ubiquitous in numerical analysis. They are extensively used in proofs, but usually it is not necessary to compute them. However, there are some important applications in the realm of verified error bounds for the solution of ordinary and partial differential equations where reasonably tight error bounds for the spectral norm of a matrix are mandatory. We present various approaches to this together with some auxiliary useful estimates.     

Students’ coordination of lower and higher dimensional units in the context of constructing and evaluating sums of consecutive whole numbers

This paper examines how three eighth grade students coordinated lower and higher dimensional units (e.g., composite units and pairs) in the context of constructing a formula for evaluating sums of consecutive whole numbers while solving combinatorics problems (e.g., 1 + 2 + ⋯ + 15 = (16 × 15)/2). The data is drawn from the beginning of an 8-month teaching experiment. The findings from the study include: (1) a framework for understanding how students coordinate lower and higher dimensional units; (2) identification of key learning that occurred as students made the transition between solving two kinds of combinatorics problems; and (3) identification of the links between the way students’ coordinated lower and higher dimensional units and their evaluation of sums of consecutive whole numbers. Implications for research and teaching are considered.     

A new approach with new solutions to the Matkowski and Wesołowski problem

Aequationes mathematicae - Based on a result of de&nbsp;Rham, we give a family of functions solving the Matkowski and Weso?owski problem. This family consists of Hölder continuous...     

Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem

In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.     

Numerical approximation of the LQR problem in a strongly damped wave equation

The aim of this work is to obtain optimal-order error estimates for the LQR (Linear-quadratic regulator) problem in a strongly damped 1-D wave equation. We consider a finite element discretization of the system dynamics and a control law constant in the spatial dimension, which is studied in both point and distributed case. To solve the LQR problem, we seek a feedback control which depends on the solution of an algebraic Riccati equation. Optimal error estimates are proved in the framework of the approximation theory for control of infinite-dimensional systems. Finally, numerical results are presented to illustrate that the optimal rates of convergence are achieved.     

Remarks on the Gagliardo-Nirenberg Type Inequality in the Besov and the Triebel-Lizorkin Spaces in the Limiting Case

We consider the generalized Gagliardo-Nirenberg inequality in $\Bbb{R}^{n}$ including homogeneous Besov space $\dot{B}^{s}_{r,\rho}(\Bbb{R}^{n})$ with the critical order s=n/r, which describes the continuous embedding such as $L^{p}(\Bbb{R}^{n})\cap\dot{B}^{n/r}_{r,\rho}(\Bbb{R}^{n})\subset L^{q}(\Bbb{R}^{n})$ for all q with p ≦ q<∞, where 1≦ p ≦ r<∞ and 1<ρ ≦∞. Indeed, the following inequality holds: $$\|u\|_{L^{q}(\Bbb{R}^{n})}\leqq C\,q^{1-1/\rho}\|u\|_{L^{p}(\Bbb{R}^{n})}^{p/q}\|u\|_{\dot{B}^{n/r}_{r,\rho}(\Bbb{R}^{n})}^{1-p/q},$$ where C is a constant depending only on r. In this inequality, we have the exact order 1?1/ρ of divergence to the power q tending to the infinity. Furthermore, as a corollary of this inequality, we obtain the Gagliardo-Nirenberg inequality with the homogeneous Triebel-Lizorkin space $\dot{F}^{n/r}_{r,\rho}(\Bbb{R}^{n})$ , which implies the usual Sobolev imbedding with the critical Sobolev space $\dot{H}^{n/r}_{r}(\Bbb{R}^{n})$ . Moreover, as another corollary, we shall prove the Trudinger-Moser type inequality in $\dot{B}^{n/r}_{r,\rho}(\Bbb{R}^{n})$ .     

Some qualitative effects in the exact solutions of the Lamé problem for large deformations

Qualitative effects in the solution of a number of radially symmetric and plane axisymmetric problems for bodies made of non-linearly elastic incompressible materials are analysed for large deformations. In the case of problems of the axisymmetric plane deformation of cylindrical bodies, the lack of uniqueness of the solution for a given follower load in the case of a Bartenev–Khazanovich material and the existence of a limiting load in the case of a Treloar (neo-Hookian) material have been studied in detail and the dependences of the limiting load on the ratio of the external and internal radii of a hollow cylinder in the undeformed state have been presented. A similar study has been carried out for constitutive relations of a special form that well describe the properties of rubber. For this material, the lack of uniqueness of the solution is revealed for fairly high loads. The axisymmetric problem of the plane stress state of a circular ring made of a Bartenev–Khazanovich material has been solved and a lack of uniqueness of the solution for a given follower load was discovered in the case when the dimensions of the ring are given in the undeformed state. Similar studies have been carried out for Chernykh and Treloar materials in the case of the problem of the radially symmetric deformation of a spherical shell. It was established that, in the case of a Chernykh material, the lack of uniqueness of the solution depends considerably on the constant characterizing the physical non-linearity. The limit case of the deformation of a spherical cavity in an infinitely extended body has been investigated. The effect of an unbounded increase in the boundary stresses is observed for finite external loads, that appears in the case of the problem of the plane axisymmetric deformation of a cylindrical cavity in an infinitely extended body made of a Bartenev–Khazanovich material and in the case of the problem of the radially symmetric deformation of an infinitely extended body made of a Chernykh material with a spherical cavity.     

Multi-step methods for choosing the best set of variables in regression analysis

In a recent article (Konno and Yamamoto in ISE 07-01, Department of Industrial and Systems Engineering, Chuo University, February 2007), one of the authors formulated the problem of choosing the best set of explanatory variables from a large number of candidate variables in a linear regression model as a mixed 0–1 integer linear programming problem and showed that it can be solved by the state-of-the-art integer programming software.     

An exact procedure and LP formulations for the leader—follower location problem

The leader—follower location problem consists of determining an optimal strategy for two competing firms which make decisions sequentially. The leader optimisation problem is to minimise the maximum market share of the follower. The objective of the follower problem is to maximise its market share. We describe linear programming formulations for both problems and analyse the use of these formulations to solve the problems. We also propose an exact procedure based on an elimination process in a candidate list.