Supercomputer or Cloud? - Solving Integer Linear Programs in Cloud

OData support
Supervisor:
Dr. Tapolcai János
Department of Telecommunications and Media Informatics

Linear and integer linear programming is a considerable field of optimization for several reasons. Many practical problems in operations research can be formulated as linear programs. Linear and integer linear programming is heavily used in microeconomics and company management, such as planning, production, transportation, technology and other issues. While there are efficient methods to solve linear programs, unfortunately, it has been shown that integer linear programs (ILPs) are NP-hard.

Thus, solving these hard problems often requires supercomputers with huge computing capacity and expensive commercial ILP solvers. Nowadays cloud computing gets a lot of attention, and the attraction of free software and program libraries is much greater than ever before.

During my work, I tried to answer the question, whether clouds can beat supercomputers when it is about solving integer linear programs. I was working on a program suite, which splits huge integer linear programs into smaller subproblems, distributes them in cloud, and manages their parallel solution, doing it all using free ILP program libraries.

The BSc diploma work first introduces the architecture of the program, which was implemented. Then some simulation result collected on supercomputers depict its performance compared to commercial ILP solvers.

Downloads

Please sign in to download the files of this thesis.