14
$\begingroup$

I asked this question on Stack Overflow but it was closed as "not programming related". So I think this is probably the best place for it...

I read over the wikipedia article, but it seems to be beyond my comprehension. It says it's for optimization, but how is it different than any other method for optimizing things?

An answer that introduces me to linear programming so I can begin diving into some less beginner-accessible material would be most helpful.

$\endgroup$
2

3 Answers 3

Reset to default
11
$\begingroup$

The standard form (and example) sections pretty well describe what it is.

How is it different than any other method for optimizing things?

It's, well, just another method. However, it is somewhat special in that many other optimization algorithms either use linear programming as part of their solution, or are in reality a specialized solution to a linear programming problem. In fact, integer linear programming is NP-complete, meaning that any problem in NP can be stated as an (integer) linear programming problem.
(this also means solving your typical integer linear programming problem is much more difficult than if we didn't restrict ourselves to integers..)

$\endgroup$
1
  • 1
    $\begingroup$ I kind of disagree (but not enough to make a new answer, as this is kind of an intro-to question). I would say the difference is that a "Linear Program" is a way of writing down an optimization problem. It is the precise mathematical definition of an optimization problem with a linear objective function and linear constraints. Then "Linear Programming" is a phrase meaning: the study of linear programs, their properties, and solution methods. $\endgroup$
    – cheshirekow
    Commented Feb 24, 2012 at 13:22
6
$\begingroup$

BlueRaja's answer is certainly more complete than this one (and gives good references), but here's a rough overview of linear programming. Suppose that you have a linear function (in high school courses, it's typically a function of two variables) that you want to optimize on a convex "feasible" region bounded by linear equations (again, in high school, the bounds are typically described using linear inequalities in two variables).

Because the function to optimize is linear, the set of points for which the function has a particular value, say c, is a line (and all such lines are parallel) and the value of the function anywhere to one side of the line is greater than c and anywhere to the other side of the line is less than c. So, you can think about moving through this set of constant-value lines to increase/decrease the value of the target function as appropriate to optimize it.

Since the feasible region is bounded by linear equations, as the constant-value line moves through and out of the feasible region, it last touches the feasible region at a vertex (or possibly at all points on an edge connecting two vertices), so the optimal solution must occur at a vertex of the feasible region.

Given all that, linear programming comes down to evaluating the target function at all the vertices of the feasible region to find the optimal value.

$\endgroup$
5
  • $\begingroup$ +1, I like how you answered this just after asking that stamp question :P . When you say it must be evaluated at all the vertices of the feasible region... isn't that impossible unless only integers are being used? Surely there's a more efficient way to solve LP problems than evaluating the target function at all the vertices of the feasible region to find the optimal value $\endgroup$
    – Cam
    Commented Jul 26, 2010 at 22:17
  • $\begingroup$ Consider this, from one of BlueRaja's links. The feasible region shown at the right, bounded by three inequalities (five if you count the axes) has 5 vertices: the origin, the intersection of two of the bounding lines with the axes, and two points of intersection of pairs of bounding lines. Applying a linear function to those points is fairly efficient and doesn't require that they be integers. There are also descriptions of specific algorithms for linear programming at that link. $\endgroup$
    – Isaac
    Commented Jul 26, 2010 at 22:25
  • $\begingroup$ Yes it is my link, wikipedia is my little secret :) more seriously though, perhaps I should mention that integer programming being NP-complete is not a good thing, to avoid confusion.. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented Jul 26, 2010 at 22:46
  • $\begingroup$ Oh, cool - that totally makes sense. I had misunderstood some stuff at first :) $\endgroup$
    – Cam
    Commented Jul 26, 2010 at 23:26
  • $\begingroup$ Just a comment on Isaac's last statement: For all but the smallest problems, you actually don't want to evaluate the target function at all the extreme points of the feasible region. There are just too many of them. (I believe the best known result on an upper bound for the expected number is $2^n$, where $n$ is the number of variables!) The major linear programming algorithm, the simplex method, works so well because it (except in a few pathological cases) manages to consider only a small subset of the extreme points and still gets to an optimal solution. $\endgroup$
    – Mike Spivey
    Commented Oct 23, 2010 at 18:57
3
$\begingroup$

I suggest you this article, which talks about Linear Equations, Linear Programming, Integer Programming and P=NP. It's easy to understand and talks about the differences among these things

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .