Threading Race Deque

Following code has been causing problems at a various times and has sent me debugging in a lot of unrelated areas.

private final NavigableSet scenarios = new ConcurrentSkipListSet()

public void fireCompletedScenarios() {
        while (!scenarios.isEmpty()) {
            InMemoryScenarioRecord firstScenario = scenarios.first();
            if (firstScenario.completed()) {
                synchronized (completedScenarios) {
                    completedScenarios.offer(scenarios.pollFirst());
                }
                continue;
            }
            //exit when you find first uncompleted scenario
            break;
        }
    }

There is a navigable set of scenarios, ordered by scenario time. We pull out completed scenarios from it and add it to another queue. We break when we find the first incomplete scenario.

The issue I have been facing is - incomplete scenarios getting into the queue of completed scenarios. As usual, the case does not happen in local environment - happens in non-prod environments -under high load. Hence, it must be some race condition causing the issue.

Finally it stuck to me is the bug in the above code that manifests under high load. The bug is as follows:

The scenarios.first() just gives me access to the first scenario and does not remove it from the navigable set. After the completion check, pollFirst is called to remove it from the set.

This is the bug - under high load - the element returned by first and the element removed by pollFirst are not same!

There can be another incomplete scenario that came in to the set; to the top because it had lower scenario time; but arrived late into the set because of the asynchronicity that existed in this system. This resulted in adding a incomplete scenario returned by pollFirst to the completed queue!

huh! I fixed this over sight and learnt a valuable lesson !

Farey Series

I have been managing to read the book Recreations in Theory of Numbers. A good informal book on Number Theory. Farey series is one of topics I wanted to write a program for. Following is the Groovy code of generating Farey series until the given value of the denominator.

def farey = {
    def a = 1, b = it, c = 1, d = it - 1;
    printf "%d/%d ", a, b
    while (c != 1 || d != 1) {
        printf "%d/%d ", c, d
        z = (int) ((it + b) / d)
        (a, b, c, d) = [c, d, z * c - a, z * d - b]
    }
}

farey(7)

Output: 
1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 

Learning OAuth 2.0

Source of truth for OAuth 2.0 is, of course, the RFC 6749. The language and explanation in RFC is very much comprehensible.

 
     +--------+                               +---------------+
     |        |--(A)- Authorization Request ->|   Resource    |
     |        |                               |     Owner     |
     |        |<-(B)-- Authorization Grant ---|               |
     |        |                               +---------------+
     |        |
     |        |                               +---------------+
     |        |--(C)-- Authorization Grant -->| Authorization |
     | Client |                               |     Server    |
     |        |<-(D)----- Access Token -------|               |
     |        |                               +---------------+
     |        |
     |        |                               +---------------+
     |        |--(E)----- Access Token ------>|    Resource   |
     |        |                               |     Server    |
     |        |<-(F)--- Protected Resource ---|               |
     +--------+                               +---------------+

OAuth 2.0 defines quite a few API endpoints. The RFC provides examples for the request and expected responses for these APIs.

One of the good ways to understand the RFC is build the OAuth endpoints and try out the samples mentioned in it. Apigee Edge support of OAuth 2.0 is a quick help here.

This github project oauth20_apigee contains the proxy and the postman client requests.

Apart from the RFC,following are two good resources about OAuth 2.0

• Good Explanation of OAuth 2.0 By Aaron - OAuth 2 Simplified
• If you wondered (like me) why Authorization Code is required in OAuth 2.0 - Stack Overflow Question

brew install octave fails on OS X - Mountain Lion

Octave installation on Mountain Lion fails during the make install phase with the following error:

 make install
./plot.texi:3957: warning: node `Multiple Plot Windows' is prev for `Printing and Saving Plots' in menu but not in sectioning
 make[3]: *** [octave.info] Error 1
 make[2]: *** [install-recursive] Error 1
 make[1]: *** [install-recursive] Error 1
 make: *** [install] Error 2

The solution seems to be the manual patch indicated here: http://goo.gl/nq0H5b
In summary: --enable-docs=no makes it work.

Post S2 I9100G ICS Upgrade: Only Samsung Logo Left?

I decided to upgrade my Samsung S2 I9100G from Gingerbread to ICS; used the software update on the phone to perform the upgrade; now my phone would boot and show the Samsung logo for eternity!

