Close

My Introduction to Linear Programming and GPLK

A project log for Embedded Software Systems!

Collection of small hardware and/or software projects not worthy enough for dedicated project pages, but interesting enough to share!

andrewpowellandrew.powell 10/05/2016 at 03:380 Comments

( An observant reader noticed an inconsistency with the MCFP-CF model! I modified the GMPL code on GitHub and the snippet presented in this log, but I will later modify the text in this log in order to reflect the changes made the to code! )

So, I can already foresee the "Embedded Systems" project becoming a dump for anything and everything related to engineering. I sort of want a place where I can post small blogs on things I find interesting, and HACKADAY just seems like the ideal place. Plus, I find it really helps to understand an idea by explaining it in your own words. Now on to what this log is supposed to be about!


The Idea: Learning Linear Programming and GMPL

Before I elaborate on the idea behind this log, I first want to point out why I am posting this particular log, and also explain some of my long term goals. At some point, I aim to create a project page, detailing the research project I have been working on for my degree. Not going to explain any specifics in this post, but a crucial facet of the work is to implement an on-chip distributed network, optimized for satisfying real-time constraints ( for reasons that will be explained in the future ). The pertinent research area related to that facet is Network-on-Chip ( NoC ), particularly the area having to do with satisfying Guaranteed Services ( GS ). A good introduction to the area can be found here!

However, my background is in Computer Architecture and Embedded Systems! Although I'm not new to the idea of NoCs ( effectively, let's develop on-chip communications to utilize switching networks, such as that on which the Internet depends ), I still have a lot to learn regarding the theory, specifically the area having to do with circuit switching and GS quality of service. More importantly, I need to learn the tools needed to understand a lot of that theory, which brings me to a somewhat new, though fascinating area of mathematical optimization: Linear Programming ( LP ).

From my basic understanding, LP problems are always defined as the optimization ( either maximizing or minimizing ) an objective function with respect to a set of constraints, which are typically linear inequalities but can include equalities.

Actually, I'm not sure whether or not it's okay to count equalities as legitimate constraints, since every source I've checked defines the constraints as a bunch of inequalities. In spite of those sources, though, there does appear to be a lot of problems for which an equality is needed. So I'll go ahead assume equalities are somehow implied!

( until someone much smarter than I decides to yell at me, of course! )

In addition to learning the fundamentals of LP, I want to also test my understanding through trying to recreate the results of various LP problems related to my application. The tool that appears to be most common for modeling and solving LP problems is the GNU Mathematical Programming Language ( GMPL ) ( which is partially derived from AMPL ). I was initially debating whether or not to use MATLAB's LP tools. For now I will stick with GMPL since, from various online postings, it seems the general consensus is that GMPL/GLPK runs comparatively faster and is more common for my application.


The Theory: GLPK API and Multi-Commodity Flow Problem.

I decided to first get practice with both the GLPK API ( C/C++ interface for GMPL ), as well as GMPL. And, as it turns out, programming with the GLPK API is a TEDIOUS experience; many function calls are needed to implement the simplest of models. Worst of all, the API doesn't appear to have any way using set theory, other than importing a GMPL model!

I decided to post a C example I wrote on GitHubGist since I didn't see too many other examples online.

This leads me to the "project" I want to present! As a way to learn how bandwidth across a network can be allocated according to the demands of the network, I decided to implement the Multi-Commodity Flow Problem ( MCFP ), optimized for Concurrent Flow ( CF )!

What does all that mean, though? Well, from my basic understanding, the problem involves a network in which data needs to be transmitted between source and sink nodes. Judging from the references, the network seems to be typically represented as a directed graph, but MCFP does have a variant for which the network is a undirected graph. I simply chose the directed variant in my implementation. Commodity basically represents the data that can be transmitted over the network. Specifically, commodity is defined by a source node, a sink node, and its demand on the network. The source and sink nodes inject and remove commodity from the network, respectively.

So the goal of MCFP is to determine what the flow of each commodity is over each edge in the network that optimizes the objective function, subject to a set of constraints. Since the flow of commodity can represent utilized bandwidth and capacity can represent available bandwidth, it makes sense to implement the CF variant. Thus, the objective is to maximize the lowest percentage of injected commodity over demand ( I could not figure out how to best word this for the life of me lol ).

Last and certainly not least are the constraints. There are basically three. The first ensures the total flow over an edge does not exceed a chosen capacity. The second, I like to refer to as the conservation constraint, in reference to the Law of Conservation of Energy. In short, the net flow of a node ( in other words, the sum of a commodity flowing into and out of the node ), should equal zero if the node isn't a source or a sink. The final constraint ensures the demand is always met. If the node is a source, then the net flow should equal positive demand of the source node's commodity. This represents commodity being injected into the network. If a sink, then the net flow should equal negative demand of the sink node's commodity, instead. This represents commodity being removed from the network.

