Linear models for the approximate solution of the problem of packing equal circles into a given domain

The linear models for the approximate solution of the problem of packing the maximum number of equal circles of the given radius into a given closed bounded domain G are proposed. We construct a grid in G; the nodes of this grid form a finite set of points T, and it is assumed that the centers of circles to be packed can be placed only at the points of T. The packing problems of equal circles with the centers at the points of T are reduced to 0–1 linear programming problems. A heuristic algorithm for solving the packing problems based on linear models is proposed. This algorithm makes it possible to solve packing problems for arbitrary connected closed bounded domains independently of their shape in a unified manner. Numerical results demonstrating the effectiveness of this approach are presented.     

A Note on a Packing Problem in Transitive Tournaments

Let TT_n be a transitive tournament on n vertices. We show that for any directed acyclic graph G of order n and of size not greater than two directed graphs isomorphic to G are arc disjoint subgraphs of TT_n. Moreover, this bound is generally the best possible. The research partially supported by KBN grant 2 P03A 016 18     

Solving the pickup and delivery problem with three-dimensional loading constraints and reloading ban

In this paper, we extend the classical Pickup and Delivery Problem (PDP) to an integrated routing and three-dimensional loading problem, called PDP with three-dimensional loading constraints (3L-PDP). We are given a set of requests and a homogeneous fleet of vehicles. A set of routes of minimum total length has to be determined such that each request is transported from a loading site to the corresponding unloading site. In the 3L-PDP, each request is given as set of rectangular boxes and the vehicle capacity is replaced by a 3D loading space.This paper is the second one in a series of articles on 3L-PDP. As in the first paper we are dealing with constraints which guarantee that no reloading effort will occur. Here the focus is laid on the reloading ban, a packing constraint that ensures identical placements of same boxes in different packing plans. The reloading ban allows for better solutions in terms of travel distance than a routing constraint that was used in the first paper to preclude any reloading effort. To implement this packing constraint a new type of packing procedure is needed that is capable to generate a series of interrelated packing plans per route. This packing procedure, designed as tree search algorithm, and the corresponding concept of packing checks is the main contribution of the paper at hand. The packing procedure and a large neighborhood search procedure for routing form a hybrid algorithm for the 3L-PDP. Computational experiments were performed using 54 3L-PDP benchmark instances.     

Packing edge-disjoint cycles in graphs and the cyclomatic number

For a graph G let μ(G) denote the cyclomatic number and let ν(G) denote the maximum number of edge-disjoint cycles of G.We prove that for every k≥0 there is a finite set P(k) such that every 2-connected graph G for which μ(G)−ν(G)=k arises by applying a simple extension rule to a graph in P(k). Furthermore, we determine P(k) for k≤2 exactly.     

完备格上基于Sup-T合成算子的矩阵的平方根

对于完备格L上给定的|I|×|I|的矩阵R,若存在|I|×|I|的L上的矩阵S满足S⊙S=R,则称S为R的平方根,其中I表示指标集|I|的基数,⊙在本文中指的是sup-T合成算子并且T是无限∨分配的保序的算子。本文给出了完备格上基于sup-T合成算子的矩阵平方根存在的充要条件以及相应的理论上的算法求解所有的平方根。     

Numerical solution of the generalized Stokes problem for the flow in a channel

In this article we introduce the separation of variables in the two-dimensional generalized Stokes problem. −νΔu + αu + inverted delta p = f, for the flow in a channel. Also for the first time, we discuss the implementation of the Incremental Unknowns Method with a data structure of Compressed Column Storage. Two examples of application of the Incremental Unknowns method for this problem are presented in which we compare the CPU times of three methods: Conjugate Gradient (CG), Incremental Unknowns (IU), and Uzawa Algorithm (Uzawa). © 1997 John Wiley & Sons, Inc.     

Completeness of the Floquet solutions to the problem of a solid oscillating in a fluid

We prove the completeness of the Floquet solutions to the parabolic equation describing small oscillations of a fluid-solid system. The symmetry axis of the solid is fixed inside a container of an arbitrary shape which is filled with an incompressible viscous fluid. The solid oscillates torsionally under the action of an elastic force with time periodic rigidity.     

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

Sequential heuristic for the two-dimensional bin-packing problem

A heuristic approach for the two-dimensional bin-packing problem is proposed. The algorithm is based on the sequential heuristic procedure that generates each pattern to produce some items and repeats until all items are produced. Both guillotine and non-guillotine patterns can be used. Each pattern is obtained from calling a pattern-generation procedure, where the objective is to maximize the pattern value. The item values are adjusted after the generation of each pattern using a value correction formula. The algorithm is compared with five published algorithms, using 50 groups of benchmark instances. The results indicate that the algorithm is the most efficient in improving solution quality.     

Valid inequalities and branch-and-cut for the clique pricing problem

Motivated by an application in highway pricing, we consider the problem that consists in setting profit-maximizing tolls on a clique subset of a multicommodity transportation network. We formulate the problem as a linear mixed integer program and propose strong valid inequalities, some of which define facets of the two-commodity polyhedron. The numerical efficiency of these inequalities is assessed by embedding them within a branch-and-cut framework.     

