Multistage Transmission Expansion Planning Considering Fixed Series Compensation Allocation

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

A hybrid method for the probabilistic maximal covering location-allocation problem

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

Minimizing the Number of Optical Amplifiers Needed to Support a Multi-Wavelength Optical LAN/MAN

Optical networks based on passive star couplers and employing wavelength-division multiplexing (WDhf) have been proposed for deployment in local and metropolitan areas. Amplifiers are required in such networks to compensate for the power losses due to splitting and attenuation. However, an optical amplifier has constraints on the maximum gain and the maximum output power it can supply; thus optical amplifier placement becomes a challenging problem. The general problem of minimizing the total amplifier count, subject to the device constraints, is a mixed-integer non-linear problem. Previous studies have attacked the amplifier placement problem by adding the “artificial” constraint that all wavelengths, which are present at a particular point in a fiber, be at the same power level. In this paper, we present a method to solve the minimum amplifier- placement problem while avoiding the equally powered- wavelength constraint. We demonstrate that, by allowing signals to operate at different power levels, our method can reduce the number of amplifiers required in several small to medium-sized networks.

Three time-based scale formulations for the two-stage lot sizing and scheduling in process industries

In this paper, we propose three novel mathematical models for the two-stage lot-sizing and scheduling problems present in many process industries. The problem shares a continuous or quasi-continuous production feature upstream and a discrete manufacturing feature downstream, which must be synchronized. Different time-based scale representations are discussed. The first formulation encompasses a discrete-time representation. The second one is a hybrid continuous-discrete model. The last formulation is based on a continuous-time model representation. Computational tests with state-of-the-art MIP solver show that the discrete-time representation provides better feasible solutions in short running time. On the other hand, the hybrid model achieves better solutions for longer computational times and was able to prove optimality more often. The continuous-type model is the most flexible of the three for incorporating additional operational requirements, at a cost of having the worst computational performance. Journal of the Operational Research Society (2012) 63, 1613-1630. doi:10.1057/jors.2011.159 published online 7 March 2012

Algorithms for network design and routing problems

In this thesis we study three combinatorial optimization problems belonging to the classes of Network Design and Vehicle Routing problems that are strongly linked in the context of the design and management of transportation networks: the Non-Bifurcated Capacitated Network Design Problem (NBP), the Period Vehicle Routing Problem (PVRP) and the Pickup and Delivery Problem with Time Windows (PDPTW). These problems are NP-hard and contain as special cases some well known difficult problems such as the Traveling Salesman Problem and the Steiner Tree Problem. Moreover, they model the core structure of many practical problems arising in logistics and telecommunications. The NBP is the problem of designing the optimum network to satisfy a given set of traffic demands. Given a set of nodes, a set of potential links and a set of point-to-point demands called commodities, the objective is to select the links to install and dimension their capacities so that all the demands can be routed between their respective endpoints, and the sum of link fixed costs and commodity routing costs is minimized. The problem is called non- bifurcated because the solution network must allow each demand to follow a single path, i.e., the flow of each demand cannot be splitted. Although this is the case in many real applications, the NBP has received significantly less attention in the literature than other capacitated network design problems that allow bifurcation. We describe an exact algorithm for the NBP that is based on solving by an integer programming solver a formulation of the problem strengthened by simple valid inequalities and four new heuristic algorithms. One of these heuristics is an adaptive memory metaheuristic, based on partial enumeration, that could be applied to a wider class of structured combinatorial optimization problems. In the PVRP a fleet of vehicles of identical capacity must be used to service a set of customers over a planning period of several days. Each customer specifies a service frequency, a set of allowable day-combinations and a quantity of product that the customer must receive every time he is visited. For example, a customer may require to be visited twice during a 5-day period imposing that these visits take place on Monday-Thursday or Monday-Friday or Tuesday-Friday. The problem consists in simultaneously assigning a day- combination to each customer and in designing the vehicle routes for each day so that each customer is visited the required number of times, the number of routes on each day does not exceed the number of vehicles available, and the total cost of the routes over the period is minimized. We also consider a tactical variant of this problem, called Tactical Planning Vehicle Routing Problem, where customers require to be visited on a specific day of the period but a penalty cost, called service cost, can be paid to postpone the visit to a later day than that required. At our knowledge all the algorithms proposed in the literature for the PVRP are heuristics. In this thesis we present for the first time an exact algorithm for the PVRP that is based on different relaxations of a set partitioning-like formulation. The effectiveness of the proposed algorithm is tested on a set of instances from the literature and on a new set of instances. Finally, the PDPTW is to service a set of transportation requests using a fleet of identical vehicles of limited capacity located at a central depot. Each request specifies a pickup location and a delivery location and requires that a given quantity of load is transported from the pickup location to the delivery location. Moreover, each location can be visited only within an associated time window. Each vehicle can perform at most one route and the problem is to satisfy all the requests using the available vehicles so that each request is serviced by a single vehicle, the load on each vehicle does not exceed the capacity, and all locations are visited according to their time window. We formulate the PDPTW as a set partitioning-like problem with additional cuts and we propose an exact algorithm based on different relaxations of the mathematical formulation and a branch-and-cut-and-price algorithm. The new algorithm is tested on two classes of problems from the literature and compared with a recent branch-and-cut-and-price algorithm from the literature.

