N–Dimensional Orthogonal Tile Sizing Problem

AMS subject classification: 68Q22, 90C90

A fizikai matematika legújabb eredményei mint a közgazdaság-tudomány lehetséges vizsgálati eszközei (The newest results of physical mathematics as the possible investigation tools of economics)

A közgazdaság-tudomány számos problémája a fizika analóg modelljeinek segítségével nyert megoldást. A közgazdászok körében erőteljesen megoszlanak a vélemények, hogy a közgazdasági modellek mennyire redukálhatók a fizika, vagy más természettudományok eredményeire. Vannak,akik pontosan ezzel magyarázzák,hogy a mai mainstream közgazdasági elmélet átalakult alkalmazott matematikává,ami a gazdasági kérdéseket csak a társadalom-tudományi vonatkozásaitól eltekintve képes vizsgálni. Mások, e tanulmányszerzője is, viszont úgy vélekednek, hogy a közgazdasági problémák egy része, ahol lehetőség van a mérésre, jól modellezhetők a természettudományok technikai arzenáljával. A másik része, amelyekben nem lehet mérni,s tipikusan ilyenek a társadalomtudományi kérdések, ott sokkal komplexebb technikákra lesz szükség. Etanulmány célkitűzése, hogy felvázolja a fizika legújabb, az irreverzibilis dinamika, a relativitáselmélet és a kvantummechanika sztochasztikus matematikai összefüggéseit, amelyekből a közgazdászok választhatnak egy-egy probléma megfogalmazásában és megoldásában. Például az időoperátorok pontos értelmezése jelentős fordulatot hozhat a makroökonómiai elméletekben; vagy az eddigi statikus egyensúlyi referencia pontokat felválthatják a dinamikus,időben változó sztochasztikus egyensúlyi referenciafüggvények, ami forradalmian új megvilágításba helyezhet számos társadalomtudományi, s főleg nemegyensúlyi közgazdasági kérdést.A termodinamika és a biológiai evolúció fogalmait és definícióit Paul A. Samuelson (1947) már adaptálta a közgazdaságtanban, viszont a kvantummechanika legújabb eredményeit, az időoperátorokat stb. nem érintette. E cikk azokat a legújabb fizikai, kémiai és biológiai matematikai összefüggéseket foglalja össze,amelyek hasznosak lehetnek a közgazdasági modellek komplexebb megfogalmazásához. ___________________ The aim of this paper is to out line the newest results of physics,i.e.,the stochastic mathematical relations of relativity theory and quantum mechanics as well as irreversible dynamics which can be applied for some economic problems.For example,the correct interpretation of time operators using for the macroeconomic theories may provide a serious improvement in approach to the reality.The stochastic dynamic equilibrium reference functions will take over the role of recent static equilibrium reference points,which may also reveal some nonequilibrium questions of macroeconomics.The concepts and definitions of thermodynamics and biological evolution have been adopted in economics by Paul A. Samuelson, but he did not concern the newest results of quantum mechanics, e.g., the time operators. Now we do it.In addition, following Samuelson,we show that von Neumann growth model cannot be explained as a peculiar extension of thermodynamic irreversibility.

A decision support framework for infrastructure maintenance investment decision-making

Infrastructure management agencies are facing multiple challenges, including aging infrastructure, reduction in capacity of existing infrastructure, and availability of limited funds. Therefore, decision makers are required to think innovatively and develop inventive ways of using available funds. Maintenance investment decisions are generally made based on physical condition only. It is important to understand that spending money on public infrastructure is synonymous with spending money on people themselves. This also requires consideration of decision parameters, in addition to physical condition, such as strategic importance, socioeconomic contribution and infrastructure utilization. Consideration of multiple decision parameters for infrastructure maintenance investments can be beneficial in case of limited funding. Given this motivation, this dissertation presents a prototype decision support framework to evaluate trade-off, among competing infrastructures, that are candidates for infrastructure maintenance, repair and rehabilitation investments. Decision parameters' performances measured through various factors are combined to determine the integrated state of an infrastructure using Multi-Attribute Utility Theory (MAUT). The integrated state, cost and benefit estimates of probable maintenance actions are utilized alongside expert opinion to develop transition probability and reward matrices for each probable maintenance action for a particular candidate infrastructure. These matrices are then used as an input to the Markov Decision Process (MDP) for the finite-stage dynamic programming model to perform project (candidate)-level analysis to determine optimized maintenance strategies based on reward maximization. The outcomes of project (candidate)-level analysis are then utilized to perform network-level analysis taking the portfolio management approach to determine a suitable portfolio under budgetary constraints. The major decision support outcomes of the prototype framework include performance trend curves, decision logic maps, and a network-level maintenance investment plan for the upcoming years. The framework has been implemented with a set of bridges considered as a network with the assistance of the Pima County DOT, AZ. It is expected that the concept of this prototype framework can help infrastructure management agencies better manage their available funds for maintenance.

