In this dissertation, we consider extensions of dynamic programming for combinatorial optimization. We introduce two exact multi-objective optimization algorithms: the multi-stage optimization algorithm that optimizes the problem relative to the ordered sequence of objectives (lexicographic optimization) and the bi-criteria optimization algorithm that simultaneously optimizes the problem relative to two objectives (Pareto optimization). We also introduce a counting algorithm to count optimal solution before and after every optimization stage of multi-stage optimization. We propose a fairly universal approach based on so-called circuits without repetitions in which each element is generated exactly one time. Such circuits represent the sets of elements under consideration (the sets of feasible solutions) and are used by counting, multi-stage, and bi-criteria optimization algorithms. For a given optimization problem, we should describe an appropriate circuit and cost functions. Then, we can use the designed algorithms for which we already have proofs of their correctness and ways to evaluate the required number of operations and the time. We construct conventional (which work directly with elements) circuits without repetitions for matrix chain multiplication, global sequence alignment, optimal paths in directed graphs, binary search trees, convex polygon triangulation, line breaking (text justification), one-dimensional clustering, optimal bitonic tour, and segmented least squares. For these problems, we evaluate the number of operations and the time required by the optimization and counting algorithms, and consider the results of computational experiments. If we cannot find a conventional circuit without repetitions for a problem, we can either create custom algorithms for optimization and counting from scratch or can transform a circuit with repetitions into a so-called syntactical circuit, which is a circuit without repetitions that works not with elements but with formulas representing these elements. We apply both approaches to the optimization of matchings in trees and apply the second approach to the 0/1 knapsack problem. We also briefly introduce our work in operation research with applications to health care. This work extends our interest in the optimization field from developing new methods included in this dissertation towards the practical application.

The power to mass ratio of a heavy truck causes even moderate slopes to have a significant influence on the motion. The velocity will inevitable vary within an interval that is primarily determined by the ratio and the road topography. If further variations are actuated by a controller, there is a potential to lower the fuel consumption by taking the upcoming topography into account. This possibility is explored through theoretical and simulation studies as well as experiments in this work. Look-ahead control is a predictive strategy that repeatedly solves an optimization problem online by means of a tailored dynamic programming algorithm. The scenario in this work is a drive mission for a heavy diesel truck where the route is known. It is assumed that there is road data on-board and that the current heading is known. A look-ahead controller is then developed to minimize fuel consumption and trip time. The look-ahead control is realized and evaluated in a demonstrator vehicle and further studied in simulations. In the prototype demonstration, information about the road slope ahead is extracted from an on-board database in combination with a GPS unit. The algorithm calculates the optimal velocity trajectory online and feeds the conventional cruise controller with new set points. The results from the experiments and simulations confirm that look-ahead control reduces the fuel consumption without increasing the travel time. Also, the number of gear shifts is reduced. Drivers and passengers that have participated in tests and demonstrations have perceived the vehicle behavior as comfortable and natural. / <p>Report code: LIU-TEK-LIC-2007:28.</p>

Many tasks of visual computing and communications such as object recognition, matting, compression, etc., need to extract and encode the outer boundary of the object in a digital image or video. In this thesis, we focus on a particular video segmentation task and propose an efficient method for head-and-shoulder of humans through video frames. The key innovations for our work are as follows: (1) a novel head descriptor in polar coordinate is proposed, which can characterize intrinsic head object well and make it easy for computer to process, classify and recognize. (2) a learning-based method is proposed to provide highly precise and robust head-and-shoulder segmentation results in applications where the head-and-shoulder object in the question is a known prior and the background is too complex. The efficacy of our method is demonstrated on a number of challenging experiments. / Thesis / Master of Applied Science (MASc)

<p> Differential Dynamic. Programming is a new method, based on Bellman's principle of optimality, for determining optimal control strategies for nonlinear systems. It has originally been developed by D.H.Jacobson. </p> <p> In this thesis a result is presented for a problem with saturation characteristics in nonlinearity solved by the Jacobson's approach. In the differential dynamic programming the principle of optimality is applied to the differential change in non-optimal cost due to small changes in state; variables instead of the cost itself. This results in modest memory requirements for its defining parameters and rapid convergence. </p> / Thesis / Master of Engineering (MEngr)

No description available.

This thesis examines decision optimization of product recalls. Product recalls in recent years have shown unprecedented impact on both immediate economic and reputational damage to the company and long-lasting impact on the brand and industry. Admittedly, imperfect product quality makes recalls inevitable. Thus, we explore from three perspectives to elicit business insights regarding better management and risk control. Chapter 1 introduces the topic of product recall management optimization and its real-world motivation. Chapter 2 views the decision making of "when to initiate a product recall" as a dynamic process and takes the feedback of customer returns to update the product defect rate. Updating is simplified by the conjugate properties of beta distribution and Bernoulli trials. We develop the optimal stopping model to find the thresholds of total product returns above which initiating recall is optimal. We implement dynamic programming to solve the model optimally. For large-size problems, we propose a simulation method to balance computation time with solution quality. Chapter 3 allows the company to control the recall risk by investing in quality. We adopt the one-stage stochastic newsvendor model and add quality-dependent recall risk. The resulting model is not concave in production quantity and quality levels. The parametric analysis reveals several interesting features such as the optimal ordering quantity and quality level have a conflicting relationship. We further extend our model from internal supply to external supply from multiple sources. Chapter 4 examines managing product recalls from the closed-loop supply chain management and disruption management perspectives. We model the location and allocation decisions of both manufacturing plants and reprocessing facilities where facilities are built after the recalls. Numerical experiments show the costs of overlooking potential recalls vary greatly, indicating the necessity of considering recalls in initial designs and the importance of accurate recall probability prediction. Chapter 5 summarizes. / Thesis / Doctor of Philosophy (PhD)

No description available.

This work deals with building a program system for solving dynamic programming problems on a computer. The theoretical part describes dynamic programming as a tool used for optimizing multistage decision processes and dynamic programming problems implemented in the program system. The practical part describes the design and implementation of the program system and verification of its functionality.

The future success of chargeable vehicles will, among other factors, depend on their charging costs and their ability to charge with minimal disturbances to the national, local and household electrical grid. To be able to minimize costs and schedule charging sessions, there has to be knowledge of how the charging power varies with time. This is called charging profile. A number of charging profiles for a Volvo V60 plug‑in hybrid electric vehicle have been recorded. For charging currents above 10 A they prove to be more complex than are assumed in most current research papers.   The charging profiles are used together with historical electricity prices to calculate charging costs for 2013 and 2014. Charging is assumed to take place during the night, between 18:00 and 07:00, with the battery being totally depleted at 18:00. By using a timer to have the charging start at 01:00, instead of immediately at 18:00, annual charging costs are reduced by approximately 7 to 8%. By using dynamic programming to optimize the charging sessions, annual charging costs are reduced by approximately 10 to 11%. An interesting issue regarding dynamic programming was identified, namely when using a limited set of predetermined discrete control signals, interpolation returns unrealizable cost-to-go values. This occurs specifically for instances crossing the zero cost-to-go area boundary.   It is concluded that the mentioned savings are realizable, via implementing timers or optimization algorithms into consumer charging stations. Finally, by using these decentralized charging planning tools and seen from a power usage perspective, at least 30% of the Swedish vehicle fleet could be chargeable and powered by the electrical grid.

published_or_final_version / Mathematics / Master / Master of Philosophy