An exact algorithm for the type-constrained and variable sized bin packing problem

In this paper, we introduce an additional constraint to the one-dimensional variable sized bin packing problem. Practically, some of items have to be packed separately in different bins due to their specific requirement. Therefore, these items are labelled as different types. The bins can be used to pack either any type of items if they are empty originally or the same type of items as what they already have. We model the problem as a type-constrained and variable sized bin packing problem (TVSBPP), and solve it via a branch and bound method. An efficient backtracking procedure is proposed to improve the efficiency of the algorithm.     

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.     

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.     

A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing

The three-dimensional bin packing problem consists of packing a set of boxes into the minimum number of bins. In this paper we propose a new GRASP algorithm for solving three-dimensional bin packing problems which can also be directly applied to the two-dimensional case. The constructive phase is based on a maximal-space heuristic developed for the container loading problem. In the improvement phase, several new moves are designed and combined in a VND structure. The resulting hybrid GRASP/VND algorithm is simple and quite fast and the extensive computational results on test instances from the literature show that the quality of the solutions is equal to or better than that obtained by the best existing heuristic procedures.     

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.     

An improved multi-staged algorithmic process for the solution of the examination timetabling problem

The efficient creation of examination timetables is a recurring and important problem for universities worldwide. Good timetables typically are characterized by balanced distances between consecutive exams for all students. In this contribution an approach for the examination timetabling problem as defined in the second International Timetabling Competition () is presented. The solution approach is managed on the top level by GRASP (Greedy Randomized Adaptive Search Procedure) and it involves several optimization algorithms, heuristics and metaheuristics. A construction phase is executed first producing a relatively high quality feasible solution and an improvement phase follows that further ameliorates the produced timetable. Each phase consists of stages that are consumed in a circular fashion. The procedure produces feasible solutions for each dataset provided under the runtime limit imposed by the rules of the ITC07 competition. Results are presented and analyzed.     

Existence of a periodic solution for continuous and discrete periodic second-order equations with variable potentials

Green’s functions for new second-order periodic differential and difference equations with variable potentials are found, then used as kernels in integral operators to guarantee the existence of a positive periodic solution to continuous and discrete second-order periodic boundary value problems with periodic coefficient functions. A new version of the Leggett-Williams fixed point theorem is employed.     

Study of the Kepler��s conjecture: the problem of the closest packing

In the first and second parts the problem of the Kepler??s conjecture is reduced from a problem with an infinite number of parameters to a problem with a finite number of parameters. In the third part is it is shown that the latter problem can be solved by a numerical verification using only a finite number of computations. However that finite number remains large, even if modern computers can do it. The method of analysis is classical: to each sphere of an arbitrary packing is associated a corresponding large enough ??associated domain??, disjoint from all other similar domains, in the hope of obtaining an interesting upper limit of the space occupation coefficient. Many methods of association have been tried in the past and the new method presented in this study is complex, but very well adapted to the problem of interest.     

Numerical solution of the Cauchy problem for the Painlevé I and II equations

A numerical method for solving the Cauchy problem for the first and second Painlevé differential equations is proposed. The presence of movable poles of the solution is allowed. The positions of the poles are not a priori known and are determined in the process of solving the equation. The proposed method is based on the transition to an auxiliary system of differential equations in a neighborhood of a pole. The equations in this system and its solution have no singularities in either the pole or its neighborhood. Numerical results confirming the efficiency of this method are presented.     

On the existence and the uniqueness of the solution of a fluid–structure interaction scattering problem

The existence and uniqueness of the solution of a fluid–structure interaction problem is investigated. The proposed analysis distinguishes itself from previous studies by employing a weighted Sobolev space framework, the DtN operator properties, and the Fredholm theory. The proposed approach allows to extend the range of validity of the standard existence and uniqueness results to the case where the elastic scatterer is assumed to be only Lipschitz continuous, which is of more practical interest.     

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.     