Spatial Learning and Stress Response of Male Rats Prenatally Exposed to Dexamethasone

Dexamethasone is routinely administered to women at risk for a preterm birth in order to enhance fetal lung development and reduce uterine contractions. Research has demonstrated possible behavioral abnormalities in adulthood as a result of dexamethasone treatment. Using nonlinear mixed effects modeling, this study found thatprenatal dexamethasone treatment impaired spatial learning and memory of adult male Sprague-Dawley rats. Prenatal dexamethasone treatment also led to more anxiety related behaviors on Elevated Plus Maze testing 1.5 hours after a stress challenge. Because theassumptions underlying the independent samples t-test were violated, the randomization test was used to compare groups on the Elevated Plus Maze.

ON MARGINALIZED MULTILEVEL MODELS AND THEIR COMPUTATION

Clustered data analysis is characterized by the need to describe both systematic variation in a mean model and cluster-dependent random variation in an association model. Marginalized multilevel models embrace the robustness and interpretations of a marginal mean model, while retaining the likelihood inference capabilities and flexible dependence structures of a conditional association model. Although there has been increasing recognition of the attractiveness of marginalized multilevel models, there has been a gap in their practical application arising from a lack of readily available estimation procedures. We extend the marginalized multilevel model to allow for nonlinear functions in both the mean and association aspects. We then formulate marginal models through conditional specifications to facilitate estimation with mixed model computational solutions already in place. We illustrate this approach on a cerebrovascular deficiency crossover trial.

RANDOM EFFECTS MODELS IN A META-ANALYSIS OF THE ACCURACY OF DIAGNOSTIC TESTS WITHIN A GOLD STANDARD IN THE PRESENCE OF MISSING DATA

In evaluating the accuracy of diagnosis tests, it is common to apply two imperfect tests jointly or sequentially to a study population. In a recent meta-analysis of the accuracy of microsatellite instability testing (MSI) and traditional mutation analysis (MUT) in predicting germline mutations of the mismatch repair (MMR) genes, a Bayesian approach (Chen, Watson, and Parmigiani 2005) was proposed to handle missing data resulting from partial testing and the lack of a gold standard. In this paper, we demonstrate an improved estimation of the sensitivities and specificities of MSI and MUT by using a nonlinear mixed model and a Bayesian hierarchical model, both of which account for the heterogeneity across studies through study-specific random effects. The methods can be used to estimate the accuracy of two imperfect diagnostic tests in other meta-analyses when the prevalence of disease, the sensitivities and/or the specificities of diagnostic tests are heterogeneous among studies. Furthermore, simulation studies have demonstrated the importance of carefully selecting appropriate random effects on the estimation of diagnostic accuracy measurements in this scenario.

Modeling of transfer kinetics at the serum-cerebrospinal fluid barrier in rabbits with experimental meningitis: application to grepafloxacin

The goals of the present study were to model the population kinetics of in vivo influx and efflux processes of grepafloxacin at the serum-cerebrospinal fluid (CSF) barrier and to propose a simulation-based approach to optimize the design of dose-finding trials in the meningitis rabbit model. Twenty-nine rabbits with pneumococcal meningitis receiving grepafloxacin at 15 mg/kg of body weight (intravenous administration at 0 h), 30 mg/kg (at 0 h), or 50 mg/kg twice (at 0 and 4 h) were studied. A three-compartment population pharmacokinetic model was fit to the data with the program NONMEM (Nonlinear Mixed Effects Modeling). Passive diffusion clearance (CL(diff)) and active efflux clearance (CL(active)) are transfer kinetic modeling parameters. Influx clearance is assumed to be equal to CL(diff), and efflux clearance is the sum of CL(diff), CL(active), and bulk flow clearance (CL(bulk)). The average influx clearance for the population was 0.0055 ml/min (interindividual variability, 17%). Passive diffusion clearance was greater in rabbits receiving grepafloxacin at 15 mg/kg than in those treated with higher doses (0.0088 versus 0.0034 ml/min). Assuming a CL(bulk) of 0.01 ml/min, CL(active) was estimated to be 0.017 ml/min (11%), and clearance by total efflux was estimated to be 0.032 ml/min. The population kinetic model allows not only to quantify in vivo efflux and influx mechanisms at the serum-CSF barrier but also to analyze the effects of different dose regimens on transfer kinetic parameters in the rabbit meningitis model. The modeling-based approach also provides a tool for the simulation and prediction of various outcomes in which researchers might be interested, which is of great potential in designing dose-finding trials.