That's basically it!


The Implementation: GMPL

As for actually solving MCFP-CL for a given network, I of course used GMPL. Since the language is very concise, I'll include the model below as a snippet. But, the full thing with the comments can be found here.

# Multicommodity Flow Problem for Directed Networks, 
## Optimized for Concurrent Flow
set V;                     
set E, within V cross V;    
set K;                      
param s {K}, symbolic in V;
param t {K}, symbolic in V; 
param d {K}, >= 0;         
param c, >= 0;                
var f {K,E}, >= 0;           
var dstar {K}, >= 0;       

# Conservation Constraint. 
s.t. conserve_ct { k in K, v in V } :
    ( sum { w in V : (w,v) in E } f[k,w,v] ) -
    ( sum { w in V : (v,w) in E } f[k,v,w] ) =
        if ( v!=s[k] and v!=t[k] ) then 0
        else if ( v=s[k] ) then -dstar[k]
        else if ( v=t[k] ) then dstar[k];

# Demand Constraint.
s.t. demand_ct { k in K } :
    d[k] <= dstar[k];
    
# Flow Constraint. 
s.t. flow_ct { k in K, (w,v) in E } :
    f[k,w,v] <= dstar[k];

# Capacity Constraint.
s.t. capacity_ct { (v,w) in E } :
    ( sum { k in K } f[k,v,w] ) <= c;
    
# Optimization Objective.
var z, >= 0;
s.t. conc_ct { k in K } :
    dstar[k] / d[k] - z >= 0;
maximize obj : z;

data;

# Example.
set V := A B C;
set E := 
    A B
    B C
    C A;

# Capacity of each edge.
param c := 10;

# Finally, let's define
## the commodities.
param : K : s t d :=
    k0 A C 0.5
    k1 B A 0.5;

Might actually take more time to learn GMPL and possibly AMPL ( but a quick Google search reveals AMPL costs money, so maybe not )! From my brief experience, GMPL seems to have a very concise and clean look to it, which I like a lot when it comes to relating the model back to the mathematical expressions.

Anyways, to test the model, I ran it against several simple flow networks with commodities. Still learning how to automate the generation of more complex topologies and how to easily check such topologies with their commodities. So for now I will only demonstrate a single test case. Let's consider the following directional ring network for which the capacity of every edge is 1.

Let's say the commodities are the following.

Kstd
k0AC0.5
k1BA0.5


After applying the well-known Simplex Method ( with GMPL, of course ), the following is the results.

VariablesResult
f_{k0,(A,B)}0.5
f_{k0,(C,A)}0
f_{k0,(B,C)}0.5
f_{k1,(A,B)}0
f_{k1,(C,A)}0.5
f_{k1,(B,C)}0.5
z ( objective value )1


GMPL also returns the final results for net flow and how much of the total capacity of each edge is utilized! But, ( believe or not ) I'm trying not to let this post go on for too long!

This obvious example is simple to check, though. First of all, summing together the flows for the same edges reveals the capacity constraint is satisfied. Looking at f_{f0,(B,C)} and f_{k1,(C,A)} shows the conservation constraint is met! Finally, the demand constraint is also satisfied, as evidence by the fact the net flow going out of k0's source is equivalent to the net flow going into k0's sink. The same is true for k1.

The objective value of 1 also makes sense. Recall, the objective value describes the lowest ratio between amount of commodity injected into the network over the commodity's demand. Since, the problem is constrained such that the demand is always met, the lowest the objective value can be is 1, implying the amount of commodity injected into the network is at least equal to its demand.

One last check!

What if the demand of a commodity is increased such that a single edge in the ring network wouldn't have the capacity to meet the total demand? In a directed ring network, where there's only one direction commodity can flow, increasing any of the demands will just cause the solver to fail and return an objective value of 0! This failure is actually a good thing, considering there's no other alternative paths in a directed ring!

Annnd, that finally concludes this log!


The Conclusion: These Logs are Way Too Long.

Really need to work on a way to make these posts shorter. But, I sure as hell enjoy writing them! Next time, I will probably break up longer logs into several shorter logs. If you managed to get this far, please look at the references! Pretty much my entire knowledge base on LP and related problems and algorithms came from those references!


The References:

https://www.math.ucla.edu/~tom/LP.pdf

http://www.purplemath.com/modules/linprog.htm

https://www3.nd.edu/~jeff/mathprog/

http://www.es.ele.tue.nl/~kgoossens/Stefan12PHD.pdf

http://www.columbia.edu/~cs2035/courses/ieor6614.S16/multi.pdf

https://en.wikipedia.org/wiki/Multi-commodity_flow_problem

Discussions