Entropy-based framework for combinatorial optimization problems and enabling the grid of the future

Baranwal, Mayank

Permalink

https://hdl.handle.net/2142/101489 Copy

Description

Title

Entropy-based framework for combinatorial optimization problems and enabling the grid of the future

Author(s)

Baranwal, Mayank

Issue Date

2018-06-14

Director of Research (if dissertation) or Advisor (if thesis)

Salapaka, Srinivasa M.

Doctoral Committee Chair(s)

Salapaka, Srinivasa M.

Committee Member(s)

• Srikant, Rayadurgam
• Beck, Carolyn
• Belabbas, Mohammed Ali
• Bose, Subhonmesh
• Chandrasekaran, Karthekeyan

Department of Study

Mechanical Sci & Engineering

Discipline

Mechanical Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

maximum entropy principle, combinatorial optimization, traveling salesman problem, clustering, multiway cut, microgrid, robust control, distributed control, converter, inverter

Abstract

This thesis is divided into two parts. In the first part, I describe efficient meta-heuristic algorithms for a series of combinatorially complex optimization problems, while the second part is concerned with robust and scalable control architecture for a network of paralleled converter/inverter systems (DC/AC microgrids). Combinatorial optimization problems arise in many applications in various forms in seemingly unrelated areas such as data compression, pattern recognition, image segmentation, resource allocation, routing, and scheduling, graph aggregation, and graph partition problems. These optimization problems are characterized by a combinatorial number of configurations, where a cost value can be assigned to each configuration, and the goal is to find the configuration that minimizes the cost. Moreover, these optimization problems are largely non-convex, computationally complex and suffer from multiple local minima that riddle the cost surface. Most heuristics to these optimization problems are very sensitive to initial guess solutions, and efforts to make them robust to initializations typically come at significant computational costs such that the algorithms lose practicality in many applications. In our work, we are motivated by solutions that are employed by nature to similar combinatorial optimization problems; well described in terms of laws such as maximum entropy principle (MEP) in statistical physics literature. We propose to use MEP in solving a variety of combinatorial optimization problems. Our main current contributions are threefold - (i) First we provide a clustering or resource allocation viewpoint to several combinatorial optimization problems: (a) data clustering, (b) graph partitioning (such as clustering of power networks), (c) traveling salesman problem (TSP) and its variants, and (d) hard problems on graphs, such as multiway $k$-cut. This viewpoint enables a unified approach to handle a broad class of problems, and therefore efficient MEP based heuristics can be leveraged to obtain high-quality solutions. (ii) Second, we explore MEP based ideas to clustering problems specified by pairwise distances. Many problems in graph theory are indeed specified in terms of the corresponding edge-weight matrices (and not in terms of the nodal locational coordinates). (iii) Finally, our framework allows for inclusion of several constraints in the clustering/resource allocation problems. These constraints may correspond to capacity constraints in case of resource allocations where capacity of each resource is limited, or minimum-tour length constraints in case of traveling salesman problems (TSPs) and its variants. In the second part of this thesis, we describe a novel distributed, robust and optimal control architecture for both DC as well as AC microgrids. Microgrids are grid systems that allow integration of local power sources, such as photovoltaics (PVs), wind, battery and other distributed energy resources (DERs) with local loads connected at the DC-link or the point of common coupling (PCC). Microgrids are hypothesized as viable alternatives to the traditional electric grid. In a microgrid, the main goals of the control design are to regulate voltage and frequency at the PCC and ensuring a prescribed sharing of power among different sources; for instance, economic considerations can dictate that power provided by the sources should be in a certain proportion or according to a prescribed priority. The main challenges arise from the uncertainties in the size and the schedules of loads, the complexity of a coupled multi-converter network, the uncertainties in the model parameters at each converter, and the adverse effects of interfacing DC power sources with AC loads, such as the $120$Hz ripple that must be provided by the DC sources. A systematic control design that addresses all the challenges and objectives for the multi-converter/inverter control is still lacking in the existing literature. The main contribution of the control architecture proposed by us is its capability to addresses all the primary objectives - a) voltage and frequency regulation at the PCC with guaranteed robustness margins, b) prescribed time-varying power sharing in a network of parallel converters, c) controlling the tradeoff between 120Hz ripple on the total current provided by the power sources and the ripple on the DC-link voltage. An important contribution of our work is that our control architecture allows for closed-loop analysis and robust control synthesis for the entire grid network. We introduce a structure in the control architecture, whereby, we show that analysis of the entire multi-component microgrid can be simplified to that of an equivalent {\em single-component} system. Besides analysis, this simplification facilitates using robust and optimal control tools for achieving multiple objectives simultaneously; in contrast in existing architectures, closed-loop analysis for entire networks is typically difficult, and posing optimal control and robustness objectives for the entire network practically untenable.

Graduation Semester

2018-08

Type of Resource

text

Permalink

http://hdl.handle.net/2142/101489

Copyright and License Information

Copyright 2018 Mayank Baranwal

Owning Collections