论文标题
最佳$（0,1）$ - 矩阵完成，具有多数订购的目标（对Pravin Varaiya的内存）
Optimal $(0,1)$-Matrix Completion with Majorization Ordered Objectives (To the memory of Pravin Varaiya)
论文作者
论文摘要
我们提出并检查两个最佳$（0,1）$ - 矩阵完成问题，其中有订购的目标。他们将Gale和Ryser的开创性研究从可行性提高到部分顺序编程（POP），指的是通过部分有序的目标进行优化。我们在电动汽车充电，投资组合优化和安全数据存储中展示了它们的应用。解决此类整数POP（IPOP）问题是具有挑战性的，因为目标值和整数要求之间可能存在不可弥补的性能。然而，我们证明了所有最佳目标值的基本唯一性，并为两个固有的对称iPop问题中的每个问题都确定了两个特定的唯一性。此外，对于每个最佳目标值，我们将相关的最佳〜$（0,1）$ - 矩阵的构造分解为一系列分类过程，分别与“峰值剃须”或“山谷填充”的规则一致。我们表明，与POP的标准订单保留方法相比，所得算法具有线性时间复杂性，并通过数值模拟验证其经验效率。
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.
