We present versions of the Frank-Wolfe method for linearly constrained convex programs, in which consecutive search directions are made conjugate. Preliminary computational studies in a MATLAB environment applying pure Frank-Wolfe, Conjugate direction Frank-Wolfe (CFW), Bi-conjugate Frank-Wolfe (BFW) and ”PARTANized” Frank-Wolfe methods to some classical Traffic Assignment Problems show that CFW and BFW compare favorably to the other methods. This spurred a more detailed study, comparing our methods to Bar-Gera’s origin-based algorithm. This study indicates that our methods are competitive for accuracy requirements suggested by Boyce et al. We further show that CFW is globally convergent. We moreover point at independent studies by other researchers that show that our methods compare favourably with recent bush-based and gradient projection algorithms on computers with several cores. / <p>Updated from "E-publ" to published. QC 20130625</p>

The purpose of this research is to formulate a multi-commodity network flow model for vehicular traffic in a geographic area and develop a procedure for estimating traffic counts based on available partial traffic data for a selected subset of highway links. Due to the restriction of time and cost, traffic counts are not always observed for every highway link. Typically, about 50% of the links have traffic counts in urban highway networks. Also, it should be noted that the observed traffic counts are not free from random errors during the data collection process. As a result, an incoming flow into a highway node and an outgoing flow from the node do not usually match. They need to be adjusted to satisfy a flow conservation condition, which is one of the fundamental concepts in network flow analysis. In this dissertation, the multi-commodity link flows are estimated in a two-stage process. First, traffic flows of "empty" links, which have no observation data, are filled with deterministic user equilibrium traffic assignments. This user equilibrium assignment scheme assumes that travelers select their routes by their own interests without considering total cost of the system. The assignment also considers congestion effects by taking a link travel cost as a function of traffic volume on the link. As a result, the assignment problem has a nonlinear objective function and linear network constraints. The modified Frank-Wolfe algorithm, which is a type of conditional gradient method, is used to solve the assignment problem. The next step is to consider both of the observed traffic counts on selected links and the deterministic user equilibrium assignments on the group of remaining links to produce the final traffic count estimates by the generalized least squares optimization procedure. The generalized least squares optimization is conducted under a set of relevant constraints, including the flow conservation condition for all highway intersections.

The purpose of this research is to develop a heuristic algorithm to minimize total costs in multi-commodity, multi-mode generalized networks with time windows problems. The proposed mathematical model incorporates features of the congestion of vehicle flows and time restriction of delivering commodities. The heuristic algorithm, HA, has two phases. Phase 1 provides lower and upper bounds based on Lagrangian relaxations with subgradient methods. Phase 2 applies two methods, early due date with overdue-date costs and total transportation costs, to search for an improved upper bound. Two application networks are used to test HA for small and medium-scale problems. A different number of commodities and various lengths of planning time periods are generated. Results show that HA can provide good feasible solutions within the reasonable range of optimal solutions. If optimal solutions are unknown, the average gap between lower and upper bounds is 0.0239. Minimal and maximal gaps are 0.0007 and 0.3330. If optimal solutions are known, the maximal gap between upper bounds and optimal solutions is less than 10% ranges of optimal solutions.

No description available.

Successful future surface combatants in the US Navy must embrace the growing integration and interdependency of propulsive and combat systems. Traditionally, the development of Hull, Mechanical and Electrical systems has been segregated from the development of weapons and sensors. However, with the incorporation of high energy weapons into future ship configurations, ship design processes must evolve to embrace the concept of a System of Systems being the only way to achieve affordable capability in our future fleets. This thesis bridges the gap between the physical architecture of components within a ship and the way in which they are logically connected to model the energy flow through a representative design and provide insight into sizing requirements of both system components and their connections using an Architecture Flow Optimization (AFO). This thesis presents a unique method and tool to optimize naval ship system logical and physical architecture considering necessary operational conditions and possible damage scenarios. The particular and unique contributions of this thesis are: 1) initially only energy flow is considered without explicit consideration of commodity flow (electric, mechanical, chilled water, etc.), which is calculated in post-processing; 2) AFO is applied to a large and complex naval surface combatant system of systems, demonstrating its scalability; 3) data necessary for the AFO is extracted directly from a naval ship synthesis model at a concept exploration level of detail demonstrating its value in early stage design; and 4) it uses network-based methods which make it adaptable to future knowledge-based network analysis methods and approaches. / Master of Science

