SimplexAlgo

Author: Lucas Turci

This is a project made by me with the purpose of solving linear programming problems such as this one:

Maximize f(x) = c₁ x₁ + c₂ x₂ + ... + c_m x_m
Subject to:
a₁₁ x₁ + a₁₂ x₂ + ... + a_1n x_n ≤ b₁
a₂₁ x₁ + a₂₂ x₂ + ... + a_2n x_n ≤ b₂
...
a_n1 x₁ + a_n2 x₂ + ... + a_nn x_n ≤ b_n

My implementation of simplex algorithm solves such problems easily, but not so fast. The assimptotic complexity of simplex best implementation is still exponential, but in average it runs very fast. This implementation does not care to make any major optimization such as to cut some restrictions or stuff like that. In addition, to this moment this program requires that all b_i are non-negative.

How to use

Requirements: g++ compiler with c++ 11 or above

• Clone this repository to your computer, using git clone https://github.com/lucasturci/SimplexAlgo
• Then enter the directory, cd SimplexAlgo
• There is a Makefile in the directory, just write make in your command line to compile.
• To run, ./simplex file, in which file is a text input file described below

Input File

This is where you describe your linear problem.

• The first line contains the function you want to maximize, in the following format:
  [number *] <first variable> {+|-} [number *] <second variable> {+|-} ... {+|-} [number *] <m-th variable>
  
• The second line must be an empty line
  
• The following n lines will be in format:
  [number *] <first variable> {+|-} [number *] <second variable> {+|-} ... {+|-} [number *] <m-th variable> <= <number>
  

Variables can be any string with alphanumeric characters (but they mustn't start with a digit), and number can be any real number.

For example,

file.in

2.5 * a + 3 * c - x

a + c <= 15.5
3 * a - y <= 100