Stokes’ first problem for Sisko fluid over a porous wall

We investigate the time-dependent flow of an incompressible Sisko fluid over a wall with suction or blowing. The flow is caused by sudden motion of the wall in its own plane. The magnetodynamic nature of the fluid is taken into account by applying a variable magnetic field. The resulting nonlinear problem is solved by invoking a symmetry approach and numerical techniques. The essential features of the embedded key parameters are described. Particularly the significance of the rheological effects is studied.     

An exact depth-first algorithm for the pallet loading problem

This paper proposes a fast exact algorithm to solve the Pallet Loading Problem (PLP) using depth-first strategy. A new concept called Maximal Breadth Filling Sequence (MBFS) is introduced to bring down the size of the search tree. The algorithm makes use of two pruning rules — lower-bound pruning and state-dominance pruning. Although depth-first search, by itself, requires very little memory, the dominance pruning rule makes effective utilization of the available memory. For large problems, more the memory available, more effective is the dominance pruning. The algorithm has been tested on standard problem sets. It has been found to be quite fast in outputting optimal solutions. Empirical findings are given in detail.     

A non-homogeneous boundary-value problem for the Korteweg-de Vries equation in a quarter plane

The Korteweg-de Vries equation was first derived by Boussinesq and Korteweg and de Vries as a model for long-crested small-amplitude long waves propagating on the surface of water. The same partial differential equation has since arisen as a model for unidirectional propagation of waves in a variety of physical systems. In mathematical studies, consideration has been given principally to pure initial-value problems where the wave profile is imagined to be determined everywhere at a given instant of time and the corresponding solution models the further wave motion. The practical, quantitative use of the Korteweg-de Vries equation and its relatives does not always involve the pure initial-value problem. Instead, initial-boundary-value problems often come to the fore. A natural example arises when modeling the effect in a channel of a wave maker mounted at one end, or in modeling near-shore zone motions generated by waves propagating from deep water. Indeed, the initial-boundary-value problem

studied here arises naturally as a model whenever waves determined at an entry point propagate into a patch of a medium for which disturbances are governed approximately by the Korteweg-de Vries equation. The present essay improves upon earlier work on (0.1) by making use of modern methods for the study of nonlinear dispersive wave equations. Speaking technically, local well-posedness is obtained for initial data in the class for \frac34$"> and boundary data in , whereas global well-posedness is shown to hold for when , and for when . In addition, it is shown that the correspondence that associates to initial data and boundary data the unique solution of (0.1) is analytic. This implies, for example, that solutions may be approximated arbitrarily well by solving a finite number of linear problems.

     

Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem

Bin-oriented heuristics for one-dimensional bin-packing problem construct solutions by packing one bin at a time. Several such heuristics consider two or more subsets for each bin and pack the one with the largest total weight. These heuristics sometimes generate poor solutions, due to a tendency to use many small items early in the process. To address this problem, we propose a method of controlling the average weight of items packed by bin-oriented heuristics. Constructive heuristics and an improvement heuristic based on this approach are introduced. Additionally, reduction methods for bin-oriented heuristics are presented. The results of an extensive computational study show that: (1) controlling average weight significantly improves solutions and reduces computation time of bin-oriented heuristics; (2) reduction methods improve solutions and processing times of some bin-oriented heuristics; and (3) the new improvement heuristic outperforms all other known complex heuristics, in terms of both average solution quality and computation time.     

Packing algorithms for arborescences (and spanning trees) in capacitated graphs

In a digraph with real-valued edge capacities, we pack the greatest number of arborescences in time O(n ³m log(n ²/m)); the packing uses at mostm distinct arborescences. Heren andm denote the number of vertices and edges in the given graph, respectively. Similar results hold for integral packing: we pack the greatest number of arborescences in time O(min{n, logN}n ²m log(n ²/)) using at mostm + n – 2 distinct arborescences; hereN denotes the largest (integral) capacity of an edge. These resuts improve the best previous bounds for capacitated digraphs. The algorithm extends to several related problems, including packing spanning trees in an undirected capacitated graph, and covering such graphs by forests. The algorithm provides a new proof of Edmonds' theorem for arborescence packing, for both integral and real capacities, based on a laminar family of sets derived from the packing. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

A two-stage intelligent search algorithm for the two-dimensional strip packing problem

This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. In the first stage, a heuristic algorithm is proposed, which is based on a simple scoring rule that selects one rectangle from all rectangles to be packed, for a given space. In the second stage, a local search and a simulated annealing algorithm are combined to improve solutions of the problem. In particular, a multi-start strategy is designed to enhance the search capability of the simulated annealing algorithm. Extensive computational experiments on a wide range of benchmark problems from zero-waste to non-zero-waste instances are implemented. Computational results obtained in less than 60 seconds of computation time show that the proposed algorithm outperforms the supposedly excellent algorithms reported recently, on average. It performs particularly better for large instances.