Optimal Capital Requirements in Financial Networks with Fire Sales

I explore and analyze a problem of finding the socially optimal capital requirements for financial institutions considering two distinct channels of contagion: direct exposures among the institutions, as represented by a network and fire sales externalities, which reflect the negative price impact of massive liquidation of assets.These two channels amplify shocks from individual financial institutions to the financial system as a whole and thus increase the risk of joint defaults amongst the interconnected financial institutions; this is often referred to as systemic risk. In the model, there is a trade-off between reducing systemic risk and raising the capital requirements of the financial institutions. The policymaker considers this trade-off and determines the optimal capital requirements for individual financial institutions. I provide a method for finding and analyzing the optimal capital requirements that can be applied to arbitrary network structures and arbitrary distributions of investment returns.

In particular, I first consider a network model consisting only of direct exposures and show that the optimal capital requirements can be found by solving a stochastic linear programming problem. I then extend the analysis to financial networks with default costs and show the optimal capital requirements can be found by solving a stochastic mixed integer programming problem. The computational complexity of this problem poses a challenge, and I develop an iterative algorithm that can be efficiently executed. I show that the iterative algorithm leads to solutions that are nearly optimal by comparing it with lower bounds based on a dual approach. I also show that the iterative algorithm converges to the optimal solution.

Finally, I incorporate fire sales externalities into the model. In particular, I am able to extend the analysis of systemic risk and the optimal capital requirements with a single illiquid asset to a model with multiple illiquid assets. The model with multiple illiquid assets incorporates liquidation rules used by the banks. I provide an optimization formulation whose solution provides the equilibrium payments for a given liquidation rule.

I further show that the socially optimal capital problem using the ``socially optimal liquidation" and prioritized liquidation rules can be formulated as a convex and convex mixed integer problem, respectively. Finally, I illustrate the results of the methodology on numerical examples and

discuss some implications for capital regulation policy and stress testing.

Algorithms for Geometric Matching, Clustering, and Covering

With the popularization of GPS-enabled devices such as mobile phones, location data are becoming available at an unprecedented scale. The locations may be collected from many different sources such as vehicles moving around a city, user check-ins in social networks, and geo-tagged micro-blogging photos or messages. Besides the longitude and latitude, each location record may also have a timestamp and additional information such as the name of the location. Time-ordered sequences of these locations form trajectories, which together contain useful high-level information about people's movement patterns.

The first part of this thesis focuses on a few geometric problems motivated by the matching and clustering of trajectories. We first give a new algorithm for computing a matching between a pair of curves under existing models such as dynamic time warping (DTW). The algorithm is more efficient than standard dynamic programming algorithms both theoretically and practically. We then propose a new matching model for trajectories that avoids the drawbacks of existing models. For trajectory clustering, we present an algorithm that computes clusters of subtrajectories, which correspond to common movement patterns. We also consider trajectories of check-ins, and propose a statistical generative model, which identifies check-in clusters as well as the transition patterns between the clusters.

The second part of the thesis considers the problem of covering shortest paths in a road network, motivated by an EV charging station placement problem. More specifically, a subset of vertices in the road network are selected to place charging stations so that every shortest path contains enough charging stations and can be traveled by an EV without draining the battery. We first introduce a general technique for the geometric set cover problem. This technique leads to near-linear-time approximation algorithms, which are the state-of-the-art algorithms for this problem in either running time or approximation ratio. We then use this technique to develop a near-linear-time algorithm for this

shortest-path cover problem.

Communication-efficient decentralized sequential detection

The problem of decentralized sequential detection is studied in this thesis, where local sensors are memoryless, receive independent observations, and no feedback from the fusion center. In addition to traditional criteria of detection delay and error probability, we introduce a new constraint: the number of communications between local sensors and the fusion center. This metric is able to reflect both the cost of establishing communication links as well as overall energy consumption over time. A new formulation for communication-efficient decentralized sequential detection is proposed where the overall detection delay is minimized with constraints on both error probabilities and the communication cost. Two types of problems are investigated based on the communication-efficient formulation: decentralized hypothesis testing and decentralized change detection. In the former case, an asymptotically person-by-person optimum detection framework is developed, where the fusion center performs a sequential probability ratio test based on dependent observations. The proposed algorithm utilizes not only reported statistics from local sensors, but also the reporting times. The asymptotically relative efficiency of proposed algorithm with respect to the centralized strategy is expressed in closed form. When the probabilities of false alarm and missed detection are close to one another, a reduced-complexity algorithm is proposed based on a Poisson arrival approximation. In addition, decentralized change detection with a communication cost constraint is also investigated. A person-by-person optimum change detection algorithm is proposed, where transmissions of sensing reports are modeled as a Poisson process. The optimum threshold value is obtained through dynamic programming. An alternative method with a simpler fusion rule is also proposed, where the threshold values in the algorithm are determined by a combination of sequential detection analysis and constrained optimization. In both decentralized hypothesis testing and change detection problems, tradeoffs in parameter choices are investigated through Monte Carlo simulations.

