Optimal (0,1)-Matrix Completion with Majorization Ordered Objectives (To the memory of Pravin Varaiya)

作     者：Mo, Yanfang Chen, Wei You, Keyou Qiu, Li 

作者机构：School of Data Science City University of Hong Kong Tat Chee Avenue Kowloon Hong Kong Department of Mechanics and Engineering Science State Key Laboratory for Turbulence and Complex Systems Peking University Beijing100871 China Department of Automation Beijing National Research Center for Information Science and Technology Tsinghua University Beijing100084 China Department of Electronic and Computer Engineering The Hong Kong University of Science and Technology Clear Water Bay Kowloon Hong Kong 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2022年

核心收录：

主　　题：Digital storage 

摘      要：We propose and examine two optimal (0,1)-matrix completion problems with majorization ordered objectives. They elevate the seminal study by Gale and Ryser from feasibility to optimality in partial order programming (POP), referring to optimization with partially ordered objectives. We showcase their applications in electric vehicle charging, portfolio optimization, and secure data storage. Solving such integer POP (iPOP) problems is challenging because of the possible non-comparability among objective values and the integer requirements. Nevertheless, we prove the essential uniqueness of all optimal objective values and identify two particular ones for each of the two inherently symmetric iPOP problems. Furthermore, for every optimal objective value, we decompose the construction of an associated optimal (0,1)-matrix into a series of sorting processes, respectively agreeing with the rule of thumb peak shaving or valley filling. We show that the resulting algorithms have linear time complexities and verify their empirical efficiency via numerical simulations compared to the standard order-preserving method for POP. Copyright © 2022, The Authors. All rights reserved.