Memories Of An Old Man

LINEAR PROGRAMMING

Shortly after starting work in the Research Department I was ask to see if I could solve a problem that an engineer in Columbia's Pittsburgh office had. The problem was this:

Field operations needed up to 10 different sizes of pipe with different kinds of protective coating when laid in the ground.

The pipe could be purchased from 10 suppliers.

The pipe could be coated at 8 coating facilities.

The shipping costs varied depending upon company suppling the pipe, where it was coated, and the cost of shipping to the final destination, which was based on weight.

Find the cheapest way to purchase, coat, and delivery the pipe to the various Columbia Gas units in the field.

This is a very complicated problem and I wasn't sure how to tackle it so I did a little research at the OSU Math library and found several books on Linear Programming (LP). I learned that LP was developed during World War II to determine, among other things, how many escort ships would be needed for maximum protection of our supply ships crossing the Atlantic Ocean to Europe & England. The most famous problem solved with LP is the "traveling salesman" problem which involves finding the shortest route a salesman should take to cover a certain number of cites with different route between each city with different distances.

One book in particular seemed to have a pretty detailed description of how to solve the problem so I checked out the book, headed back to the office for some serious study. I am not sure how long it took me to figure out the routine necessary to solve the problem but it was not easy. I suspect it was a month or so. But I did do it and wrote a FORTRAN program to solve it. The mathematics was fairly simple, e.g equation and inequalities as shown below.

At that time, about 1968-69, our main frame computer had about 64K of memory, that's correct, you didn't read it wrong, 64K of memory, a tape drive, a high spread chain printer, and a punch card reader to input the program. The computer (PC) I am writing these memories, in 1998, has 128MB of memory, a CD, a zip drive, and a monitor to input program and display results, all of which is about 1,000 times more powerful than the computer I was using in 1969. In 2007 I have a PC with 512MB of memory, a CD-RW drive, 37.2 GB hard drive, HP 5940 printer, and a 17" LCD monitor - quite an up grade!

Back then I had to write the program on coding paper, take the paper to a keypunch machine and type in each line of code on a card one at a time, a very slow process although touch typing did help. But if you made a typing mistake you had to eject the current card, take it out of the tray, hit the NEW CARD key and start over again. Today, you type a program on a monitor screen and if you make a mistake you use the BACKSPACE key to erase it and type in the correct code. Much faster.

After getting the program typed up I would write up a request for computer service, wrap it around the deck of card, and submit it the computer operator. We could not run the computer ourselves where as today we do it on a PC or the PC is attached to the main frame and the job is automatically submitted, run, and return to you.

The computer operator would take one job at a time and put it into the card reader and run the program. The program was printed on the big printer along with the results. No matter how careful you were you make mistakes so the program would not run. Then you looked at the results or error codes, the listing of the program and tried to figure out what was wrong. If you did, it was back to the keypunch, more typing and then submitting the program all over again.

We had about four programmers in the Research Department so everyone could not get their program running at the same time. There was no such thing as a virtual computer, one that can run many programs as the same time. Today this is done by a PC which can run many programs at the same time and switch back and forth such as that done when someone is running a spreadsheet and graphics editor at the same time.

When I first ran the fully de-bugged program, i.e. it would run without errors, the computer operator had to kick it off as it was taking up to much computer time, i.e. more the several hours. So we arranged for it to run over night. The next morning when we came into work, the program was still running!

I got a dump, a hexadecimal listing of all program variables and found that a conditions I was testing to see if the solution was found was very, very small, 0.00000001, but not zero. So I change the condition so that the program would stop when the test-for-completion variable was 0.01 and submitted the program again. I told the operation that the program should complete now and sure enough, in a few minutes it printed the results.

The final program run was completed with actual data and produced a cost for all the Pennsylvania site that was about $40,000 less than what they had paid the previous year. For some reason, the Pennsylvania office didn't use the program in future years.

I believe it was about this time in my life that Barbara and I got divorced, rather I divorced her. About three months later I met Mary Ann, who worked where I worked. To see a bit more about here please see Marriage.

My next major project was a study and recommendation to Columbia's Transmission companies regarding the application of electronics in several areas.