The only way to get the phone back to work is to revert to Gingerbread! This has to be done manually by downloading the firmware and installing it.

Thanks to this link , it provides a detailed explanation for doing the same.

Appreciate Samsung for such robust update release which only shows their logo after its applied!

Of course, I can visit the Samsung service center in Bangalore which is worse than their upgrade package!

loadClass - JDK 1.6.0_18 vs JDK 1.6.0_27

Recently while implementing a custom class loader, I hit upon a issue related to loadClass method of the Classloader.  The custom classloader code of interest is below.

This classloader worked on JDK 6 Update 27 (dev env) but failed to work on JDK 6 Update 17 (test env).


Its a rare skill to write code in Java that  fails between minor revisions!! :-)

The class loader code was written looking at the Java source code for Classloader. This was the cause of the issue - the custom loader implementation did not adhere to the documented contract for the loadClass method.

The documentation of the loadClass method clearly states

Throws:

ClassNotFoundException - If the class could not be found

While the custom class loader method returns null if the class is not found! So why did it work in latest update of Java?  Following are the Classloader code snippets from the two JDK 6 updates that I have mentioned.

Jdk 1.6 Update 18


Jdk 1.6 Update 27


The if check c==null in the Update 27 made the loadClass method work even though it did not adhere to the documented contract.

The bottom line is to code against documented contract and not look at the implementation to write code!

Analytical Reasoning With Prolog

Last year, I solved the following analytical reasoning problem by hand. Post learning Prolog, I think this is a good problem to solve using a computer! I had a interesting experience doing so.

Problem:

Facts:

1: There are 5 villas in 5 different colors 

2: In each villa lives a person with a different nationality. 

3: These 5 owners drink a certain beverage, smoke a certain brand of cigar and keep a certain pet. 

4: No owner has the same pet, smoke the same brand of cigar or drink the same drink.

Hints:

1: The British lives in a red villa. 

2: The Swede keeps dogs as pets 

3: The Dane drinks tea 

4: The green villa is on the left of the white villa (it also means they are next door to each other) 

5: The green villa owner drinks coffee 

6: The person who smokes Pall Mall rears birds 

7: The owner of the yellow villa smokes Dunhill 

8: The man living in the villa right in the center drinks milk 

9: The Norwegian lives in the first villa 

10: The man who smokes Blend lives next to the one who keeps cats 

11: The man who keeps horses lives next to the man who smokes Dunhill 

12: The owner who smokes Blue Master drinks beer 

13: The German smokes Prince 

14: The Norwegian lives next to the blue villa 

15: The man who smokes Blend has a neighbor who drinks water.

The question is: who keeps the fish?

Prolog Solution:

The following is what i could come up with after serval iterations through code.

Answer to Puzzle:

Following is the output of the prolog program.

1,norwegian,yellow,water,dunhill,cat

2,dane,blue,tea,blend,horse

3,british,red,milk,pallmall,birds

4,german,green,coffee,prince,fish

5,swede,white,beer,bluemaster,dog

Hence the answer is German keeps the fish.

C#: Timer, Deferred Evaluation & GC

Following is the snippet of benign (at least by appearance) code that had been cause one of the bugs we faced recently.

The class schedules the given jobs on a timer. The start time for the jobs is around 10 hours from the point the scheduler Start is executed. The timer fires every 24 hrs periodically.

As unexpected, the timer never fired, not even once in production.

We did not face any issue related to this code in development environment, the only difference was that the delay time and period for the timer were shorter in the unit test.

Key suspect in such code behavior is GC. GC has high probability of execution in a long running process than a short running unit test.

The issue was indeed GC, the timer was being garbage collected hence the timer callback was not being executed.

Here is the detailed analysis of the code.

•  The Loc 1 in the code is a Select expression which is implemented  by deferred execution.
•  The Loc 2 in the code exists to ensure the Select is executed and timer is created/scheduled.
•  The key issue with the code is no reference to the Timer object created is retained.  Hence, the Timer object is garbage collected.
• Even though the Loc 1 seems to indicate that the reference to the Timer is assigned to the _timers field, it's not so. The _timers field holds the reference to the Select iterator. In other words, the lambda code itself.

