Integer matrix completion is a long-studied mathematical topic for finding a required matrix based on partially observed information, which aids in modeling and solving various engineering problems. Majorization, meanwhile, is a simple but important ordering, widely used in diverse fields. In this thesis, we elaborate on the interactions between (0, 1)-matrix completion and majorization, and their applications in smart grids.

Firstly, we study a class of (0,1)-matrices with prescribed row/column sums and fixed zeros. In the form of the nonnegativity of a derived structure tensor, we establish a necessary and sufficient condition under which such a class is nonempty. Moreover, we design a tensor-based combinatorial algorithm to construct a required matrix when the class is nonemp...[ Read more ]

Integer matrix completion is a long-studied mathematical topic for finding a required matrix based on partially observed information, which aids in modeling and solving various engineering problems. Majorization, meanwhile, is a simple but important ordering, widely used in diverse fields. In this thesis, we elaborate on the interactions between (0, 1)-matrix completion and majorization, and their applications in smart grids.

Firstly, we study a class of (0,1)-matrices with prescribed row/column sums and fixed zeros. In the form of the nonnegativity of a derived structure tensor, we establish a necessary and sufficient condition under which such a class is nonempty. Moreover, we design a tensor-based combinatorial algorithm to construct a required matrix when the class is nonempty. We show by simulation that such an algorithm is efficient, especially when the number of rows is sufficiently large compared with the number of associated tensor elements. Furthermore, the tensor condition addresses the supply/demand matching of the multiple-arrival multiple-deadline (MAMD) differentiated energy services. We propose the MAMD services for flexible loads requiring constant power for specified durations. Such loads are indifferent to the actual power delivery time as long as the duration requirements are satisfied between the specified arrival times and deadlines. We also study the market implementation of MAMD services and show that selfish market participants can attain the maximum social welfare distributedly.

Secondly, we propose two closely linked Integer Partial Order Programming (iPOP) problems, whose vector-valued objectives are ordered by majorization. After establishing their connections with optimal (0, 1)-matrix completion problems, we propose a (0, 1)-matrix completion approach to addressing the particular iPOP problems. Such a specialized approach performs better than the common order-preserving scalarization method for POP. From an application perspective, we derive the two fundamental iPOP problems from unstructured resource allocation in scenarios involving smart grids, portfolio optimization, and secure data storage. When the accessible resources of distinct demands are nested or intersect at a shared pool, we formulate several generalized iPOP problems of structural constraints, which are shown to be equivalent to optimal (0, 1)-matrix completion problems with a staircase or an overlapping pattern of unfixed positions. After exploiting the structural information, we solve the structural iPOP programs in a unified framework by decomposing them into a sequence of fundamental iPOP problems.