Entwicklung eines Dispositionsleitstandes zur Bestimmung optimaler Torbelegungen in Stückgutspeditionsanlagen

Im operativen Betrieb einer Stückgutspeditionsanlage entscheidet der Betriebslenker bzw. der Disponent in einem ersten Schritt darüber, an welche Tore die Fahrzeuge zur Be- und Entladung andocken sollen. Darüber hinaus muss er für jede Tour ein Zeitfenster ausweisen innerhalb dessen sie das jeweilige Tor belegt. Durch die örtliche und zeitliche Fahrzeug-Tor-Zuordnung wird der für den innerbetrieblichen Umschlagprozess erforderliche Ressourcenaufwand in Form von zu fahrenden Wegstrecken oder aber Gabelstaplerstunden bestimmt. Ein Ziel der Planungsaufgabe ist somit, die Zuordnung der Fahrzeuge an die Tore so vorzunehmen, dass dabei minimale innerbetriebliche Wegstrecken entstehen. Dies führt zu einer minimalen Anzahl an benötigten Umschlagmittelressourcen. Darüber hinaus kann es aber auch zweckmäßig sein, die Fahrzeuge möglichst früh an die Tore anzudocken. Jede Tour verfügt über einen individuellen Fahrplan, der Auskunft über den Ankunftszeitpunkt sowie den Abfahrtszeitpunkt der jeweiligen Tour von der Anlage gibt. Nur innerhalb dieses Zeitfensters darf der Disponent die Tour einem der Tore zuweisen. Geschieht die Zuweisung nicht sofort nach Ankunft in der Anlage, so muss das Fahrzeug auf einer Parkfläche warten. Eine Minimierung der Wartezeiten ist wünschenswert, damit das Gelände der Anlage möglichst nicht durch zuviele Fahrzeuge gleichzeitig belastet wird. Es kann vor allem aber auch im Hinblick auf das Reservieren der Tore für zeitkritische Touren sinnvoll sein, Fahrzeuge möglichst früh abzufertigen. Am Lehrstuhl Verkehrssysteme und -logistik (VSL) der Universität Dortmund wurde die Entscheidungssituation im Rahmen eines Forschungsprojekts bei der Stiftung Industrieforschung in Anlehnung an ein zeitdiskretes Mehrgüterflussproblem mit unsplittable flow Bedingungen modelliert. Die beiden Zielsetzungen wurden dabei in einer eindimensionalen Zielfunktion integriert. Das resultierende Mixed Integer Linear Programm (MILP) wurde programmiert und für mittlere Szenarien durch Eingabe in den Optimization Solver CPlex mit dem dort implementierten exakten Branch-and-Cut Verfahren gelöst. Parallel wurde im Rahmen einer Kooperation zwischen dem Lehrstuhl VSL und dem Unternehmen hafa Docking Systems, einem der weltweit führenden Tor und Rampenhersteller, für die gleiche Planungsaufgabe ein heuristisches Scheduling Verfahren sowie ein Dispositionsleitstand namens LoadDock Navigation entwickelt. Der Dispositionsleitstand dient der optimalen Steuerung der Torbelegungen in logistischen Anlagen. In dem Leitstand wird planerische Intelligenz in Form des heuristischen Schedulingverfahrens, technische Neuerungen in der Rampentechnik in Form von Sensoren und das Expertenwissen des Disponenten in einem Tool verbunden. Das mathematische Modell sowie der Prototyp mit der integrierten Heuristik werden im Rahmen dieses Artikels vorgestellt.

Optimal Scheduling of Work-Content-Constrained Projects