GetType() on _timers will return System.Linq.Enumerable+WhereSelectListIterator`2 [System.Threading.TimerCallback,System.Threading.Timer]

• If the timer is garbage collected, what is the observed behavior in the Dispose method of the JobScheduler ? 

The foreach loop actually creates new timers as a result of Select execution again and disposes them. 

So the current situation with the code is

• Timer will not be fired if the GC runs.
• Timer created will never be stopped by Dispose if the GC does not collect it.

The solution is to convert the output of the Select iterator using toList()or an equivalent method . This method not only forces eager evaluation but also creates a proper enumerable list of Timer objects - System.Collections.Generic.List`1[System.Threading.Timer]

This is the Gist of the the complete program to observe the issue/code behavior.

Prolog: List Difference

Today I was implementing a Prolog program to find the difference between two lists.

Here is the problem statement and the expected output.

minus([1,2,3,4],[1,3],W).

W=[2,4]

yes

As a beginner in Prolog, I tend use the accumulator based approach to find the solution. Here is what I came up with spending some significant time at the Prolog interpreter and debugger.


minusAcc(L,[],_,L) :- !.
minusAcc([],_,A,A) :- !.
minusAcc([H|T],SL,A,W) :- \+memberchk(H,SL),!,
                            append([H],A,AL),
                            minusAcc(T,SL,AL,W).
minusAcc([_|T],SL,A,W) :- minusAcc(T,SL,A,W).
minus(L,SL,W) :- minusAcc(L,SL,[],W).

This program gives the expected output but does not preserve the order. It actually gives the output in the reverse order because of the inherent recursion in the program.  Following is output generated by this program.

minus([1,2,3,4],[1,3],W).

W=[4,2]

yes

Since, I wrote this routine for use in list sorting, the order did not matter and I decided to live with this program.

Meanwhile, I had a look at the implementation available on the web for the same purpose and I found the following program on stackoverflow very interesting.

minus(L,[],L) :- !.

minus([],_,[]) :- !.

minus([H|T],SL,W) :- memberchk(H,SL),!,minus(T,SL,W).

minus([H|T1],SL,[H|T2]) :- minus(T1,SL,T2).

This program gives the expected output and preserves the order too. This program also uses the classic accumulator (unlike mine) based approach, but here the result itself is the accumulator. I had to trace it on debugger for about 10 mins (this is my 2nd day on prolog) to understand the control flow. It was totally worth it!

Gem of a program! Made my weekend!

BTW, here is the gist of my Day 2 of Prolog using Seven Languages in Seven Weeks!

Installing Io on Snow Leopard

Started on Seven Languages in Seven Weeks . Interesting set of 7 languages. Y'day reached Io - Day One. Had to do some googling around to get Io working on OS X.

In case you intend to do the same, here is the gist of the steps required to get going

• Download Io source from git-repo

sudo git clone git://github.com/stevedekorte/io.git

• Next step is to run the build.sh file in the cloned git  io directory. You might get the following error

~/software/io/libs/iovm/source/IoObject_inline.h:322: error: ‘always_inline’ function could not be inlined in call to ‘IoObject_rawGetSlot_’: recursive inlining

• You need to modify the file  ~/software/io/libs/basekit/source/Common_inline.h change

#define NS_INLINE static __inline__ __attribute__((always_inline)) 
in the section #if defined(__APPLE__)  to
#define NS_INLINE static inline

• Now run the build.sh file again.  Io binary will be ready for use!
• Here is the Vim plugin for Io: http://www.vim.org/scripts/script.php?script_id=2116

Trying REBOL

REBOL was the language I wanted to explore. Today I thought of writing a timezone converter application using REBOL.

The application should be able to convert time from Indian timezone to Munich and Boston timezone. This conversion is related to my current project.

With this weird requirement, I decided to use the most weird way to convert time. I decided to use the timeanddate.com timezone converter to do the conversion. As a result, the application has to make an HTTP GET call to this link and parse the resulting web page to find the converted time.

Summarizing the Approach:

1. Write a REBOL UI application that takes the Indian time as input
2. On click of Convert, makes an HTTP call to the website with input given by the user.
3. Parse the resulting web page and find the converted time.
4. Show the converted time on the UI !!

Here is the REBOL code for the application.

This is a REBOL code for timezone convertor

REBOL
[
Title: "Timezone Convertor IN to BOS & MUN"
 Author: "Srikanth Seshadri" 
]

t-time: to-string now/time

