A branch-and-price approach to p-median location problems

This paper describes a branch-and-price algorithm for the p-median location problem. The objective is to locate p facilities (medians) such as the sum of the distances from each demand point to its nearest facility is minimized. The traditional column generation process is compared with a stabilized approach that combines the column generation and Lagrangean/surrogate relaxation. The Lagrangean/surrogate multiplier modifies; the reduced cost criterion, providing the selection of new productive columns at the search tree. Computational experiments are conducted considering especially difficult instances to the traditional column generation and also with some large-scale instances. (C) 2004 Elsevier Ltd. All rights reserved.

Insights into metal ion binding in phospholipases A(2): ultra high-resolution crystal structures of an acidic phospholipase A(2) in the Ca2+ free and bound states

The electrophile Ca2+ is an essential multifunctional co-factor in the phospholipase A(2) mediated hydrolysis of phospholipids. Crystal structures of an acidic phospholipase A(2) from the venom of Bothrops jararacussu have been determined both in the Ca2+ free and bound states at 0.97 and 1.60 angstrom resolutions, respectively. In the Ca2+ bound state, the Ca2+ ion is penta-coordinated by a distorted pyramidal cage of oxygen and nitrogen atoms that is significantly different to that observed in structures of other Group I/II phospholipases A(2). In the absence of Ca2+, a water molecule occupies the position of the Ca2+ ion and the side chain of Asp49 and the calcium-binding loop adopts a different conformation. (c) 2005 Elsevier SAS. All rights reserved.

Soluble and bound peroxidases from papaya fruit

Soluble and bound peroxidases were isolated from the pulp of ripening papaya fruit. During papaya ripening, soluble and bound peroxidase activities increased 2.5- and 4.2-fold, respectively. Soluble peroxidase was purified 59-fold by ammonium sulphate precipitation and chromatography on Sephadex G-25, DEAE-cellulose and Sephadex G-100. Bound peroxidase was purified 140-fold by ammonium sulphate precipitation and chromatography on Sephadex G-100 and DEAE-cellulose. Polyacrylamide gel electrophoresis of the purified preparations revealed that both enzymes were highly purified by the procedures adopted. The soluble and bound forms had a Mr of 41 000 and 54 000, respectively. Soluble and bound peroxidases showed optimum activity at pH 6.0 and 5.5, respectively, and were inhibited by p-chloromercuribenzoate, iodoacetamide, N-ethylmaleimide, potassium cyanide and Fe2+. Soluble peroxidase was activated by ammonium sulphate and this activation was prevented by cyanide. © 1990.

Scattering and bound states of fermions in a mixed vector-scalar smooth step potential

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Scattering and bound states of fermions in the modified Hulthen potential

In the present work the scattering of a fermion in the modified Hulthen potential is considered with a general vector and scalar and we solved the Dirac equation in the one-dimensional space. The transmission and reflection coefficients are reported. The bound-state solution is also given. The study shows the asymptotic behavior of the wave function in bound-state and scattering states solutions.

A matheuristic for the selection of beam directions and dose distribution in radiotherapy planning

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Uma nova abordagem branch and cut aplicada ao problema de planejamento da expansão de redes de transmissão de grande porte

Neste artigo propomos um algoritmo branch and cut com novas inequações específicas ao problema de planejamento da expansão de redes de transmissão de energia elétrica. Todas as inequações propostas neste trabalho são válidas tanto para os modelos lineares como para os modelos não lineares do problema. Os testes computacionais têm mostrado a eficiência do método proposto neste trabalho quando aplicado a subsistemas reais brasileiros e ao sistema colombiano.

Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Efficient certification of feasibility and objective value of linear programs and its applications

The use of linear programming in various areas has increased with the significant improvement of specialized solvers. Linear programs are used as such to model practical problems, or as subroutines in algorithms such as formal proofs or branch-and-cut frameworks. In many situations a certified answer is needed, for example the guarantee that the linear program is feasible or infeasible, or a provably safe bound on its objective value. Most of the available solvers work with floating-point arithmetic and are thus subject to its shortcomings such as rounding errors or underflow, therefore they can deliver incorrect answers. While adequate for some applications, this is unacceptable for critical applications like flight controlling or nuclear plant management due to the potential catastrophic consequences. We propose a method that gives a certified answer whether a linear program is feasible or infeasible, or returns unknown'. The advantage of our method is that it is reasonably fast and rarely answers unknown'. It works by computing a safe solution that is in some way the best possible in the relative interior of the feasible set. To certify the relative interior, we employ exact arithmetic, whose use is nevertheless limited in general to critical places, allowing us to rnremain computationally efficient. Moreover, when certain conditions are fulfilled, our method is able to deliver a provable bound on the objective value of the linear program. We test our algorithm on typical benchmark sets and obtain higher rates of success compared to previous approaches for this problem, while keeping the running times acceptably small. The computed objective value bounds are in most of the cases very close to the known exact objective values. We prove the usability of the method we developed by additionally employing a variant of it in a different scenario, namely to improve the results of a Satisfiability Modulo Theories solver. Our method is used as a black box in the nodes of a branch-and-bound tree to implement conflict learning based on the certificate of infeasibility for linear programs consisting of subsets of linear constraints. The generated conflict clauses are in general small and give good rnprospects for reducing the search space. Compared to other methods we obtain significant improvements in the running time, especially on the large instances.

Scheduling of continuous and discontinuous material flows with intermediate storage restrictions

