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

Comments

Post a Comment

Popular posts from this blog

Using the Supervisor Controller Pattern to access View controls in MVVM

Image
As discussed on a StackOverflow post , this is considered bad practice, so only use this when necessary. Step 1: Create a new WPF project Step 2: Add event handling code A number of classes are needed for doing command bindings in MVVM. Create the following classes and add to your Visual Studio project: RelayCommand.cs [code language="csharp"] using System; using System.Windows.Input; namespace SupervisorControllingPattern { public class RelayCommand<T> : ICommand { private readonly Predicate<T> _canExecute; private readonly Action<T> _execute; public RelayCommand(Action<T> execute) : this(execute, null) { _execute = execute; } public RelayCommand(Action<T> execute, Predicate<T> canExecute) { if (execute == null) throw new ArgumentNullException(nameof(execute)); _execute = execute; _canExecute = canExecute; ...
Read more

Getting started with client-server applications in C++

Image
A demonstration of simple Internet client-server applications in C++ (Linux-based). The client application tries to connect to the remote server application using the IP address of the remote server ('localhost' or 127.0.0.1) and the server port number which defaulted to 1234. The server application listens to port number 1234 for a connection request. When the server application receives the connection request it sends the text message "Hello!\r\n" to the client.
Read more

How to send an e-mail via Google SMTP using C#

Image
First things first, some useful StackOverflow links: https://stackoverflow.com/questions/9201239/send-e-mail-via-smtp-using-c-sharp https://stackoverflow.com/questions/17462628/the-server-response-was-5-7-0-must-issue-a-starttls-command-first-i16sm1806350 To demonstrate how this is done I first create a new Visual Studio project: Some example code for sending an email via a Google email account (smtp.goolgle.com) - obviously replace this with email / credentials of your own... I put the code within a try-catch block in order to capture any errors that may occur while attempting this. [code language="csharp"] using System; using System.Net; using System.Net.Mail; namespace EmailSmtp { class Program { static void Main(string[] args) { try { // Credentials var credentials = new NetworkCredential("someEmail@gmail.com", "somePassword"); // Mail message var ...
Read more