time-get: func [inp-time tz] [
page: reform [
"http://www.timeanddate.com/worldclock/converted.html?hour="inp-time/hour"&min="inp-time/minute"&sec="inp-time/second"&p1=438&p2="tz]
tzurl: to-url page
tz-text: load/markup tzurl
zone-found: false tg-time: now
foreach item tz-text [
if all [string? item zone-found ] [ tg-time: item  break]
if all [string? item any[ find item "(U.S.A" find item "(Germ"] ]  [zone-found: true]
]
tg-time
]

gui: layout [
backdrop effect [gradient 0x1 white]
across
h3 "Timezone Converter IN -> BOS & MUN" black return
lab "Indian Time"
t-time: field t-time 60x24 return
tab
button "Convert Time" [
inp-time: (to-time t-time/text)
if inp-time
[
 boslbl/text: reform ["Time in Boston: " time-get inp-time 43]
 munlbl/text: reform ["Time in Munich: " time-get inp-time 83]
 show boslbl
 show munlbl
]
] keycode [#"^m"] return
boslbl: h4 "[---------------------------------------------------------------------]" return
munlbl: h4 "[---------------------------------------------------------------------]" return
]
view center-face gui

and the output

This is most strange way to do timezone conversion, but the learnings and development was fun; all the effort was worth it!

World War II + India + Java

While exploring Java timezone related API, it was a surprise to me that during the World War II, India(being colony of England) had Daylight Saving Time !

This timezone was in effect from 1-Sept-1942 to 15-Oct-1945. Interestingly, this DST is supported by Java date time API.

DateFormat indiaDtFmt = new SimpleDateFormat("dd/MM/yyyy HH'h'mm");
DateFormat gmtDtFmt = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

indiaDtFmt.setTimeZone(TimeZone.getTimeZone("Asia/Calcutta"));
gmtDtFmt.setTimeZone(TimeZone.getTimeZone("GMT"));

Date worldWarIIDate = indiaDtFmt.parse("02/02/1944 06h30");
Date nonWorldWarIIDate = indiaDtFmt.parse("02/02/2006 06h30");

System.err.println(gmtDtFmt.format(worldWarIIDate) +" GMT");
System.err.println(gmtDtFmt.format(nonWorldWarIIDate) +" GMT");

The above code produces the following output.

1944-02-02 00:00:00 GMT
2006-02-02 01:00:00 GMT

So the during the World War II, India was in the timezone +4.30 GMT compared to the normal timezone of +5.30 GMT.

This also mean the horoscopes of the people born in India during the World War II need to take this DST into consideration. These people include celebrities like Ilaiyaraaja,Azim Premji,Amitabh Bachchan etc.

Obviously this well known to Astrologers.Here is one of the links for war-time correction for horoscopes. Another link for war time correction across the world.

Auto Fare Converter

New Auto fare in Bangalore is in effect from Aug 1, 2010. But, Autos have been given 2 month time period to change their meters.

As a result, commuters are expected to know the fare conversion from old to new. Either trust the Auto Driver or have a print of the fare conversion table published.

So I quickly wrote a mobile application to do the conversion. I wrote 2 versions, one android version and other Java ME (MIDP 2.0) application.

Here are the links to the application installables

1. Java Me (MIDP 2.0) App: http://sriki77-blog.googlegroups.com/web/AutoFareMe.jar

2. Android App: http://sriki77-blog.googlegroups.com/web/AutoFareDroid.apk

Application Usage:

1. Enter the current fare in the meter.
2. Click Convert button.
3. The amount you need to pay, the new fare, will be shown.

BMTC Bus Ticket Cost Calculation

In a recent travel through BMTC bus to my office, I was involved in a big fight between another software engineer and the bus conductor on - how the ticket price was calculated? The software engineer did not know Kannada and the bus conductor could explain in the English. I served as the translator in that heated argument :)... here is the info how the ticket price is calculated.

Note: The calculation is performed by the ticketing machine given to the bus conductor so the conductor cannot cheat you!

BMTC divides the routes into stages. Following is the 'Fare Table' of BMTC Bus No 45. You can get the 'Fare Table' for your route from the conductor....Please Ask!

FARE TABLE-010
Stage	Name	Fare
1	KAMAKYA	0.00
2	KATTRIGUPPE	5.00
3	HOSAKERE HALLI	9.00
4	BANK COLONY	10.00
5	GANESH BHAVAN	13.00
6	CHAMARAJPET	15.00
7	GOODS ROAD	16.00
8	KBS	16.00

