MemComputing Integer Linear Programming
eScholarship, University of California, 2018
Online
academicJournal
Integer linear programming (ILP) encompasses a very important class ofoptimization problems that are of great interest to both academia and industry.Several algorithms are available that attempt to explore the solution space ofthis class efficiently, while requiring a reasonable compute time. However,although these algorithms have reached various degrees of success over theyears, they still face considerable challenges when confronted withparticularly hard problem instances, such as those of the MIPLIB 2010 library.In this work we propose a radically different non-algorithmic approach to ILPbased on a novel physics-inspired computing paradigm: Memcomputing. Thisparadigm is based on digital (hence scalable) machines represented byappropriate electrical circuits with memory. These machines can be either builtin hardware or, as we do here, their equations of motion can be efficientlysimulated on our traditional computers. We first describe a new circuitarchitecture of memcomputing machines specifically designed to solve for thelinear inequalities representing a general ILP problem. We call theseself-organizing algebraic circuits, since they self-organize dynamically tosatisfy the correct (algebraic) linear inequalities. We then show simulationsof these machines using MATLAB running on a single core of a Xeon processor forseveral ILP benchmark problems taken from the MIPLIB 2010 library, and compareour results against a renowned commercial solver. We show that our approach isvery efficient when dealing with these hard problems. In particular, we findwithin minutes feasible solutions for one of these hard problems (f2000 fromMIPLIB 2010) whose feasibility, to the best of our knowledge, has remainedunknown for the past eight years.
Titel: |
MemComputing Integer Linear Programming
|
---|---|
Autor/in / Beteiligte Person: | Traversa, Fabio L ; Ventra, Massimiliano Di |
Link: | |
Veröffentlichung: | eScholarship, University of California, 2018 |
Medientyp: | academicJournal |
Schlagwort: |
|
Sonstiges: |
|