Implementation of the Simplex algorithm in Visual C++

An excellent implementation of the Simplex algorithm exists over at Google Code, written by Tommaso Urli:

https://code.google.com/p/cpplex/

Implemented as class library, it relies on no other dependencies other than the C++ Standard Library. I’ve taken this implementation and compiled it as a Visual Studio application. The only slight modification I needed was to insert:

#include <algorithm>

into matrix.cpp then it compiled std::max just fine.

The project is able to load formatted problems in the form:

[METADATA]

name Simple problem
vars 3

[VARIABLES]

0    x1  4
-2   x2  inf
-3   x3  232

[CONSTRAINTS]

1 3 4 > 0
0 0 1 < 1
1 2 0 < 2

[OBJECTIVE]

maximize 1 3 1

Defining your constraints is simple. A constraint of the form:

1 3 4 > 0

Actually means that we want the value of

x1 + 3*x2 + 4*x3

to be greater than zero.

An objective function of the form:

maximize 1 3 1

Attempts to maximize the expression: x1 + 3*x2 + x3. Minimize is also available.

Running the programs requires that the name of the problem is provided. This application comes with three example problems: “small.problem”, “template.problem” and “test.problem”.

The sample problems can be run via the command line eg

simplex1

Alternatively in Visual Studio you can supply the same of the test problem as a command line argument. Right-click on the project, select Properties and set the command line argument in the Debugging section:
simplex2

Here are the test problems and their outputs:

test.problem

[METADATA]

name This is a small test problem
vars 5

[VARIABLES]

0       x1      inf
2.1     x2      4.1
23.4    x3      30
-2.2    x4      3
inf     x5      104.3    

[CONSTRAINTS]

1 3 1 1 0 < 43

[OBJECTIVE]

maximize 1 1 2 1 1

simplex3

template.problem

[METADATA]

name Nome del problema
vars 10

[VARIABLES]

0       variable_1      0.2
0       variable_2      0.1
0       variable_3      1
-2      variable_4      1
-4      variable_5      1
inf     variable_6      inf
inf     variable_7      inf
-4      variable_8      1
4    	variable_9      3
8     	variable_10     inf

[CONSTRAINTS]

1 2 0 0 1 0 2 3 2 1  > 2    
-2 0 0 0 1 1 1 2 5 1 < 10

[OBJECTIVE]

minimize 0 0 0 0 0 0 0 0 1 1

simplex4

small.problem

[METADATA]

name Problema semplice
vars 3

[VARIABLES]

0   x1  4
-2   x2  inf
-3   x3  232

[CONSTRAINTS]

1 3 4 > 0
0 0 1 < 1
1 2 0 < 2

[OBJECTIVE]

maximize 1 3 1

simplex5
brunel.problem
Another example, this time from J E Beasley‘s Operational Research page at the Brunel University website:

http://people.brunel.ac.uk/~mastjjb/jeb/or/morelp.html

An example Linear Programming problem is formulated as follows:

x1 be the number of units of product 1 produced
x2 be the number of units of product 2 produced

where

x1, x2 <= 0

The constraints are:

15x1 + 7x2 <= 20* 60 (machine X)
25x1 + 45x2 <= 15 * 60 (machine Y)
x1 <= 37 demand for product 1
x2 <= 14 demand for product 2

maximize 13x1 + 5x2 - 125

This is encoded into the following brunel.problem file:

[METADATA]

name http://people.brunel.ac.uk/~mastjjb/jeb/or/morelp.html
vars 2

[VARIABLES]

0   x1  37
0   x2  14

[CONSTRAINTS]

15 7 < 1200
25 45 < 900

[OBJECTIVE]

maximize 13 5 -125

The result upon running this is:

simplex6

x1 = 36
x2 = 0

Giving the total profit as 13×1 + 5×2 – 125 = 13(36) + 5(0) – 125 = £343 as anticipated.

Visual Studio 2010 project downloadable from here:
http://www.technical-recipes.com/Downloads/Simplex.zip

Leave a Reply