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:

http://www.technical-recipes.com/Downloads/Simplex.zip