FPGA Based Integer Linear Program Solver

Type: Master's Assignment
Contacts: Albert MolderinkBert Molenkamp
Project: Islanded House
Location: CAES, University of Twente

Introduction

Linear Programming (LP) is a scientific computing application which provides a general framework for describing optimization problems as a linear objective function and a set of linear constraints. It is used for a wide range of optimizations problems. The most used solving algorithm, the simplex algorithm, has a exponential complexity. A special type of LP is Integer Linear Programming (ILP), meaning that the decision variables are integers. This ILP problem is often solved by iteratively solving an LP, adding constraints based on the solution (branch-and-bound and branch-and-cut) and solve the new LP again until all variables in the solution have an integer value. Because of this iterative process solving an ILP is in general an NP-complete problem. Solving an ILP problem can take a few seconds up to several days.

An FPGA is in nature suitable for algorithms with a lot of parallellism. The simplex algorithm and an iterative ILP solver have potential to exploit parellellism. Therefore, an FPGA might solve an ILP problem much faster than (free and commercial) GPP solvers.

Assignment

Developing an ILP solver for an FPGA is a challenging assignment. When do you want to exploit parallellism and when is a serial implementation with less control a better option? A lot of research questions raise for this assignment:

  1. How to implement the simplex algorithm? It should be a flexible implementation because contraints are removed and added during the branch-and-bound and the branch-and-cut stage. How much parallellism can be exploited?
  2. When to switch from branch-and-cut to branch-and-bound? What is the trade-off between control-based optimizations and regularity of the algorithm?
  3. What is the best architecture and control method? The simplex algorithm is a computational intensive building block, but the branch-and-bound and branch-and-cut are more control oriented, or require at least more control. Furthermore, the simplex is executed multiple times with adjusted constraints. Are there multiple simplex solving blocks or are they solved sequentially?
  4. What are the limitations concerning memory and size of the ILP? What are the consequences of communication with an external memory on the execution time and the architecture itself?
  5. What is the execution time reduction in comparison with standard free solvers and the commercial CPLEX solver?
Free Joomla Templates designed by Web Hosting Top