Gait Regulation for Bipedal Locomotion

This work explores regulation of forward speed, step length, and slope walking for the passive-dynamic class of bipedal robots. Previously, an energy-shaping control for regulating forward speed has appeared in the literature; here we show that control to be a special case of a more general time-scaling control that allows for speed transitions in arbitrary time. As prior work has focused on potential energy shaping for fully actuated bipeds, we study in detail the shaping of kinetic energy for bipedal robots, giving special treatment to issues of underactuation. Drawing inspiration from features of human walking, an underactuated kinetic-shaping control is presented that provides efficient regulation of walking speed while adjusting step length. Previous results on energetic symmetries of bipedal walking are also extended, resulting in a control that allows regulation of speed and step length while walking on any slope. Finally we formalize the optimal gait regulation problem and propose a dynamic programming solution seeded with passive-dynamic limit cycles. Observations of the optimal solutions generated by this method reveal further similarities between passive dynamic walking and human locomotion and give insight into the structure of minimum-effort controls for walking.

Vulcanus 2.0: A Recommender System for Accessibility

Even though the use of recommender systems is already widely spread in several application areas, there is still a lack of studies for accessibility research field. One of these attempts to use recommender system benefits for accessibility needs is Vulcanus. The Vulcanus recommender system uses similarity analysis to compare user’s trails. In this way, it is possible to take advantage of the user’s past behavior and distribute personalized content and services. The Vulcanus combined concepts from ubiquitous computing, such as user profiles, context awareness, trails management, and similarity analysis. It uses two different approaches for trails similarity analysis: resources patterns and categories patterns. In this work we performed an asymptotic analysis, identifying Vulcanus’ algorithm complexity. Furthermore we also propose improvements achieved by dynamic programming technique, so the ordinary case is improved by using a bottom-up approach. With that approach, many unnecessary comparisons can be skipped and now Vulcanus 2.0 is presented with improvements in its average case scenario.

Energy Management of a Battery-Ultracapacitor Hybrid Energy Storage System in Electric Vehicles

Electric vehicle (EV) batteries tend to have accelerated degradation due to high peak power and harsh charging/discharging cycles during acceleration and deceleration periods, particularly in urban driving conditions. An oversized energy storage system (ESS) can meet the high power demands; however, it suffers from increased size, volume and cost. In order to reduce the overall ESS size and extend battery cycle life, a battery-ultracapacitor (UC) hybrid energy storage system (HESS) has been considered as an alternative solution. In this work, we investigate the optimized configuration, design, and energy management of a battery-UC HESS. One of the major challenges in a HESS is to design an energy management controller for real-time implementation that can yield good power split performance. We present the methodologies and solutions to this problem in a battery-UC HESS with a DC-DC converter interfacing with the UC and the battery. In particular, a multi-objective optimization problem is formulated to optimize the power split in order to prolong the battery lifetime and to reduce the HESS power losses. This optimization problem is numerically solved for standard drive cycle datasets using Dynamic Programming (DP). Trained using the DP optimal results, an effective real-time implementation of the optimal power split is realized based on Neural Network (NN). This proposed online energy management controller is applied to a midsize EV model with a 360V/34kWh battery pack and a 270V/203Wh UC pack. The proposed online energy management controller effectively splits the load demand with high power efficiency and also effectively reduces the battery peak current. More importantly, a 38V-385Wh battery and a 16V-2.06Wh UC HESS hardware prototype and a real-time experiment platform has been developed. The real-time experiment results have successfully validated the real-time implementation feasibility and effectiveness of the real-time controller design for the battery-UC HESS. A battery State-of-Health (SoH) estimation model is developed as a performance metric to evaluate the battery cycle life extension effect. It is estimated that the proposed online energy management controller can extend the battery cycle life by over 60%.

Short-Term Trading for a Wind-PV Power Producer in an Electricity Market

