A Secure Revised Simplex Algorithm for Privacy-Preserving Linear Programming

Linear programming is one of the most widely applied solutions to optimization problems. This paper presents a privacy-preserving solution to linear programming for two parties when the cost, or objective, function is known only to one party, and the constraint equations are known only to the other party. An algorithm based on Revised Simplex is given that ensures that neither party gains access to the other’s private information. While this has been proposed before, our solution is significantly more efficient for the given data distribution. This enables collaboration among companies in many domains, enhancing efficiency while maintaining competitiveness.

线性规划是优化问题应用最广泛的解决方案之一。本文针对成本（或目标）函数仅一方知晓，约束方程仅另一方知晓的两方线性规划问题，提出了一种隐私保护解决方案。给出了一种基于修正单纯形法的算法，确保双方都无法获取对方的私有信息。虽然之前已经有人提出过类似方案，但对于给定的数据分布，我们的解决方案效率明显更高。这使得许多领域的公司能够进行协作，在提高效率的同时保持竞争力。