Now the stage you climb the bus is the Stage 1 for you and of course the stage you get off is the last stage for you. Lets see the following examples of fare calculation with the previous assumption.

Fare from

• KAMAKYA to KBS = Stage 8 - Stage 0 = 8 Stages crossed = Rs 16
• BANK COLONY to GOODS Road = Stage 7 - Stage 4 = 3 Stages Crossed = Rs 9
• GOODS ROAD to KBS = Stage 8 - Stage 7 = 1 Stage crossed = Rs 5

Algorithmically,


List stageList=[KAMKYA...KBS]
List fareList=[0..16]
int start= stageList.indexOf[YOUR START STAGE]
int end = stageList.indexOf[YOUR END STAGE]
Fare= fareList[end-start]

Hope the calculation is clear!

Reading Java Concurrency

The j.u.c package added to Java in 1.5 introduced me to the world of Concurrency research itself. Somehow i never thought of looking to this package beyond Executors class.

Here is the study plan for that worked for me...

1. Locks, Conditions And Fairness
2. Understanding the Java Memory Model and its fix by JSR 133
3. Happens-Before and volatile.
4. LL/SC, CAS concepts
5. Atomic package
6. Concurrent Data Structures & Synchronizers
   
7. Executors,Futures and other threading concepts.

People & Forums:

1. Articles by Brian Goetz, Doug Lea
   
2. Java concurrency Interest group.
   

Two useful books:

1. Concurrent Programming In Java by Doug Lea.
2. Java Concurrency in Practice By Brian Goetz
   

rmToMp3.pl

Here is the perl script to convert .rm files to .mp3 format on linux. Needed this script since my DVD player cannot play .rm files. Script needs the following software to work

1. Perl
2. mplayer
3. lame
4. wget

The script can download rm or ram files and then process the download .rm files to produce the .mp3 file.

#!/usr/bin/perl -w
use strict;

BEGIN{
$\="\n";
}

&usage if @ARGV!=1;
my $fileName=shift;
&usage if ($fileName !~ m#\.(ram|rm)$#);
&process_ram($fileName) if ($fileName =~ m|\.ram$|);
&process_rm($fileName) if ($fileName =~ m|\.rm$|);


sub usage(){
print STDERR "usage: $0 filename.rm/ram\n";
exit 1;
}

sub process_ram(){
my $fileName=shift;
$fileName=&processUrl($fileName);
open RAM_FILE, $fileName || die "Failed To Process File: $!";
while(){
 chomp;
 chop if ~ m/\r$/;
 $_ = &processUrl($_);
 &convertToMp3($_);
}
close RAM_FILE;
}

sub process_rm(){
my $fileName=shift;
$fileName=&processUrl($fileName);
&convertToMp3($fileName);
}

sub convertToMp3(){
my $fileName=shift;
chomp($fileName);
chop($fileName) if $fileName =~ m/\r$/;
print "Processing File...$fileName";
my ($dirName,$baseName)=&dirname($fileName);
$baseName =~ s/\.rm/.mp3/;
die "Invalid File: ${fileName}" unless(-e $fileName);
`mplayer $fileName -ao pcm 2>/dev/null`;
`lame -h -b 128 audiodump.wav $dirName/$baseName`;
`rm audiodump.wav`;
}

sub dirname(){
return (".",$_[0]) unless $_[0] =~ m|^/|;
return $_[0]=~ m|(.*/)(.*)$|;
}
sub processUrl(){
my $fileName=shift;
chomp($fileName);
if(&isUrl($fileName)){
 &download($fileName);
 return $fileName =~ m|.*/(.*)$|,$1;
}
return $fileName;
}

sub isUrl(){
$_[0] =~ m/^http.*/;
}

sub download(){
print "Downloading File...$_[0]";
system("wget -c $_[0]")==0 || die "Failed to download file: $_[0]";
}

Encroachers Hammering Project

Recent anti-encroachment drive of Mysore is an example of admirable planning and execution. The drive was directed and managed by the MCC commissioner K. S Raykar.

Planning Phase:Almost 6 months

a) to get approvals from higher ups including district minister Shobha Karandlaje

b) to develop project execution plan.

