pushmedia1

9.22.2004

When does Simplex get out of hand?

In 1972, Klee and Minty gave an example of a linear programming problem in which the polytope P is a distortion of anThis is a quote from wikipedia. Maybe I should dig up that paper...n-dimensional cube. They showed that the simplex method as formulated by Danzig visits all 2^{n}vertices before arriving at the optimal vertex.

Duality in LP
I'm trying to get my head around duality. Essentially, every linear program has a dual program. If in the original problem, you're maximizing, in the second you're minimizing. Also, you swap the 'costs' and the constraints. The costs become constraints and the original constraints go into the objective function.

Economically, duality means that the problem of maximizing profit is the same as the the problem of minimizing costs.

Of course, a system of constraints usually has many feasible solutions. One result of duality is that if one of the problems has a solution than its dual will have a solution, too. A more interesting result about duality is that if the maximizing problem has a solution then the value of its objective function will be less than or equal to the value of the objective function for some solution to the minimizing problem.

This last result, called the weak duality theorem, can be used to show that the optimal solution for the maximizing problem results in a value of its objective function equal to the value of the objective fuction for the minimizing problem at its optimal solution. In this way, you can know if you have an optimal solution by checking if the dual problem gives an equal value of the objective function.

I'm still wrapping my head around all this and I certainly don't understand the math.... There's a great presentation I grabbed off a google search.

Economically, duality means that the problem of maximizing profit is the same as the the problem of minimizing costs.

Of course, a system of constraints usually has many feasible solutions. One result of duality is that if one of the problems has a solution than its dual will have a solution, too. A more interesting result about duality is that if the maximizing problem has a solution then the value of its objective function will be less than or equal to the value of the objective function for some solution to the minimizing problem.

This last result, called the weak duality theorem, can be used to show that the optimal solution for the maximizing problem results in a value of its objective function equal to the value of the objective fuction for the minimizing problem at its optimal solution. In this way, you can know if you have an optimal solution by checking if the dual problem gives an equal value of the objective function.

I'm still wrapping my head around all this and I certainly don't understand the math.... There's a great presentation I grabbed off a google search.

9.10.2004

Ken Jennings news
Confirmation of the rumor reported at kottke.org.

I just recieved this email from a friend:

I just recieved this email from a friend:

My sister was on Jeopardy! so we went down to L.A. Wednesday to see the taping. Her episodes will air the first week of December or thereabouts.

And yes, Ken got beat the day before we saw the tapings. My sister said that she and the other contestants were all standing around in the morning nervously wondering "where's Ken? anyone seen Ken? does he not have to come in with the rest of the contestants anymore?" until a security guard took pity on them and said "Ken got beaten yesterday" and then they all cheered.

9.09.2004

Estimations
I think I did pretty well. I really screwed the pooch on the number of 'petrol' stations in the UK. I was guessing 1 per 1000 folks, having estimated that there is 100M Britons (hence my guess of 100k). It turns out that using the gas station density in a small, rural US town overestimates the density in the UK by about 10X. Who knew... Well, probably most people.

BTW, Chris Lightfoot comments on the results from the quiz.

BTW, Chris Lightfoot comments on the results from the quiz.

Application requirements - UC Davis
App deadline: 12/15

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

Application requirements - George Mason
App deadline: 2/1

Materials:

- 2 letters of rec

- transcripts

- gre

Materials:

- 2 letters of rec

- transcripts

- gre

Application requirements - Stanford
App deadline: 1/5

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

Application requirements - UCSD
App deadline: 1/14

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

Application requirements - Chicago
App deadline: 12/28

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

Application requirements - Berkeley
App deadline: 12/15

Materials deadline: 1/10

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

- optional: resume and writing sample

Materials deadline: 1/10

Materials:

- 3 letters of rec

- transcripts

- gre

- sop

- optional: resume and writing sample

9.07.2004

OR jobs - more stats

Message: go east for the jobs, come west for the money...

- mean salary - $60,890
- top paying industry - pharmaceuticals
- mean salary in that industry - $103,460 (wow!)
- Cities with highest concentration of these jobs - Huntsville, AL and D.C.
- Cities with highest pay - Bakersfield, CA and San Jose, CA

Message: go east for the jobs, come west for the money...

stats on OR postions
Highlights of OR related jobs from the BLS:

- there were about 62,000 OR jobs in 2002
- 4 out of 5 government OR jobs are in the military
- many private sector OR jobs are defense related
- demand growth for these jobs is expected to be below average over the next 10 years
- however, job prospects are good because supply is low and decreasing
- most employers are looking for advanced degrees (combo degrees... OR and Computer Science, for example... are most attractive)

stats on OR postions
Highlights of OR related jobs from the BLS:

- there were about 62,000 OR jobs in 2002
- 4 out of 5 government OR jobs are in the military
- many private sector OR jobs are defense related
- demand growth for these jobs is expected to be below average over the next 10 years
- however, job prospects are good because supply is low and decreasing
- most employers are looking for advanced degrees (combo degrees... OR and Computer Science, for example... are most attractive)

9.06.2004

Linear programming in forest management
Foresters use linear programming to optimize the production of lumber in timber 'estates'. They generally have one of the following objectives when chosing which stands to harvest:

- Maximize discounted cash flow (i.e. profit over time)
- Minimize costs to a particular 'utilization plant' (lumber mill?)
- Maximize total production (in anticapation of a logging ban?)

9.05.2004

Stochastic programming links
A quicky 'cause I wanna go to bed...

Current trends. Stochastic Programming Community.

Current trends. Stochastic Programming Community.

