Some computational results on real 0–1 knapsack problems

The most recent algorithms to solve binary knapsack problems employ Lagrangean based reduction schemes to fix on or off a significant portion of the variables. This paper points out that, on hard problems encountered in practice, the repeated. application of an LP-based reduction on the pivot variable can greatly shorten solution times     

Duchon–Robert solutions for the Rayleigh–Taylor and Muskat problems

We construct analytic solutions to the Euler equations with an interface between two fluids, extending work of Duchon and Robert. We also show that the estimates of Duchon and Robert yield global analytic solutions to the Muskat problem with small initial data.     

Wine and maths: mathematical solutions to wine–inspired problems

We deal with an application of partial differential equations to the correct definition of a wine cellar. We present some historical details about this problem. We also discuss how to build or renew a wine cellar, creating ideal conditions for the ageing process and improving the quality of wines. Our goal is to calculate the optimal depth z₀ of a wine cellar in order to attenuate the periodic temperature fluctuations. What follows is a kind of survey of wine-related and optimization problems which have been solved by means of powerful math tools.     

Max–max,max–min,min–max and min–min knapsack problems with a parametric constraint

4OR - Max–max, max–min, min–max and min–min optimization problems with a knapsack-type constraint containing a single numerical parameter are studied. The goal is to present...     

Local search metaheuristics for discrete–continuous scheduling problems

Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource are considered. For each job there are known: its processing speed as a continuous, concave function of a continuous resource allotted at a time and its processing demand. The optimization criterion is the schedule length. The problem can be decomposed into two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to find an optimal (continuous) resource allocation among jobs already sequenced. Problem (ii) can be formulated as a convex programming problem with linear constraints and solved using proper solvers. Thus, the problem remains to generate a set of all feasible sequences of jobs on machines (this guarantees finding an optimal schedule in the general case). However, the cardinality of this set grows exponentially with the number of jobs. Thus, we propose to use heuristic search methods defined on the space of feasible sequences. Three metaheuristics: tabu search (TS), simulated annealing (SA) and genetic algorithm (GA) have been implemented and compared computationally with a random sampling technique. The computational experiment has been carried out on an SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out.     

Tabu search for discrete–continuous scheduling problems with heuristic continuous resource allocation

Problems of scheduling non-preemptable, independent jobs on parallel identical machines under an additional continuous renewable resource to minimize the makespan are considered. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. The processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. A heuristic procedure for allocating the continuous resource is used. The tabu search metaheuristic to solve the considered problem is presented. The results produced by tabu search are compared with optimal solutions for small instances, as well as with the results generated by simple search methods – multi-start iterative improvement and random sampling for larger instances.     

Wavelet–Galerkin solutions of one dimensional elliptic problems

Daubechies wavelet bases are used for numerical solution of partial differential equations of one dimension by Galerkin method. Galerkin bases are constructed from Daubechies functions which are compactly supported and which constitute an orthonormal basis of L²(R)$L^2(\mathbb{R})$. Theoretical and numerical results are obtained for elliptic problems of second order with different types of boundary conditions. Optimal error estimates are also obtained. Comparison of solutions with simple finite difference method suggests that for this class of problems, the present method will provide a better alternative to other classical methods. The methodology can be generalized to multidimensional problems by taking care of some technical facts.     

Computation of eigenvalues and solutions of regular Sturm–Liouville problems using Haar wavelets

The paper presents a novel method for the computation of eigenvalues and solutions of Sturm–Liouville eigenvalue problems (SLEPs) using truncated Haar wavelet series. This is an extension of the technique proposed by Hsiao to solve discretized version of variational problems via Haar wavelets. The proposed method aims to cover a wider class of problems, by applying it to historically important and a very useful class of boundary value problems, thereby enhancing its applicability. To demonstrate the effectiveness and efficiency of the method various celebrated Sturm–Liouville problems are analyzed for their eigenvalues and solutions. Also, eigensystems are investigated for their asymptotic and oscillatory behavior. The proposed scheme, unlike the conventional numerical schemes, such as Rayleigh quotient and Rayleigh–Ritz approximation, gives eigenpairs simultaneously and provides upper and lower estimates of the smallest eigenvalue, and it is found to have quadratic convergence with increase in resolution.     

Comment on ‘some computational results on real 0–1 knapsack problems’

A logical test used in some knapsack algorithms was recently described in this journal as erroneous. We show that the test is correct.     

Periodic solutions of “predator–prey” systems with continuous delay and periodic coefficients

We prove the existence of positive ω-periodic solutions for some “predator–prey” systems with continuous delay of the argument for the case where the parameters of these systems are specified by ω-periodic continuous positive functions.     

Optimized Runge–Kutta pairs for problems with oscillating solutions

Three types of methods for integrating periodic initial value problems are presented. These methods are (i) phase-fitted, (ii) zero dissipation (iii) both zero dissipative and phase fitted. Some particular modifications of well-known explicit Runge–Kutta pairs of orders five and four are constructed. Numerical experiments show the efficiency of the new pairs in a wide range of oscillatory problems.     

Classical solutions of many-dimensional elliptic–parabolic free boundary problems

We consider a free boundary problem modeling fluid flow in a partially saturated porous media. In that context an unknown function represents the pressure and satisfies an elliptic equation in the saturated domain and a quasilinear parabolic equation in the unsaturated domain. The principal part of this work is the investigation of the smoothness properties of an unknown (free) boundary between domains of ellipticity and parabolicity.      

Property of positive solutions and its applications for Sturm–Liouville singular boundary value problems

This paper is concerned with the property of the positive solutions for Sturm–Liouville singular boundary value problems with the linear conditions. We obtain a relation between the solutions and Green’s function. It implies a necessary condition for the C¹[0,1]$C^1[0,1]$ positive solutions. We apply the result to conclude that the given equation has no C¹[0,1]$C^1[0,1]$ positive solutions.     

Approximate solutions of the Kuramoto–Sivashinsky equation for periodic boundary value problems and chaos

An approach to find approximate solutions of the Kuramoto–Sivashinsky (KS) equation for boundary value problems (BVP) is developed. Attention is focused to periodic boundary value problems. This approach is used to find the approximate solutions for stress-free and rigid boundary conditions. In the first case, it is shown that the spatial pattern of the solutions fluctuates chaotically for small times. But it becomes asymptotically regular. The time-averaged solutions are also regular. In contrast, the solution for rigid boundary conditions exhibit robust chaos.     

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.     

A Newton’s method for the continuous quadratic knapsack problem

We introduce a new efficient method to solve the continuous quadratic knapsack problem. This is a highly structured quadratic program that appears in different contexts. The method converges after $O(n)$ iterations with overall arithmetic complexity $O(n^2)$ . Numerical experiments show that in practice the method converges in a small number of iterations with overall linear complexity, and is faster than the state-of-the-art algorithms based on median finding, variable fixing, and secant techniques.     

Multi-marginal Monge–Kantorovich transport problems: A characterization of solutions

We shall present a measure theoretical approach that, together with the Kantorovich duality, provides an efficient tool to study the optimal transport problem. Specifically, we study the support of optimal plans where the cost function does not satisfy the classical twist condition in the two marginal problem as well as in the multi-marginal case when twistedness is limited to certain subsets.