Optimization/Graph GUI Utility in MATLAB

This project deals with different Optimization and Graph algorithms and creating a user friendly GUI utility for users. We’ve used MATLAB for the same. It was done a long time ago in 2011 with my friend Vipul Pandey, a fellow Bitsian.

The different algorithms covered are :

All Slack Primal Simplex
Big M Method Simplex
Two Phase Method Simplex
Dual Simplex
Generalized Simplex
Floyd Warshall (Shortest Path)
Kruskal (Minimum Spanning Tree)
Fractional Knapsack
Task Scheduling
Complete Graph
Graph from Adjacency Matrix

The user has to just run the “start.m”  file and he is presented the Menu below :

I’ll go through all of these algorithms and their respective GUIs.

1) All the Simplex Algorithms (top 5) :

First, you are asked for the number of variables and constraints in your problem

Next, you are presented with this input table :

The appropriate output is showed in the tabular format, as we solve on paper :

We’ve also taken care of all the special cases such as

• Alternate Solution
• Unbounded Solution
• Infeasible Solution

The most important part, error handling. Any wrong input by the user is taken care of . For instance,

2) Floyd Warshall Shortest Path Algorithm :

First, you are asked for the number of vertices and edges in the graph :

You can then enter the edge information in a much simpler way compared to adjacency matrix :

The program then outputs the given graph and the Shortest Path Matrix :

3) Kruskal’s Algorithm Minimum Spanning Tree Algorithm :

You are asked to enter the Graph information just like you did in Floyd Warshall. Once this is done, the final output is the minimum spanning tree. For instance, consider this information for some graph :

The minimum spanning tree for the above graph is :

4) Fractional Knapsack Algorithm :

You are asked for the total number of items.

Once this is done, you are presented this input table. Please note that the Max Weight field is editable as well.

The output is :

5) Task Scheduling Algorithm :

You are first asked for the total number of  jobs to be scheduled :

Then comes the input table where you enter the start and end time for all the jobs.

The algorithm calculates the minimum number of machines needed to schedule all the jobs and also the timetable :

6) Complete Graph :

This is pretty simple one. You simply enter the number of vertices and the complete graph with that number of vertices is drawn.

It can be used to explain what a complete graph is to students who’ve started learning graph theory.

For example, a complete graph on 10 vertices would be :

7) Graph from Adjacency Matrix :

This one too is a pretty simple one. You enter the adjacency matrix and this program draws the graph for you. You are first asked to enter the number of vertices and then the adjacency matrix. For 7 vertices :

Empty cells stand for a 0. Also, if you enter a 1 at (2,1) then the program automatically adds a 1 to (1,2), thus saving the trouble for user to do it. The graph for this matrix is :

—————————————————————————————————————————————————–

WHERE’S THE CODE ?

Here’s the link to the code :

https://github.com/chiragragarwal/Optimisation

—————————————————————————————————————————————————–

Thus, we aim at making this code available to everyone and these algorithms can be used to  help students understand them in a much better way.

Any suggestions are welcome

About these ads