Departments Involved: MCC, MUDA, Mysore Police (KSRP, CAR, DAR...etc), Telecom Department

Project Leads: K.S Raykar( MCC Commissioner), Manivannan (DCP), Sunil Agarwal (Police Commissioner)

Project Team Structure/Resourcing:

Commanded by: 2 teams of MUDA and MCC

Executed By: 27 teams of workers!!!

The team organization and composition of each team is shown below.

click to enlarge

Risks/ Risk Mitigation:

Stay Order from Court: The operation was started on a Sunday, early in the morning - no court is open at that time.

Influence from elected representatives: All the phone lines, land line and mobile, were jammed with help of Telecom providers - physical presence required for any kind of influence.

People gathering to protest: Jamming of phone lines prevent mobilization of people. Also, 500 policemen providing security would deter anyone raising voice.

Result: More than 450 encroachments cleared by noon!

Issues Encountered: There was protest by the elected representatives at the demolition site. The threat of arrest, and few arrests, by the police was enough to diffuse the crowd.

Post Execution: MCC Commissioner goes on a 3 day sick leave from Monday – leaving all the encroachers and their supporters with the rubble!

A Geyser Weekend

This weekend has been a Geyser weekend. All the weekend I was hunting for a geyser to buy. I realized this is not an easy task considering the kind of stuff you need to look for. Here is a small checklist of stuff you need to be aware for buying a geyser in India.

Capacity: 25-15 liters Storage - This is enough for a bathroom geyser in most household of 4 to 6 ppl. The decision in this case has to be based on the requirement since the cost difference between a 25 ltr and 15 ltr model is Rs 400.

Plastic Body (ABS) Acrylonitrile Butadiene Styrene (C₈H₈• C₄H₆•C₃H₃N)_n plastic has very good electrical insulation properties.

Copper Drum - Copper has special anti corrosive properties that prolongs the life of the water heater. This is useful for hard water areas.The heat retention in Copper Drum is more than that of stainless steel.

Pressure - It is recommended to select a heater with pressure withstanding capacity of 6 Kg/cm² and above in case of high rise apartments where the pressure can build-up due to water inlet. This might be due to a pressure pump used for water or water gushing down from the overhead tank.

Adjustable Temperature - Ideal water temperature for a bath is 40- 45 degrees. This would save some money the electric bill!!

Thermal Cut-out - A fail-safe device to prevent over heating and boiling

Pressure cum vacuum release–prevents build up of excessive pressure (by releasing water) or vacuum (sucking in air) inside the tank.

Semi return device – prevents dry heating of the element by cutting off flow from the tank- ensuring that element is always immersed in water.

2-in-1 pressure cum release valve - Ensures positive and negative pressure is not created inside the tank

Ceramic Heating Element - No electric shock. It is a cartridge type element that is not in contact with water. Also the heat transfer is over a much larger surface area. The result- longer elements, life, lower salt deposits, hence ideal for hard water areas, easier to replace without draining the water.

PUF Insulation - Poly Urethene Foam prevents heat loss, retains heat longer.


Certifications & Warranty
ISI/BIS certification - A must india.
Warranty period for 5 years.
IEC international certification .
And of course 5 star energy rating!!

I happened to select a water heater with most of theses specifications - 2 years down the line i will be evaluating these criteria :)

Solving a Linear Programming Problem

Operations Research (OR) is one of the key constituents of analytics. Solving a Linear Programming Problem (LPP) is core to OR. In one of my projects we have used a Simplex solver to choose an optimal solution from a set of available solutions. Its quite interesting to see a real life LPP.

We use the SYMPHONY an open source generic MILP (Mixed-Integer Linear Programs) solver from COIN-OR.

This solver takes two inputs

• Problem model file: The Problem Model file contains the formulation of the LPP to be solved. The file uses GMPL (a subset of AMPL) a modeling language for Mathematical Programming.
  

• Input data file:This file contains the input data of the problem to be solved.

Equipped with this information I decided to solve one of the 6th Semester Engineering LPP problems.(I still have my 6th Sem OR notes!!)