An exact algorithm for the 0–1 linear knapsack problem with a single continuous variable

The 0–1 linear knapsack problem with a single continuous variable (KPC) is an extension of the binary knapsack problem (KP). It is an NP-hard problem. In this paper, we show that KPC can be reduced to KP and a pseudo-knapsack problem (PKP), which is similar to the traditional knapsack problem except that the profits of items may be non-positive, and the weight sum has two sided limits on capacity. We use the Dynamic Programming algorithm COMBO (Martello et al., Manag Sci 45(3):414–424, 1999) to solve KP, and modify the branch and bound method EXPKNAP (Pisinger, Eur J Oper Res 87:175–187, 1995) for KP to solve the PKP. Numerical experiments show the efficiency of our method.     

Tools of mathematical modeling of arbitrary object packing problems

The article reviews the concept of and further develops phi-functions (Φ-functions) as an efficient tool for mathematical modeling of two-dimensional geometric optimization problems, such as cutting and packing problems and covering problems. The properties of the phi-function technique and its relationship with Minkowski sums and the nofit polygon are discussed. We also describe the advantages of phi-functions over these approaches. A clear definition of the set of objects for which phi-functions may be derived is given and some exceptions are illustrated. A step by step procedure for deriving phi-functions illustrated with examples is provided including the case of continuous rotation.     

A comparison of problem decomposition techniques for the FAP

This paper proposes a problem decomposition approach to solve hard Frequency Assignment Problem instances with standard meta-heuristics. The proposed technique aims to divide the initial problem into a number of easier subproblems, solve them and then recompose the partial solutions into one of the original problem. We consider the COST-259 MI-FAP instances and other Cardiff University test problems in order to simulate larger and more realistic networks. For both benchmarks the standard implementations of meta-heuristics do not generally produce a satisfactory performance within reasonable times of execution. However, the decomposed assignment approach can improve their results, both in terms of solution quality and runtime.     

Linear algebra-based solution of the gambler’s ruin problem

In this paper, we derive the result of the classical gambler’s ruin problem using elementary linear algebra. Moreover, the pedagogical advantage of the derivation is briefly discussed.     

Numerical solution of the Cauchy problem for Painlevé III

We suggest a numerical method for solving the Cauchy problem for the third Painlevé equation. The solution of this problem is complicated by the fact that the unknown function can have movable singular points of the pole type, and in addition, the equation has a singularity at the points where the solution vanishes. The position of poles and zeros of the function is not given and is specified in the course of the solution. The method is based on the passage, in a neighborhood of these points, to an auxiliary system of differential equations for which the equation and the corresponding solution has no singularity in that neighborhood and at the pole or zero itself. We present the results of numerical experiments, which justify the efficiency of the suggested method.     

On the solution of the Gellerstedt problem for the Lavrent’ev-Bitsadze equation

We study the solvability of the Gellerstedt problem for the Lavrent??ev-Bitsadze equation under an inhomogeneous boundary condition on the half-circle of the ellipticity domain of the equation, homogeneous boundary conditions on external, internal, and parallel side characteristics of the hyperbolicity domain of the equation, and the transmission conditions on the type change line of the equation.     

Asymptotics at t→∞ of the solution of the Cauchy problem for the Landau-Lifshitz equation

Conclusions The formulas obtained in the present paper for the leading term in the asymptotic behavior of the solution of the Cauchy problem for the LL equation subject to the boundary conditions L₃1, x± describe the solitonless sector. The transition to the general case, which takes into account the presence in the solution of soliton formations, can be made on the basis solely of algebraic considerations that use the procedure of soliton dressing developed in [17, 18] for the LL equation. In particular, applying to the obtained asymptotic formulas the procedure for a dressing of domain wall type (see [17]), we arrive at formulas that describe the asymptotic solution of the Cauchy problem for the LL equation with boundary conditions of the form L₃±1, x±.Leningrad State University. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 76, No. 1, pp. 3–17, July, 1988.     

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.