The execution of a project requires resources that are generally scarce. Classical approaches to resource allocation assume that the usage of these resources by an individual project activity is constant during the execution of that activity; in practice, however, the project manager may vary resource usage over time within prescribed bounds. This variation gives rise to the project scheduling problem which consists in allocating the scarce resources to the project activities over time such that the project duration is minimized, the total number of resource units allocated equals the prescribed work content of each activity, and various work-content-related constraints are met. We formulate this problem for the first time as a mixed-integer linear program. Our computational results for a standard test set from the literature indicate that this model outperforms the state-of-the-art solution methods for this problem.

Scheduling in service systems: an application in the event-tourism industry

This paper deals with an event-bus tour booked by Bollywood film fans. During the tour, the participants visit selected locations of famous Bollywood films at various sites in Switzerland. Moreover, the tour includes stops for lunch and shopping. Each day, up to five buses operate the tour; for organizational reasons, two or more buses cannot stay at the same location simultaneously. The planning problem is how to compute a feasible schedule for each bus such that the total waiting time (primary objective) and the total travel time (secondary objective) are minimized. We formulate this problem as a mixed-integer linear program, and we report on computational results obtained with the Gurobi solver.

Decision Support Models for Composing and Navigating through e-Learning Objects

Libraries of learning objects may serve as basis for deriving course offerings that are customized to the needs of different learning communities or even individuals. Several ways of organizing this course composition process are discussed. Course composition needs a clear understanding of the dependencies between the learning objects. Therefore we discuss the metadata for object relationships proposed in different standardization projects and especially those suggested in the Dublin Core Metadata Initiative. Based on these metadata we construct adjacency matrices and graphs. We show how Gozinto-type computations can be used to determine direct and indirect prerequisites for certain learning objects. The metadata may also be used to define integer programming models which can be applied to support the instructor in formulating his specifications for selecting objects or which allow a computer agent to automatically select learning objects. Such decision models could also be helpful for a learner navigating through a library of learning objects. We also sketch a graph-based procedure for manual or automatic sequencing of the learning objects.

Preclinical modeling of multi-drug cancer therapies

Anticancer drugs typically are administered in the clinic in the form of mixtures, sometimes called combinations. Only in rare cases, however, are mixtures approved as drugs. Rather, research on mixtures tends to occur after single drugs have been approved. The goal of this research project was to develop modeling approaches that would encourage rational preclinical mixture design. To this end, a series of models were developed. First, several QSAR classification models were constructed to predict the cytotoxicity, oral clearance, and acute systemic toxicity of drugs. The QSAR models were applied to a set of over 115,000 natural compounds in order to identify promising ones for testing in mixtures. Second, an improved method was developed to assess synergistic, antagonistic, and additive effects between drugs in a mixture. This method, dubbed the MixLow method, is similar to the Median-Effect method, the de facto standard for assessing drug interactions. The primary difference between the two is that the MixLow method uses a nonlinear mixed-effects model to estimate parameters of concentration-effect curves, rather than an ordinary least squares procedure. Parameter estimators produced by the MixLow method were more precise than those produced by the Median-Effect Method, and coverage of Loewe index confidence intervals was superior. Third, a model was developed to predict drug interactions based on scores obtained from virtual docking experiments. This represents a novel approach for modeling drug mixtures and was more useful for the data modeled here than competing approaches. The model was applied to cytotoxicity data for 45 mixtures, each composed of up to 10 selected drugs. One drug, doxorubicin, was a standard chemotherapy agent and the others were well-known natural compounds including curcumin, EGCG, quercetin, and rhein. Predictions of synergism/antagonism were made for all possible fixed-ratio mixtures, cytotoxicities of the 10 best-scoring mixtures were tested, and drug interactions were assessed. Predicted and observed responses were highly correlated (r2 = 0.83). Results suggested that some mixtures allowed up to an 11-fold reduction of doxorubicin concentrations without sacrificing efficacy. Taken together, the models developed in this project present a general approach to rational design of mixtures during preclinical drug development. ^

A new method for the identification of old-growth trees in National Forest Inventories: Application to Pinus halepensis Mill. stands in Spain

Old-growth trees play a very important role in the maintenance of biodiversity in forests. However, no clear definition is yet available to help identify them since tree age is usually not recorded in National Forest Inventories. To develop and test a new method to identify old-growth trees using a species-specific threshold for tree diameter in National Forest Inventories. Different nonlinear mixed models for diameter ? age were generated using data from the Spanish Forest Inventory in order to identify the most appropriate one for Aleppo pine in its South-western distribution area. The asymptote of the optimal model indicates the threshold diameter for defining an old-growth tree. Additionally, five site index curves were examined to analyze the influence of site quality on these models.