This paper deals with the problem of coordinated trading of wind and photovoltaic systems in order to find the optimal bid to submit in a pool-based electricity market. The coordination of wind and photovoltaic systems presents uncertainties not only due to electricity market prices, but also with wind and photovoltaic power forecast. Electricity markets are characterized by financial penalties in case of deficit or excess of generation. So, the aim o this work is to reduce these financial penalties and maximize the expected profit of the power producer. The problem is formulated as a stochastic linear programming problem. The proposed approach is validated with real data of pool-based electricity market of Iberian Peninsula.

Bidding and Optimization Strategies for Wind-PV Systems in Electricity Markets Assisted by CPS

The variability in non-dispatchable power generation raises important challenges to the integration of renewable energy sources into the electricity power grid. This paper provides the coordinated trading of wind and photovoltaic energy assisted by a cyber-physical system for supporting management decisions to mitigate risks due to the wind and solar power variability, electricity prices, and financial penalties arising out the generation shortfall and surplus. The problem of wind-photovoltaic coordinated trading is formulated as a stochastic linear programming problem. The goal is to obtain the optimal bidding strategy that maximizes the total profit. The wind-photovoltaic coordinated operation is modelled and compared with the uncoordinated operation. A comparison of the models and relevant conclusions are drawn from an illustrative case study of the Iberian day-ahead electricity market.

Optimal Wind Bidding Strategies in Day-Ahead Markets

This paper presents a computer application for wind energy bidding in a day-ahead electricity market to better accommodate the variability of the energy source. The computer application is based in a stochastic linear mathematical programming problem. The goal is to obtain the optimal bidding strategy in order to maximize the revenue. Electricity prices and financial penalties for shortfall or surplus energy deliver are modeled. Finally, conclusions are drawn from an illustrative case study, using data from the day-ahead electricity market of the Iberian Peninsula.

Modelling and Optimization of Energy Management Strategies for Hybrid Vehicles

In the last decades the automotive sector has seen a technological revolution, due mainly to the more restrictive regulation, the newly introduced technologies and, as last, to the poor resources of fossil fuels remaining on Earth. Promising solution in vehicles’ propulsion are represented by alternative architectures and energy sources, for example fuel-cells and pure electric vehicles. The automotive transition to new and green vehicles is passing through the development of hybrid vehicles, that usually combine positive aspects of each technology. To fully exploit the powerful of hybrid vehicles, however, it is important to manage the powertrain’s degrees of freedom in the smartest way possible, otherwise hybridization would be worthless. To this aim, this dissertation is focused on the development of energy management strategies and predictive control functions. Such algorithms have the goal of increasing the powertrain overall efficiency and contextually increasing the driver safety. Such control algorithms have been applied to an axle-split Plug-in Hybrid Electric Vehicle with a complex architecture that allows more than one driving modes, including the pure electric one. The different energy management strategies investigated are mainly three: the vehicle baseline heuristic controller, in the following mentioned as rule-based controller, a sub-optimal controller that can include also predictive functionalities, referred to as Equivalent Consumption Minimization Strategy, and a vehicle global optimum control technique, called Dynamic Programming, also including the high-voltage battery thermal management. During this project, different modelling approaches have been applied to the powertrain, including Hardware-in-the-loop, and diverse powertrain high-level controllers have been developed and implemented, increasing at each step their complexity. It has been proven the potential of using sophisticated powertrain control techniques, and that the gainable benefits in terms of fuel economy are largely influenced by the chose energy management strategy, even considering the powerful vehicle investigated.

Development of predictive energy management strategies for hybrid electric vehicles supported by connectivity

Nowadays, the spreading of the air pollution crisis enhanced by greenhouse gases emission is leading to the worsening of the global warming. In this context, the transportation sector plays a vital role, since it is responsible for a large part of carbon dioxide production. In order to address these issues, the present thesis deals with the development of advanced control strategies for the energy efficiency optimization of plug-in hybrid electric vehicles (PHEVs), supported by the prediction of future working conditions of the powertrain. In particular, a Dynamic Programming algorithm has been developed for the combined optimization of vehicle energy and battery thermal management. At this aim, the battery temperature and the battery cooling circuit control signal have been considered as an additional state and control variables, respectively. Moreover, an adaptive equivalent consumption minimization strategy (A-ECMS) has been modified to handle zero-emission zones, where engine propulsion is not allowed. Navigation data represent an essential element in the achievement of these tasks. With this aim, a novel simulation and testing environment has been developed during the PhD research activity, as an effective tool to retrieve routing information from map service providers via vehicle-to-everything connectivity. Comparisons between the developed and the reference strategies are made, as well, in order to assess their impact on the vehicle energy consumption. All the activities presented in this doctoral dissertation have been carried out at the Green Mobility Research Lab} (GMRL), a research center resulting from the partnership between the University of Bologna and FEV Italia s.r.l., which represents the industrial partner of the research project.

Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable,nondecreasing and convex on the number of jobs in eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.