Norrmejerier står inför förändringar vad gäller både mjölkkonsumtion och flytt av produktionen från Luleå mejeri till Umeå mejeri inom en snar framtid. Det har gett behov av ett verktyg för att snabbt kunna fatta beslut om systemet kan hantera en ökad mängd volym och antal produktkategorier. För att ta fram ett sådant verktyg skapades en matematisk optimeringsmodell uppbyggd i programvaran Python som gör det möjligt att köra programmet för olika scenarion. Modellen använder optimeringslösaren Pulp för att hitta en lösning på problemet. Den matematiska modellen baseras på Multi Commodity Flow Problem med tidsvariabel i kombination med Flow-shop scheduling och har modifierats efter systemet på Umeå mejeri. Det är en pessimistisk modell baserat på de antaganden som gjorts i rapporten. Programmet baseras på ett dygns produktion och avgör, genom att minimera den totala tiden det tar för flödet genom processen, om det finns kapacitet för en ökad produktion. Systemet i projektet är uppdelat i två subnätverk på grund av tidskomplexiteten och resultaten visar att implementering av en ytterligare produktkategori kan hanteras av båda subnätverken. En ökad volym med 10% av den befintliga kan endast hanteras av den första delen av nätverket. Det betyder att det finns tekniska begränsningar i det andra subnätverket. Genom tillägg av extra noder som kan användas till en viss straffkostnad kunde flaskhalsar identifieras och det visade sig att pastör 2P1 är en uppenbar flaskhals i systemet. Om man ökar produktionen ytterligare kan även silosarna behöva utökas för att hantera flödet. / Norrmejerier is facing changes in terms of both milk consumption and a move of the production from Luleå dairy to Umeå dairy in the near future. This has given rise to the need of a tool that quickly can make descisions about whether the system can handle an increased amount of volume and number of product categories. To produce such a tool a mathematical optimization model was created in Python which makes it possible to run the program for different scenarios. The model uses the optimization solver Pulp. The mathematical model is based on Multi Commodity Flow Problem with time variable combined with Flow-shop scheduling and has been modified according to the system at Umeå dairy. Based on the assumptions made in the report it is a pessimistic model. The program is based on one day's production and determines by minimizing the total time it takes for the flow to pass through the system, to see if there is enough capacity for increased production. The system in the project is divided into two subnetworks due to the time complexity and the results show that implementation of an additional product category can be handled by both subnetworks. An increased volume of 10% of the existing volume can only be handled by the first part of the network. This means that there are technical limitations in the second subnetwork. By adding extra nodes that can be used for a certain penalty cost, bottlenecks could be identified and it turned out that Pasteur 2P1 is an obvious bottleneck in the system. If the production increases further the silos may also need to be expanded to handle the flow in the system.

In the oil industry, there is a special class of pipelines used for the transportation of refined products. The problem of sequencing the inputs to be pumped through this type of pipeline seeks to generate the optimal sequence of batches of products and their destination as well as the amount of product to be pumped such that the total operational cost of the system, or another operational objective, is optimized while satisfying the product demands according to the requirements set by the customers. This dissertation introduces a new modeling approach and proposes a solution methodology for this problem capable of dealing with the topology of all the scenarios reported in the literature so far. The system representation is based on a 1-0 multi commodity network flow formulation that models the dynamics of the system, including aspects such as conservation of product flow constraints at the depots, travel time of products from the refinery to their depot destination and what happens upstream and downstream the line whenever a product is being received at a given depot while another one is being injected into the line at the refinery. It is assumed that the products are already available at the refinery and their demand at each depot is deterministic and known beforehand. The model provides the sequence, the amounts, the destination and the trazability of the shipped batches of different products from their sources to their destinations during the entire horizon planning period while seeking the optimization of pumping and inventory holding costs satisfying the time window constraints. A survey for the available literature is presented. Given the problem structure, a decomposition based solution procedure is explored with the intention of exploiting the network structure using the network simplex method. A branch and bound algorithm that exploits the dynamics of the system assigning priorities for branching to a selected set of variables is proposed and its computational results for the solution, obtained via GAMS/CPLEX, of the formulation for random instances of the problem of different sizes are presented. Future research directions on this field are proposed.