Problem Statement:
A small scale hardware production plant produces Nuts, Bolts and Rivets. A box of Nuts fetches a profit of Rs 20 per fortnight. Profit per fortnight from a box of Bolts and Rivets is Rs 6 and Rs 8 respectively. A box of Nuts requires 8 hrs of Milling, 2 hrs of lathe time and 4 hrs of threading time. A box of Bolts requires 2 hrs of Milling, and 4 hrs of threading time. A box of Rivets requires 3 hrs of milling and 1 hr of lathe time. Further milling, threading and lathe can operate 250 hrs, 150hrs and 50hrs per fortnight. Find an optimal solution to maximize the profit per fortnight of production plant.

Mathematical Formulation:
Lets formulate the problem to be solved. Let x₁, x₂, x₃ represent the optimal quantities of production of the Nuts, Bolts and Rivets per fortnight.

The objective and constraints formulated can be easily derived from the problem statement.

Objective: Maximize 20 x₁ + 6 x₂ + 8 x₃

Milling Constraints:
8 x₁ + 2x₂ + 3x₃ <= 250

Threading Constraints:
4 x₁ + 3x₂ + 0x₃ <= 150

Lathe Constraints:
2 x₁ + 0x₂ + 1x₃ <= 50

Model File:

Now we have to represent our mathematical formulation in way the Symphony solver can understand. Following is the formulation of the same problem in GMPL format.

Filename: HardwarePlant.mod

/*Input Data we need to Solve*/

/* Input Set of products */
set products;

/* Gains of the product */
param gain{i in products};

/* Milling Requirements of the product */
param milling{i in products};

/* Lathe Requirements of the product */
param lathe{i in products};

/* Threading Requirements of the product */
param thread{i in products};

/* Milling Limit*/
param millingLimit;

/* Threading Limit*/
param threadLimit;

/* lathe Limit*/
param latheLimit;


/*Variable Declarations*/
var x{i in products}, >= 0;

/*Objective*/
maximize profit: sum{i in products} gain[i]*x[i];

/*Constraints*/
subject to millingMachine: sum{i in products} milling[i]*x[i] <= millingLimit;  

subject to latheMachine: sum{i in products} lathe[i]*x[i] <= latheLimit;  

subject to threadMachine: sum{i in products} thread[i]*x[i] <= threadLimit;  

end;  

At first we take as input a set of products. Then we need the gain for each of the products. Next, we need the milling, threading and lathe requirements for the product. We also need the limits for each of the machines. Thats all the input we need to find an optimal solution.

We define a variable set x representing the quantities of each of the product. We need to determine the values of x.

Further we define the objective and constraints to choose the optimal solution.

Input Data File:

Following is the input data file from our problem statement to be used with the model file.

Filename: HardwarePlant.dat

data;

set products:= Nuts Bolts Rivets;


param gain:=Nuts 20
     Bolts 6
           Rivets 8 ; 

param milling:=Nuts 8
              Bolts 2
              Rivets 3;

param thread:=Nuts 4
             Bolts 3
             Rivets 0;

param lathe:=Nuts 2
            Bolts 0
            Rivets 1;

param millingLimit  := 250;
param threadLimit   := 150;
param latheLimit    := 50;

end;

First we provide the input set of products. This can be strings representing the name of the products.Name of the product acts as an index for the rest of the parameters

Next we specify the gain per fortnight. From the model file its evident that we need gain for every product. We specify the name of the product and gain. As mentioned above the name serves as an index into the gain set.

We use the similar approach as above and specify the values for milling, threading and lathe requirements.

Finally, we specify the scalar values for the limits.

Execution:
Using the model and input file, Symphony solver can be executed as follows

symphony -F HardwarePlant.mod  -D HardwarePlant.dat

The execution produces the following output (only the relevant part shown)

Solution Cost: 700.000
+++++++++++++++++++++++++++++++++++++++++++++++++++
Column names and values of nonzeros in the solution
+++++++++++++++++++++++++++++++++++++++++++++++++++
x[Bolts]     50.000
x[Rivets]     50.000

Analyzing the output:
The solver is recommending for production of 50 bolts, 50 rivets and no nuts in a fortnight. And the optimal profit is Rs 700 per fortnight.
This is answer that matches the hand solved solution in my notes!!

SOA Layering

The following links from Bill Poole is a must read for the SOA developers and architects.


http://bill-poole.blogspot.com/2008/05/layered-service-models-are-bad.html

http://bill-poole.blogspot.com/2008/05/layered-service-models-are-bad_20.html

Very impressive arguments. Thanks to Sriram for sending me these links.