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
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:
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
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
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
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:
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:
https://www.technical-recipes.com/Downloads/Simplex.zip
