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: [code language="cpp"]#include <algorithm>[/code] into matrix.cpp then it compiled std::max just fine. The project is able to load formatted problems in the form: [code language="text"] [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 [/code] Defining your constraints is simple. A constraint of the form: [code language="text"] 1 3 4 > 0 [/code] Actually means that we want the value of [code language="text"] x1 + 3*x2 + 4*x3 [/code] to be greater than zero. An objective function of the form: [code language="text"] maximize 1 3 1 [/code] 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 [code language="text"] [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 [/code] template.problem [code language="text"] [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 [/code] small.problem [code language="text"] [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 [/code] 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 [code language="text"] x1, x2 <= 0 [/code] The constraints are: [code language="cpp"] 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 [/code] This is encoded into the following brunel.problem file: [code language="text"] [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 [/code] The result upon running this is: x1 = 36 x2 = 0 Giving the total profit as 13x1 + 5x2 - 125 = 13(36) + 5(0) - 125 = £343 as anticipated. Visual Studio 2010 project downloadable from here: https://www.technical-recipes.com/Downloads/Simplex.zip