The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort. (C) 2011 Elsevier BM. All rights reserved.

Numerical solution of the PTT constitutive equation for unsteady three-dimensional free surface flows

This work deals with the development of a numerical technique for simulating three-dimensional viscoelastic free surface flows using the PTT (Phan-Thien-Tanner) nonlinear constitutive equation. In particular, we are interested in flows possessing moving free surfaces. The equations describing the numerical technique are solved by the finite difference method on a staggered grid. The fluid is modelled by a Marker-and-Cell type method and an accurate representation of the fluid surface is employed. The full free surface stress conditions are considered. The PTT equation is solved by a high order method, which requires the calculation of the extra-stress tensor on the mesh contours. To validate the numerical technique developed in this work flow predictions for fully developed pipe flow are compared with an analytic solution from the literature. Then, results of complex free surface flows using the FIT equation such as the transient extrudate swell problem and a jet flowing onto a rigid plate are presented. An investigation of the effects of the parameters epsilon and xi on the extrudate swell and jet buckling problems is reported. (C) 2010 Elsevier B.V. All rights reserved.

Heat Conduction Equation Solution in the Presence of a Change of State in a Bounded Axisymmetric Cylindrical Domain

The heat conduction problem, in the presence of a change of state, was solved for the case of an indefinitely long cylindrical layer cavity. As boundary conditions, it is imposed that the internal surface of the cavity is maintained below the fusion temperature of the infilling substance and the external surface is kept above it. The solution, obtained in nondimensional variables, consists in two closed form heat conduction equation solutions for the solidified and liquid regions, which formally depend of the, at first, unknown position of the phase change front. The energy balance through the phase change front furnishes the equation for time dependence of the front position, which is numerically solved. Substitution of the front position for a particular instant in the heat conduction equation solutions gives the temperature distribution inside the cavity at that moment. The solution is illustrated with numerical examples. [DOI: 10.1115/1.4003542]

Dynamics in dumbbell domains II. The limiting problem

In this work we continue the analysis of the asymptotic dynamics of reaction-diffusion problems in a dumbbell domain started in [J.M. Arrieta, AN Carvalho, G. Lozada-Cruz, Dynamics in dumbbell domains I. Continuity of the set of equilibria, J. Differential Equations 231 (2) (2006) 551-597]. Here we study the limiting problem, that is, an evolution problem in a ""domain"" which consists of an open, bounded and smooth set Omega subset of R(N) with a curve R(0) attached to it. The evolution in both parts of the domain is governed by a parabolic equation. In Omega the evolution is independent of the evolution in R(0) whereas in R(0) the evolution depends on the evolution in Omega through the continuity condition of the solution at the junction points. We analyze in detail the linear elliptic and parabolic problem, the generation of linear and nonlinear semigroups, the existence and structure of attractors. (C) 2009 Elsevier Inc. All rights reserved.

On the cutting stock problem under stochastic demand

