Fast exact algorithms for optimization problems in resource allocation and switched linear systems
2019-06
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Fast exact algorithms for optimization problems in resource allocation and switched linear systems
Authors
Published Date
2019-06
Publisher
Type
Thesis or Dissertation
Abstract
Discrete optimization is a branch of mathematical optimization where some of the decision variables are restricted to real values in a discrete set. The use of discrete decision variables greatly expands the scope and capacity of mathematical optimization models. In the era of big data, efficiency and scalability are increasingly important in evaluating the performance of an algorithm. However, discrete optimization problems usually are challenging to solve. In this thesis, we develop new fast exact algorithms for discrete optimization problems arising in the field of resource allocation and switched linear systems. The first problem is the discrete resource allocation problem with nested bound constraints. It is a fundamental problem with a wide variety of applications in search theory, economics, inventory systems, etc. Given $B$ units of resource and $n$ activities, each of which associated with a convex allocation cost $f_i(\cdot)$, we aim to find an allocation of resources to the $n$ activities, denoted by $\bm{x} \in \Ze^n$, to minimize the total allocation cost $\sum\limits_{i = 1}^{n} f_i(x_i)$ subject to the total amount of resource constraint as well as lower and upper bound constraints on total resource allocated to subsets of activities. We develop a $\Theta(n^2\log\frac{B}{n})$-time algorithm for it. It is an infeasibility-guided divide-and-conquer algorithm and the worst-case complexity is usually not achieved. Numerical experiments demonstrate that our algorithm significantly outperforms a state-of-the-art optimization solver and the performance of our algorithm is competitive compared to the algorithm with the best worst-case complexity for this problem in the literature. The second problem is the minimum convex cost network flow problem on the dynamic lot size network. In the dynamic lot size network, there are one source node and $n$ sink nodes with demand $d_i, i = 1, \dots, n$. Let $B = \sum_{i=0}^{n}d_i$ be the total demand. We aim to find a flow $\bm{x}$ to minimize the total arc cost and satisfy all the flow balance and capacity constraints. Many optimization models in the literature can be seen as special cases of this problem, including dynamic lot-sizing problem and speed optimization. It is also a generalization of the first problem. We develop the Scaled Flow-improving Algorithm. For the continuous problem, our algorithm finds a solution that is at most $\epsilon$ away from an optimal solution in terms of the infinity norm in $O(n^2\log{\frac{B}{n\epsilon}})$ time. For the integer problem, our algorithm terminates in $O(n^2\log\frac{B}{n})$ time. Our algorithm has the best worst-case complexity in the literature. In particular, it solves the discrete resource allocation problem with nested bound constraints in $O(n\log{n}\log\frac{B}{n})$ time and it also achieves the best worst-case complexity for that problem. We conduct extensive numerical experiments on instances with a variety of convex objectives. The numerical result demonstrates the efficiency of our algorithm in solving large-sized instances. The last problem is the optimal control problem in switched linear systems. We consider the following dynamical system that consists of several linear subsystems: $K$ matrices, each chosen from the given set of matrices, to maximize a convex function over the product of the $K$ matrices and the given vector.This simple problem has many applications in operations research and control, yet a moderate-sized instance is challenging to solve to optimality for state-of-the-art optimization software. We prove the problem is NP-hard. We propose a simple exact algorithm for this problem. Our algorithm runs in polynomial time when the given set of matrices has the oligo-vertex property, a concept we introduce for a set of matrices. We derive several easy-to-verify sufficient conditions for a set of matrices to have the oligo-vertex property. In particular, we show that a pair of binary matrices has the oligo-vertex property. Numerical results demonstrate the clear advantage of our algorithm in solving large-sized instances of the problem over one state-of-the-art global solver. We also pose several open questions on the oligo-vertex property and discuss its potential connection with the finiteness property of a set of matrices, which may be of independent interest.
Description
University of Minnesota Ph.D. dissertation.June 2019. Major: Industrial Engineering. Advisor: Qie He. 1 computer file (PDF); x, 138 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Wu, Zeyang. (2019). Fast exact algorithms for optimization problems in resource allocation and switched linear systems. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/206239.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.