Simplex method of solving linear programs
George Dantzig, the author of the paper mentioned in the previous post, developed the simplex method for solving linear programs. The algorithm exploits the fact the optimum point in a system of linear inequalities is always on the edge and never in the interior. For example, the system 0 <= x <= 1 and 0 <= y <= 1 is a box. It can be shown that the optimum point is somewhere on 1X1 square (furthermore, the optimum is at one of the vertices... [0,0], [0,1], [1,0] or [1,1]).

The first step in the method is to find the edge. Once you're there, you walk your way around the edge until you find the optimal point.

It turns out that this method is very efficient in most useful cases, but it gets bogged down in some special cases (i.e. when there are lots of variables and lots of conditions, but each condition only deals with a few variables... aka sparse matrices). There is ongoing research to determine algorithms that are more efficient in those special cases.

The first step in the method is to find the edge. Once you're there, you walk your way around the edge until you find the optimal point.

It turns out that this method is very efficient in most useful cases, but it gets bogged down in some special cases (i.e. when there are lots of variables and lots of conditions, but each condition only deals with a few variables... aka sparse matrices). There is ongoing research to determine algorithms that are more efficient in those special cases.

History of Linear Programming
OR started in WWII to solve a variety of logistical questions (e.g. are big convoys better than small ones?). Linear programming was formalized in 1947 and grew out of new interest in optimization. Computer technology was really taking off at this point, too, meaning the optimization problems were able to be computed (in a reasonable time frame). This article is a great overview of the history of linear programming. The author suggests stochastic programming (aka linear programming under uncertainty) is a ripe area for future research.

OR and container ships
OR techniques are used to run ports and container ship routes. The most popular mechanism for moving stuff between continents, container shipping is growing in the double digits every year. OR helps to increase efficiency and safety by discovering the optimal organization of containers on the ship, allocating ships to port berths, and the layout of the temporary storage on the docks.

OR Overview
What is OR? "the effective use of scarce resources under dynamic and uncertain conditions,"

"used to analyze complex real-world systems, typically with the goal of improving or optimizing performance," and

"the professional disciplines that deal with the application of information technology for informed decision-making."

The tools of OR are statistics, simulation and optimazation. All of these tools are best suited for analyzing large data sets. For the most part, this means that OR can be used to solve problems the have available large amounts 0f data.

Links:

Wikipedia

Salaries (entry level, job listings)

Programs

INFORMS marketing campaign

Boston Globe Article

Compaines: Optiant, SmartOps, RAND, Military

OR and the defense industry

Example RAND Corp job description:

Operations researchers work with multi-disciplinary teams, advising policymakers and private sector clients on a diverse set of issues ranging from military logistics and manpower policy to the allocation of public health resources and the implementation of electric power deregulation. Such individuals use their quantitative skills to model and analyze current policy problems of national and international importance while continuing to develop better analytic and modeling techniques and build upon RAND's early OR successes. In conjunction with their research teams, they communicate their results directly to senior decision-makers, the analytic community, field-level personnel affecting change, and the public at large.

"used to analyze complex real-world systems, typically with the goal of improving or optimizing performance," and

"the professional disciplines that deal with the application of information technology for informed decision-making."

The tools of OR are statistics, simulation and optimazation. All of these tools are best suited for analyzing large data sets. For the most part, this means that OR can be used to solve problems the have available large amounts 0f data.

Links:

Wikipedia

Salaries (entry level, job listings)

Programs

INFORMS marketing campaign

Boston Globe Article

Compaines: Optiant, SmartOps, RAND, Military

OR and the defense industry

Example RAND Corp job description:

Operations researchers work with multi-disciplinary teams, advising policymakers and private sector clients on a diverse set of issues ranging from military logistics and manpower policy to the allocation of public health resources and the implementation of electric power deregulation. Such individuals use their quantitative skills to model and analyze current policy problems of national and international importance while continuing to develop better analytic and modeling techniques and build upon RAND's early OR successes. In conjunction with their research teams, they communicate their results directly to senior decision-makers, the analytic community, field-level personnel affecting change, and the public at large.

I'm back!
So I took the summer off and now I'm back. I'm at HSU to take a Math degree... still working towards getting into a grad program.

My schedule is packed. I'm taking real analysis, math stat, linear algebra and German liturature (Marx, Freud, Kafka, Mann, Hesse, etc). I'm also a math tutor, I joined the math club and I particapate in the math colloquium. Last but not least, I'm doing some research for Prof. Haag regarding operational research and linear programming (he's also my linear algebra teacher).

Lot's of my posts will be regarding stuff I learn about OR and/or linear programming.

My schedule is packed. I'm taking real analysis, math stat, linear algebra and German liturature (Marx, Freud, Kafka, Mann, Hesse, etc). I'm also a math tutor, I joined the math club and I particapate in the math colloquium. Last but not least, I'm doing some research for Prof. Haag regarding operational research and linear programming (he's also my linear algebra teacher).

Lot's of my posts will be regarding stuff I learn about OR and/or linear programming.

ARCHIVES

06.2003 /
07.2003 /
08.2003 /
09.2003 /
10.2003 /
11.2003 /
12.2003 /
01.2004 /
02.2004 /
03.2004 /
04.2004 /
05.2004 /
06.2004 /
08.2004 /
09.2004 /
10.2004 /
11.2004 /
12.2004 /
01.2005 /
02.2005 /
03.2005 /
04.2005 /
05.2005 /
06.2005 /
07.2005 /
08.2005 /
09.2005 /
10.2005 /
11.2005 /
12.2005 /
01.2006 /
02.2006 /
03.2006 /
04.2006 /
05.2006 /
06.2006 /
07.2006 /
08.2006 /
09.2006 /
10.2006 /
11.2006 /
12.2006 /
01.2007 /
02.2007 /
03.2007 /