This paper addresses the one-dimensional cutting stock problem when demand is a random variable. The problem is formulated as a two-stage stochastic nonlinear program with recourse. The first stage decision variables are the number of objects to be cut according to a cutting pattern. The second stage decision variables are the number of holding or backordering items due to the decisions made in the first stage. The problem`s objective is to minimize the total expected cost incurred in both stages, due to waste and holding or backordering penalties. A Simplex-based method with column generation is proposed for solving a linear relaxation of the resulting optimization problem. The proposed method is evaluated by using two well-known measures of uncertainty effects in stochastic programming: the value of stochastic solution-VSS-and the expected value of perfect information-EVPI. The optimal two-stage solution is shown to be more effective than the alternative wait-and-see and expected value approaches, even under small variations in the parameters of the problem.

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests. (C) 2009 Elsevier B.V. All rights reserved.

An approach for solving the lot-sizing problem of a market-driven foundry

Foundries can be found all over Brazil and they are very important to its economy. In 2008, a mixed integer-programming model for small market-driven foundries was published, attempting to minimize delivery delays. We undertook a study of that model. Here, we present a new approach based on the decomposition of the problem into two sub-problems: production planning of alloys and production planning of items. Both sub-problems are solved using a Lagrangian heuristic based on transferences. An important aspect of the proposed heuristic is its ability to take into account a secondary practice objective solution: the furnace waste. Computational tests show that the approach proposed here is able to generate good quality solutions that outperform prior results. Journal of the Operational Research Society (2010) 61, 108-114. doi:10.1057/jors.2008.151

Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths

This paper deals with the classical one-dimensional integer cutting stock problem, which consists of cutting a set of available stock lengths in order to produce smaller ordered items. This process is carried out in order to optimize a given objective function (e.g., minimizing waste). Our study deals with a case in which there are several stock lengths available in limited quantities. Moreover, we have focused on problems of low demand. Some heuristic methods are proposed in order to obtain an integer solution and compared with others. The heuristic methods are empirically analyzed by solving a set of randomly generated instances and a set of instances from the literature. Concerning the latter. most of the optimal solutions of these instances are known, therefore it was possible to compare the solutions. The proposed methods presented very small objective function value gaps. (C) 2008 Elsevier Ltd. All rights reserved.

Evaluation of a bounded high order upwind scheme for 3D incompressible free surface flow computations

fit the context of normalized variable formulation (NVF) of Leonard and total variation diminishing (TVD) constraints of Harten. this paper presents an extension of it previous work by the authors for solving unsteady incompressible flow problems. The main contributions of the paper are threefold. First, it presents the results of the development and implementation of a bounded high order upwind adaptative QUICKEST scheme in the 3D robust code (Freeflow), for the numerical solution of the full incompressible Navier-Stokes equations. Second, it reports numerical simulation results for 1D hock tube problem, 2D impinging jet and 2D/3D broken clam flows. Furthermore, these results are compared with existing analytical and experimental data. And third, it presents the application of the numerical method for solving 3D free surface flow problems. (C) 2007 IMACS. Published by Elsevier B.V. All rights reserved,

Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints

This article describes and compares three heuristics for a variant of the Steiner tree problem with revenues, which includes budget and hop constraints. First, a greedy method which obtains good approximations in short computational times is proposed. This initial solution is then improved by means of a destroy-and-repair method or a tabu search algorithm. Computational results compare the three methods in terms of accuracy and speed. (C) 2007 Elsevier B.V. All rights reserved.

Combining structure and dynamics: non-denaturing high-pressure effect on lysozyme in solution

Small-angle X-ray scattering (SAXS) and elastic and quasi-elastic neutron scattering techniques were used to investigate the high-pressure-induced changes on interactions, the low-resolution structure and the dynamics of lysozyme in solution. SAXS data, analysed using a global-fit procedure based on a new approach for hydrated protein form factor description, indicate that lysozyme completely maintains its globular structure up to 1500 bar, but significant modi. cations in the protein-protein interaction potential occur at approximately 600-1000 bar. Moreover, the mass density of the protein hydration water shows a clear discontinuity within this pressure range. Neutron scattering experiments indicate that the global and the local lysozyme dynamics change at a similar threshold pressure. A clear evolution of the internal protein dynamics from diffusing to more localized motions has also been probed. Protein structure and dynamics results have then been discussed in the context of protein-water interface and hydration water dynamics. According to SAXS results, the new configuration of water in the first hydration layer induced by pressure is suggested to be at the origin of the observed local mobility changes.

Self-adjoint extensions and spectral analysis in the Calogero problem

In this paper, we present a mathematically rigorous quantum-mechanical treatment of a one-dimensional motion of a particle in the Calogero potential alpha x(-2). Although the problem is quite old and well studied, we believe that our consideration based on a uniform approach to constructing a correct quantum-mechanical description for systems with singular potentials and/or boundaries, proposed in our previous works, adds some new points to its solution. To demonstrate that a consideration of the Calogero problem requires mathematical accuracy, we discuss some `paradoxes` inherent in the `naive` quantum-mechanical treatment. Using a self-adjoint extension method, we construct and study all possible self-adjoint operators (self-adjoint Hamiltonians) associated with a formal differential expression for the Calogero Hamiltonian. In particular, we discuss a spontaneous scale-symmetry breaking associated with self-adjoint extensions. A complete spectral analysis of all self-adjoint Hamiltonians is presented.

Coherent states of a particle in a magnetic field and the Stieltjes moment problem

A solution to a version of the Stieltjes moment. problem is presented. Using this solution, we construct a family of coherent states of a charged particle in a uniform magnetic field. We prove that these states form an overcomplete set that is normalized and resolves the unity. By the help of these coherent states we construct the Fock-Bergmann representation related to the particle quantization. This quantization procedure takes into account a circle topology of the classical motion. (C) 2009 Elsevier B.V. All rights reserved.

Phototransformation of hematoporphyrin in aqueous solution: Anomalous behavior at low oxygen concentration

The photoactivation of a photosensitizer is the initial step in photodynamic therapy (PDT) where photochemical reactions result in the production of reactive oxygen species and eventually cell death. In addition to oxidizing biomolecules, some of these photochemical reactions lead to photosensitizer degradation at a rate dependent on the oxygen concentration among other factors. We investigated photodegradation of Photogem A (R) (28 mu M), a hematoporphyrin derivative, at different oxygen concentrations (9.4 to 625.0 mu M) in aqueous solution. The degradation was monitored by fluorescence spectroscopy. The degradation rate (M/s) increases as the oxygen concentration increases when the molar ratio of oxygen to PhotogemA (R) is greater than 1. At lower oxygen concentrations (< 25 mu M) an inversion of this behavior was observed. The data do not fit a simple kinetic model of first-order dependence on oxygen concentration. This inversion of the degradation rate at low oxygen concentration has not previously been demonstrated and highlights the relationship between photosensitizer and oxygen concentrations in determining the photobleaching mechanism(s). The findings demonstrate that current models for photobleaching are insufficient to explain completely the effects at low oxygen concentration.

ON THE SUPERCRITICALITY OF THE FIRST HOPF BIFURCATION IN A DELAY BOUNDARY PROBLEM

The goal of this paper is to analyze the character of the first Hopf bifurcation (subcritical versus supercritical) that appears in a one-dimensional reaction-diffusion equation with nonlinear boundary conditions of logistic type with delay. We showed in the previous work [Arrieta et al., 2010] that if the delay is small, the unique non-negative equilibrium solution is asymptotically stable. We also showed that, as the delay increases and crosses certain critical value, this equilibrium becomes unstable and undergoes a Hopf bifurcation. This bifurcation is the first one of a cascade occurring as the delay goes to infinity. The structure of this cascade will depend on the parameters appearing in the equation. In this paper, we show that the first bifurcation that occurs is supercritical, that is, when the parameter is bigger than the delay bifurcation value, stable periodic orbits branch off from the constant equilibrium.