Spelling suggestions: "subject:"mixed integer quadratic erogramming"" "subject:"mixed integer quadratic cprogramming""
1 |
Vehicle Routing for Emergency EvacuationsPereira, Victor Caon 22 November 2013 (has links)
This dissertation introduces and analyzes the Bus Evacuation Problem (BEP), a unique Vehicle Routing Problem motivated both by its humanitarian significance and by the routing and scheduling challenges of planning transit-based, regional evacuations. First, a variant where evacuees arrive at constant, location-specific rates is introduced. In this problem, a fleet of capacitated buses must transport all evacuees to a depot/shelter such that the last scheduled pick-up and the end of the evacuee arrival process occurs at a location-specific time. The problem seeks to minimize their accumulated waiting time, restricts the number of pick-ups on each location, and exploits efficiencies from service choice and from allowing buses to unload evacuees at the depot multiple times. It is shown that, depending on the problem instance, increasing the maximum number of pick-ups allowed may reduce both the fleet size requirement and the evacuee waiting time, and that, past a certain threshold, there exist a range of values that guarantees an efficient usage of the available fleet and equitable reductions in waiting time across pick-up locations. Second, an extension of the Ritter (1967) Relaxation Algorithm, which explores the inherent structure of problems with complicating variables and constraints, such as the aforementioned BEP variant, is presented. The modified algorithm allows problems with linear, integer, or mixed-integer subproblems and with linear or quadratic objective functions to be solved to optimality. Empirical studies demonstrate the algorithm viability to solve large optimization problems. Finally, a two-stage stochastic formulation for the BEP is presented. Such variant assumes that all evacuees are at the pick-up locations at the onset of the evacuation, that the set of possible demands is provided, and, more importantly, that the actual demands become known once buses visit the pick-up locations for the first time. The effect of exploratory visits (sampling) and symmetry is explored, and the resulting insights used to develop an improved formulation for the problem. An iterative (dynamic) solution algorithm is proposed. / Ph. D.
|
2 |
Control Design for a Microgrid in Normal and Resiliency Modes of a Distribution SystemAlvarez, Genesis Barbie 17 October 2019 (has links)
As inverter-based distributed energy resources (DERs) such as photovoltaic (PV) and battery energy storage system (BESS) penetrate within the distribution system. New challenges regarding how to utilize these devices to improve power quality arises. Before, PV systems were required to disconnect from the grid during a large disturbance, but now smart inverters are required to have dynamically controlled functions that allows them to remain connected to the grid. Monitoring power flow at the point of common coupling is one of the many functions the controller should perform. Smart inverters can inject active power to pick up critical load or inject reactive power to regulate voltage within the electric grid. In this context, this thesis focuses on a high level and local control design that incorporates DERs. Different controllers are implemented to stabilize the microgrid in an Islanding and resiliency mode. The microgrid can be used as a resiliency source when the distribution is unavailable. An average model in the D-Q frame is calculated to analyze the inherent dynamics of the current controller for the point of common coupling (PCC). The space vector approach is applied to design the voltage and frequency controller. Secondly, using inverters for Volt/VAR control (VVC) can provide a faster response for voltage regulation than traditional voltage regulation devices. Another objective of this research is to demonstrate how smart inverters and capacitor banks in the system can be used to eliminate the voltage deviation. A mixed-integer quadratic problem (MIQP) is formulated to determine the amount of reactive power that should be injected or absorbed at the appropriate nodes by inverter. The Big M method is used to address the nonconvex problem. This contribution can be used by distribution operators to minimize the voltage deviation in the system. / Master of Science / Reliable power supply from the electric grid is an essential part of modern life. This critical infrastructure can be vulnerable to cascading failures or natural disasters. A solution to improve power systems resilience can be through microgrids. A microgrid is a small network of interconnected loads and distributed energy resources (DERs) such as microturbines, wind power, solar power, or traditional internal combustion engines. A microgrid can operate being connected or disconnected from the grid. This research emphases on the potentially use of a Microgrid as a resiliency source during grid restoration to pick up critical load. In this research, controllers are designed to pick up critical loads (i.e hospitals, street lights and military bases) from the distribution system in case the electric grid is unavailable. This case study includes the design of a Microgrid and it is being tested for its feasibility in an actual integration with the electric grid. Once the grid is restored the synchronization between the microgrid and electric must be conducted. Synchronization is a crucial task. An abnormal synchronization can cause a disturbance in the system, damage equipment, and overall lead to additional system outages. This thesis develops various controllers to conduct proper synchronization. Interconnecting inverter-based distributed energy resources (DERs) such as photovoltaic and battery storage within the distribution system can use the electronic devices to improve power quality. This research focuses on using these devices to improve the voltage profile within the distribution system and the frequency within the Microgrid.
|
3 |
Constrained Control for Helicopter Shipboard Operations and Moored Ocean Current Turbine Flight ControlNgo, Tri Dinh 30 June 2016 (has links)
This dissertation focuses on constrained control of two applications: helicopter and ocean current turbines (OCT).
A major contribution in the helicopter application is a novel model predictive control (MPC) framework for helicopter shipboard operations in high demanding sea-based conditions. A complex helicopter-ship dynamics interface has been developed as a system of implicit nonlinear ordinary differential equations to capture essential characteristics of the nonlinear helicopter dynamics, the ship dynamics, and the ship airwake interactions. Various airwake models such as Control Equivalent Turbulence Inputs (CETI) model and Computation Fluid Dynamics (CFD) data of the airwake are incorporated in the interface to describe a realistic model of the shipborne helicopter. The feasibility of the MPC design is investigated using two case studies: automatic deck landing during the ship quiescent period in sea state 5, and lateral reposition toward the ship in different wind-over-deck conditions. To improve the overall MPC performance, an updating scheme for the internal model of the MPC is proposed using linearization around operating points. A mixed-integer MPC algorithm is also developed for helicopter precision landing on moving decks. The performance of this control structure is evaluated via numerical simulations of the automatic deck landing in adverse conditions such as landing on up-stroke, and down-stroke moving decks with high energy indices. Kino-dynamic motion planning for coordinated maneuvers to satisfy the helicopter-ship rendezvous conditions is implemented via mixed integer quadratic programming.
In the OCT application, the major contribution is that a new idea is leveraged from helicopter blade control by introducing cyclic blade pitch control in OCT. A minimum energy, constrained control method, namely Output Variance Constrained (OVC) control is studied for OCT flight control in the presence of external disturbances. The minimum achievable output variance bounds are also computed and a parametric study of design parameters is conducted to evaluate their influence on the OVC performance. The performance of the OVC control method is evaluated both on the linear and nonlinear OCT models. Furthermore, control design for the OCT with sensor failures is also examined. Lastly, the MPC strategy is also investigated to improve the OCT flight control performance in simultaneous satisfaction of multiple constraints and to avoid blade stall. / Ph. D.
|
4 |
Applications of Integer Quadratic Programming in Control and CommunicationAxehill, Daniel January 2005 (has links)
<p>The main topic of this thesis is integer quadratic programming with applications to problems arising in the areas of automatic control and communication. One of the most widespread modern control principles is the discrete-time method Model Predictive Control (MPC). The main advantage with MPC, compared to most other control principles, is that constraints on control signals and states can easily be handled. In each time step, MPC requires the solution of a Quadratic Programming (QP) problem. To be able to use MPC for large systems, and at high sampling rates, optimization routines tailored for MPC are used. In recent years, the range of application of MPC has been extended from constrained linear systems to so-called hybrid systems. Hybrid systems are systems where continuous dynamics interact with logic. When this extension is made, binary variables are introduced in the problem. As a consequence, the QP problem has to be replaced by a far more challenging Mixed Integer Quadratic Programming (MIQP) problem. Generally, for this type of optimization problems, the computational complexity is exponential in the number of binary optimization variables. In modern communication systems, multiple users share a so-called multi-access channel, where the information sent by different users is separated by using almost orthogonal codes. Since the codes are not completely orthogonal, the decoded information at the receiver is slightly correlated between different users. Further, noise is added during the transmission. To estimate the information originally sent, a maximum likelihood problem involving binary variables is solved. The process of simultaneously estimating the information sent by multiple users is called multiuser detection. In this thesis, the problem to efficiently solve MIQP problems originating from MPC is addressed. Two different algorithms are presented. First, a polynomial complexity preprocessing algorithm for binary quadratic programming problems is presented. By using the algorithm, some, or all, binary variables can be computed efficiently already in the preprocessing phase. In simulations, the algorithm is applied to unconstrained MPC problems with a mixture of real and binary control signals. It has also been applied to the multiuser detection problem, where simulations have shown that the bit error rate can be significantly reduced by using the proposed algorithm as compared to using common suboptimal algorithms. Second, an MIQP algorithm tailored for MPC is presented. The algorithm uses a branch and bound method where the relaxed node problems are solved by a dual active set QP algorithm. In this QP algorithm, the KKT-systems are solved using Riccati recursions in order to decrease the computational complexity. Simulation results show that both the QP solver and the MIQP solver proposed have lower computational complexity than corresponding generic solvers.</p> / Report code: LiU-TEK-LIC-2005:71.
|
5 |
Applications of Integer Quadratic Programming in Control and CommunicationAxehill, Daniel January 2005 (has links)
The main topic of this thesis is integer quadratic programming with applications to problems arising in the areas of automatic control and communication. One of the most widespread modern control principles is the discrete-time method Model Predictive Control (MPC). The main advantage with MPC, compared to most other control principles, is that constraints on control signals and states can easily be handled. In each time step, MPC requires the solution of a Quadratic Programming (QP) problem. To be able to use MPC for large systems, and at high sampling rates, optimization routines tailored for MPC are used. In recent years, the range of application of MPC has been extended from constrained linear systems to so-called hybrid systems. Hybrid systems are systems where continuous dynamics interact with logic. When this extension is made, binary variables are introduced in the problem. As a consequence, the QP problem has to be replaced by a far more challenging Mixed Integer Quadratic Programming (MIQP) problem. Generally, for this type of optimization problems, the computational complexity is exponential in the number of binary optimization variables. In modern communication systems, multiple users share a so-called multi-access channel, where the information sent by different users is separated by using almost orthogonal codes. Since the codes are not completely orthogonal, the decoded information at the receiver is slightly correlated between different users. Further, noise is added during the transmission. To estimate the information originally sent, a maximum likelihood problem involving binary variables is solved. The process of simultaneously estimating the information sent by multiple users is called multiuser detection. In this thesis, the problem to efficiently solve MIQP problems originating from MPC is addressed. Two different algorithms are presented. First, a polynomial complexity preprocessing algorithm for binary quadratic programming problems is presented. By using the algorithm, some, or all, binary variables can be computed efficiently already in the preprocessing phase. In simulations, the algorithm is applied to unconstrained MPC problems with a mixture of real and binary control signals. It has also been applied to the multiuser detection problem, where simulations have shown that the bit error rate can be significantly reduced by using the proposed algorithm as compared to using common suboptimal algorithms. Second, an MIQP algorithm tailored for MPC is presented. The algorithm uses a branch and bound method where the relaxed node problems are solved by a dual active set QP algorithm. In this QP algorithm, the KKT-systems are solved using Riccati recursions in order to decrease the computational complexity. Simulation results show that both the QP solver and the MIQP solver proposed have lower computational complexity than corresponding generic solvers. / <p>Report code: LiU-TEK-LIC-2005:71.</p>
|
6 |
Оптимално управљање микро мрежама у карактеристичним радним режимима / Optimalno upravljanje mikro mrežama u karakterističnim radnim režimima / Optimal Control of Microgrids in Different Operation ConditionsSelakov Aleksandar 12 September 2017 (has links)
<p>У дисертацији је дат концепт микро мрежа и описане постојеће методе у управљању и оптимизацији рада микро мрежа. Предложен је нови централизовани контролер микро мрежe заснован на технологији више-агентног система, који омогућава координацију три режима рада (повезани, острвски и хаваријски) и обезбеђује једноставну конфигурацију и комбинацију оптимизационих критеријума, уз уважавање широког скупа ограничења. Предложени модел примењен је на релевантни тест систем и резултати су приказани уз одговарајућу анализу резултата.</p> / <p>U disertaciji je dat koncept mikro mreža i opisane postojeće metode u upravljanju i optimizaciji rada mikro mreža. Predložen je novi centralizovani kontroler mikro mreže zasnovan na tehnologiji više-agentnog sistema, koji omogućava koordinaciju tri režima rada (povezani, ostrvski i havarijski) i obezbeđuje jednostavnu konfiguraciju i kombinaciju optimizacionih kriterijuma, uz uvažavanje širokog skupa ograničenja. Predloženi model primenjen je na relevantni test sistem i rezultati su prikazani uz odgovarajuću analizu rezultata.</p> / <p>Dissertation provides the microgrids concept and describes existing methods for control and optimization of microgrid operation. This paper proposes a novel, centralized, multi-agent-based, microgrid controller architecture, which provides the coordination of all three operation modes (grid-connected, island and emergency) and enables the easy configuration/combination of optimization goals that are subject to a given set of operational constraints.<br />The simulation results are presented for a typical microgrid test example.</p>
|
7 |
Um algoritmo exato para obter o conjunto solução de problemas de portfólio / An exact algorithm to obtain the solution set to portfolio problemsVillela, Pedro Ferraz, 1982- 25 August 2018 (has links)
Orientador: Francisco de Assis Magalhães Gomes Neto / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T19:03:25Z (GMT). No. of bitstreams: 1
Villela_PedroFerraz_D.pdf: 10794575 bytes, checksum: 746b8aebf0db423d557d9c5fe1446592 (MD5)
Previous issue date: 2014 / Resumo: Neste trabalho, propomos um método exato para obter o conjunto solução de um problema biobjetivo quadrático de otimização de carteiras de investimento, que envolve variáveis binárias. Nosso algoritmo é baseado na junção de três algoritmos específicos. O primeiro encontra uma curva associada ao conjunto solução de problemas biobjetivo contínuos por meio de um método de restrições ativas, o segundo encontra o ótimo de um problema de programação quadrática inteira mista pelo método Branch-and-Bound, e o terceiro encontra a interseção de duas curvas associadas a problemas biobjetivo distintos. Ao longo do texto, algumas heurísticas e métodos adicionais também são introduzidos, com o propósito de acelerar a convergência do algoritmo proposto. Além disso, o nosso método pode ser visto como uma nova contribuição na área, pois ele determina, de forma exata, a curva associada ao conjunto solução do problemas biobjetivo inteiro misto, algo que é incomum na literatura, pois o problema alvo geralmente é abordado via métodos meta-heurísticos. Ademais, ele mostrou ser eficiente do ponto de vista do tempo computacional, pois encontra o conjunto solução do problema em poucos segundos / Abstract: In this work, we propose an exact method to find the solution set of a mixed quadratic bi-objective portfolio optimization problem. Our method is based on the combination of three specific algorithms. The first one obtains a curve associated with the solution set of a continuous bi-objective problem through an active set algorithm, the second one solves a mixed quadratic optimization problem through the Branch-and-Bound method, and the third one searches the intersection of two curves associated with distinct bi-objective problems. Throughout the text, some heuristics are also introduced in order to accelerate the performance of the method. Moreover, our method can be seen as a new contribution to the field, since it finds, in an exact way, the curve related to the solution set of the mixed integer bi-objective problem, something uncommon in the corresponding literature, where the target problem is usually approached by metaheuristic methods. Additionally, it has also shown to be efficient in terms of running time, being capable of finding the problem's solution set within a much faster time frame / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada
|
8 |
Predictive Energy Management of Long-Haul Hybrid Trucks : Using Quadratic Programming and Branch-and-BoundJonsson Holm, Erik January 2021 (has links)
This thesis presents a predictive energy management controller for long-haul hybrid trucks. In a receding horizon control framework, the vehicle speed reference, battery energy reference, and engine on/off decision are optimized over a prediction horizon. A mixed-integer quadratic program (MIQP) is formulated by performing modelling approximations and by including the binary engine on/off decision in the optimal control problem. The branch-and-bound algorithm is applied to solve this problem. Simulation results show fuel consumption reductions between 10-15%, depending on driving cycle, compared to a conventional truck. The hybrid truck without the predictive control saves significantly less. Fuel consumption is reduced by 3-8% in this case. A sensitivity analysis studies the effects on branch-and-bound iterations and fuel consumption when varying parameters related to the binary engine on/off decision. In addition, it is shown that the control strategy can maintain a safe time gap to a leading vehicle. Also, the introduction of the battery temperature state makes it possible to approximately model the dynamic battery power limitations over the prediction horizon. The main contributions of the thesis are the MIQP control problem formulation, the strategy to solve this with the branch-and-bound method, and the sensitivity analysis.
|
Page generated in 0.1054 seconds