Machine learning meliorates computing and robustness in discrete combinatorial optimization problems.
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 d...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Frontiers Media S.A.
2016-11-01
|
| Series: | Frontiers in Applied Mathematics and Statistics |
| Subjects: | |
| Online Access: | http://journal.frontiersin.org/Journal/10.3389/fams.2016.00020/full |
| _version_ | 1811197529027510272 |
|---|---|
| author | Fushing Hsieh Kevin Fujii Cho-Jui Hsieh |
| author_facet | Fushing Hsieh Kevin Fujii Cho-Jui Hsieh |
| author_sort | Fushing Hsieh |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T01:16:20Z |
| format | Article |
| id | doaj.art-45d9c842cc76490e9abad0de47fe9cfa |
| institution | Directory Open Access Journal |
| issn | 2297-4687 |
| language | English |
| last_indexed | 2024-04-12T01:16:20Z |
| publishDate | 2016-11-01 |
| publisher | Frontiers Media S.A. |
| record_format | Article |
| series | Frontiers in Applied Mathematics and Statistics |
| spelling | doaj.art-45d9c842cc76490e9abad0de47fe9cfa2022-12-22T03:53:57ZengFrontiers Media S.A.Frontiers in Applied Mathematics and Statistics2297-46872016-11-01210.3389/fams.2016.00020229654Machine learning meliorates computing and robustness in discrete combinatorial optimization problems.Fushing Hsieh0Kevin Fujii1Cho-Jui Hsieh2UC DavisUC DavisUC DavisDiscrete 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.http://journal.frontiersin.org/Journal/10.3389/fams.2016.00020/fullrobustnessAssignment problemTraveling salesman problemData Mechanicsnetowk mimicking |
| spellingShingle | Fushing Hsieh Kevin Fujii Cho-Jui Hsieh Machine learning meliorates computing and robustness in discrete combinatorial optimization problems. Frontiers in Applied Mathematics and Statistics robustness Assignment problem Traveling salesman problem Data Mechanics netowk mimicking |
| title | Machine learning meliorates computing and robustness in discrete combinatorial optimization problems. |
| title_full | Machine learning meliorates computing and robustness in discrete combinatorial optimization problems. |
| title_fullStr | Machine learning meliorates computing and robustness in discrete combinatorial optimization problems. |
| title_full_unstemmed | Machine learning meliorates computing and robustness in discrete combinatorial optimization problems. |
| title_short | Machine learning meliorates computing and robustness in discrete combinatorial optimization problems. |
| title_sort | machine learning meliorates computing and robustness in discrete combinatorial optimization problems |
| topic | robustness Assignment problem Traveling salesman problem Data Mechanics netowk mimicking |
| url | http://journal.frontiersin.org/Journal/10.3389/fams.2016.00020/full |
| work_keys_str_mv | AT fushinghsieh machinelearningmelioratescomputingandrobustnessindiscretecombinatorialoptimizationproblems AT kevinfujii machinelearningmelioratescomputingandrobustnessindiscretecombinatorialoptimizationproblems AT chojuihsieh machinelearningmelioratescomputingandrobustnessindiscretecombinatorialoptimizationproblems |