This paper deals with scheduling batch (i.e., discontinuous), continuous, and semicontinuous production in process industries (e.g., chemical, pharmaceutical, or metal casting industries) where intermediate storage facilities and renewable resources (processing units and manpower) of limited capacity have to be observed. First, different storage configurations typical of process industries are discussed. Second, a basic scheduling problem covering the three above production modes is presented. Third, (exact and truncated) branch-and-bound methods for the basic scheduling problem and the special case of batch scheduling are proposed and subjected to an experimental performance analysis. The solution approach presented is flexible and in principle simple, and it can (approximately) solve relatively large problem instances with sufficient accuracy.

Scheduling the production of rolling ingots: Industrial context, model, and solution method

We study a real-world scheduling problem arising in the context of a rolling ingots production. First we review the production process and discuss peculiarities that have to be observed when scheduling a given set of production orders on the production facilities. We then show how to model this scheduling problem using prescribed time lags between operations, different kinds of resources, and sequence-dependent changeovers. A branch-and-bound solution procedure is presented in the second part. The basic principle is to relax the resource constraints by assuming infinite resource availability. Resulting resource conflicts are then stepwise resolved by introducing precedence relationships among operations competing for the same resources. The algorithm has been implemented as a beam search heuristic enumerating alternative sets of precedence relationships.

Patient classification system: An integrated method for measuring nursing intensity and optimizing resource allocation

A patient classification system was developed integrating a patient acuity instrument with a computerized nursing distribution method based on a linear programming model. The system was designed for real-time measurement of patient acuity (workload) and allocation of nursing personnel to optimize the utilization of resources.^ The acuity instrument was a prototype tool with eight categories of patients defined by patient severity and nursing intensity parameters. From this tool, the demand for nursing care was defined in patient points with one point equal to one hour of RN time. Validity and reliability of the instrument was determined as follows: (1) Content validity by a panel of expert nurses; (2) predictive validity through a paired t-test analysis of preshift and postshift categorization of patients; (3) initial reliability by a one month pilot of the instrument in a practice setting; and (4) interrater reliability by the Kappa statistic.^ The nursing distribution system was a linear programming model using a branch and bound technique for obtaining integer solutions. The objective function was to minimize the total number of nursing personnel used by optimally assigning the staff to meet the acuity needs of the units. A penalty weight was used as a coefficient of the objective function variables to define priorities for allocation of staff.^ The demand constraints were requirements to meet the total acuity points needed for each unit and to have a minimum number of RNs on each unit. Supply constraints were: (1) total availability of each type of staff and the value of that staff member (value was determined relative to that type of staff's ability to perform the job function of an RN (i.e., value for eight hours RN = 8 points, LVN = 6 points); (2) number of personnel available for floating between units.^ The capability of the model to assign staff quantitatively and qualitatively equal to the manual method was established by a thirty day comparison. Sensitivity testing demonstrated appropriate adjustment of the optimal solution to changes in penalty coefficients in the objective function and to acuity totals in the demand constraints.^ Further investigation of the model documented: correct adjustment of assignments in response to staff value changes; and cost minimization by an addition of a dollar coefficient to the objective function. ^

Investigation of retinal morphology alterations using spectral domain optical coherence tomography in a mouse model of retinal branch and central retinal vein occlusion.

Retinal vein occlusion is a leading cause of visual impairment. Experimental models of this condition based on laser photocoagulation of retinal veins have been described and extensively exploited in mammals and larger rodents such as the rat. However, few reports exist on the use of this paradigm in the mouse. The objective of this study was to investigate a model of branch and central retinal vein occlusion in the mouse and characterize in vivo longitudinal retinal morphology alterations using spectral domain optical coherence tomography. Retinal veins were experimentally occluded using laser photocoagulation after intravenous application of Rose Bengal, a photo-activator dye enhancing thrombus formation. Depending on the number of veins occluded, variable amounts of capillary dropout were seen on fluorescein angiography. Vascular endothelial growth factor levels were markedly elevated early and peaked at day one. Retinal thickness measurements with spectral domain optical coherence tomography showed significant swelling (p<0.001) compared to baseline, followed by gradual thinning plateauing two weeks after the experimental intervention (p<0.001). Histological findings at day seven correlated with spectral domain optical coherence tomography imaging. The inner layers were predominantly affected by degeneration with the outer nuclear layer and the photoreceptor outer segments largely preserved. The application of this retinal vein occlusion model in the mouse carries several advantages over its use in other larger species, such as access to a vast range of genetically modified animals. Retinal changes after experimental retinal vein occlusion in this mouse model can be non-invasively quantified by spectral domain optical coherence tomography, and may be used to monitor effects of potential therapeutic interventions.

Associating optical measurements and estimating orbits of geocentric objects through population-based meta-heuristic methods

Currently several thousands of objects are being tracked in the MEO and GEO regions through optical means. The problem faced in this framework is that of Multiple Target Tracking (MTT). In this context both, the correct associations among the observations and the orbits of the objects have to be determined. The complexity of the MTT problem is defined by its dimension S. The number S corresponds to the number of fences involved in the problem. Each fence consists of a set of observations where each observation belongs to a different object. The S ≥ 3 MTT problem is an NP-hard combinatorial optimization problem. There are two general ways to solve this. One way is to seek the optimum solution, this can be achieved by applying a branch-and- bound algorithm. When using these algorithms the problem has to be greatly simplified to keep the computational cost at a reasonable level. Another option is to approximate the solution by using meta-heuristic methods. These methods aim to efficiently explore the different possible combinations so that a reasonable result can be obtained with a reasonable computational effort. To this end several population-based meta-heuristic methods are implemented and tested on simulated optical measurements. With the advent of improved sensors and a heightened interest in the problem of space debris, it is expected that the number of tracked objects will grow by an order of magnitude in the near future. This research aims to provide a method that can treat the correlation and orbit determination problems simultaneously, and is able to efficiently process large data sets with minimal manual intervention.