Machine Learning Meliorates Computing and Robustness in Discrete Combinatorial Optimization Problems

Frontiers in Applied Mathematics and Statistics

Hsieh, Fushing¹  Fujii, Kevin¹  Hsieh, Cho-Jui² 

[1] Department of Statistics, University of California, Davis, Davis, CA, USA;Departments of Computer Science and Statistics, University of California, Davis, Davis, CA, USA

关键词: Data Mechanics;    Assignment problem;    Traveling salesman problem;    robustness;    netowk mimicking;   

DOI  :  10.3389/fams.2016.00020

学科分类：数学（综合）

来源: Frontiers

【 摘 要 】

Discrete combinatorial optimization problems in real world are typically defined via an ensemble of potentially high dimensional measurements pertaining to all subjects of a system under study. We point out that such a data ensemble in fact embeds with system's information content that is not directly used in defining the combinatorial optimization problems. Can machine learning algorithms extract such information content and make combinatorial optimizing tasks more efficient? Would such algorithmic computations bring new perspectives into this classic topic of Applied Mathematics and Theoretical Computer Science? We show that answers to both questions are positive. One key reason is due to permutation invariance. That is, the data ensemble of subjects' measurement vectors is permutation invariant when it is represented through a subject-vs-measurement matrix. An unsupervised machine learning algorithm, called Data Mechanics (DM), is applied to find optimal permutations on row and column axes such that the permuted matrix reveals coupled deterministic and stochastic structures as the system's information content. The deterministic structures are shown to facilitate geometry-based divide-and-conquer scheme that helps optimizing task, while stochastic structures are used to generate an ensemble of mimicries retaining the deterministic structures, and then reveal the robustness pertaining to the original version of optimal solution. Two simulated systems, Assignment problem and Traveling Salesman problem, are considered. Beyond demonstrating computational advantages and intrinsic robustness in the two systems, we propose brand new robust optimal solutions. We believe such robust versions of optimal solutions are potentially more realistic and practical in real world settings.

【 授权许可】

CC BY