The ability of Next-Generation Sequencing (NGS) to produce massive quantities of genomic data inexpensively has allowed to study the structure of viral populations from an infected host at an unprecedented resolution. As a result of a high rate of mutation and recombination events, an RNA virus exists as a heterogeneous "swarm". Virologists and computational epidemiologists are widely using NGS data to study viral populations. However, discerning rare variants is muddled by the presence of errors introduced by the sequencing technology. We develop and implement time- and cost-efficient strategy for NGS of multiple viral samples, and computational methods to analyze large quantities of NGS data and to handle sequencing errors. In particular, we present: (i) combinatorial pooling strategy for massive NGS of viral samples; (ii) kGEM and 2SNV — methods for viral population haplotyping; (iii) ShotMCF — a Multicommodity Flow (MCF) based method for frequency estimation of viral haplotypes; (iv) QUASIM — an agent-based simulator of viral evolution taking in account viral variants and immune response.

Energy markets feature a wide range of unusual price behaviour along with a complicated dependence structure between electricity, natural gas, coal and carbon, as well as other variables. We approach this broad modelling challenge by firstly developing a structural framework to modelling spot electricity prices, through an analysis of the underlying supply and demand factors which drive power prices, and the relationship between them. We propose a stochastic model for fuel prices, power demand and generation capacity availability, as well as a parametric form for the bid stack function which maps these price drivers to the spot electricity price. Based on the intuition of cost-related bids from generators, the model describes mathematically how different fuel prices drive different portions of the bid stack (i.e., the merit order) and hence influence power prices at varying levels of demand. Using actual bid data, we find high correlations between the movements of bids and the corresponding fuel prices (coal and gas). We fit the model to the PJM and New England markets in the US, and assess the performance of the model, in terms of capturing key properties of simulated price trajectories, as well as comparing the model’s forward prices with observed data. We then discuss various mathematical techniques (explicit solutions, approximations, simulations and other numerical techniques) for calibrating to observed fuel and electricity forward curves, as well as for pricing of various single and multi-commodity options. The model reveals that natural gas prices are historically the primary driver of power prices over long horizons in both markets, with shorter term dynamics driven also by fluctuations in demand and reserve margin. However, the framework developed in this thesis is very flexible and able to adapt to different markets or changing conditions, as well as capturing automatically the possibility of changes in the merit order of fuels. In particular, it allows us to begin to understand price movements in the recently-formed carbon emissions markets, which add a new level of complexity to energy price modelling. Thus, the bid stack model can be viewed as more than just an original and elegant new approach to spot electricity prices, but also a convenient and intuitive tool for understanding risks and pricing contracts in the global energy markets, an important, rapidly-growing and fascinating area of research.

O presente trabalho trata do planejamento da movimentação de contêineres vazios ao longo de um conjunto de portos, buscando o balanceamento entre as demandas e ofertas dos mesmos em todos os portos ao menor custo, e considerando as restrições de capacidade de transporte dos modais envolvidos. Para isso será adotado um modelo de fluxo em rede multi-produto para representar o sistema de movimentação de contêineres vazios e que servirá de base para o desenvolvimento de uma formulação matemática, a qual, implementada através de uma ferramenta computacional de otimização, determina os fluxos de vazios no sistema. A verificação do modelo proposto deu-se através de testes em problemas reduzidos de movimentação de vazios, assim como em um problema cujos resultados foram publicados na literatura. Os resultados sugeriram a adequabilidade e confiabilidade do modelo proposto que pode, então, ser aplicado a um problema real da empresa de navegação Hamburg Süd, tendo seus resultados comparados aos resultados fornecidos pela mesma. / This dissertation deals with the empty containers movement planning throughout a set of ports, aiming the balancing between the demands and supplies in all the ports at minimal cost, and considering the capacity constraints of the transport modes considered. A multi-commodity network flow model will be adopted to represent the empty containers movement system. This model supports the development of a mathematical formulation which, through a computational optimization tool, determines the flows of empty containers throughout the system. The verification of the proposed model was given through tests in reduced problems, as well as in a problem which results had already been published in literature. The results had suggested the adequateness and trustworthiness of the proposed model, which could, then, be applied to a real problem of the navigation company Hamburg Süd, and the results could be compared with the ones given by the company.