RE: [Help-glpk] Linear Programming Relaxation

[Meketon, Marc]

To the best of my knowledge (which admittedly is not up-to-date), none of the research into using interior point algorithms for solving integer programs has ever been used commercially, nor has there been any convincing arguments to use interior point algorithms for integer programming.

 

On the cases where interior point algorithms converge to the initial relaxed linear program of an integer program much more quickly than the simplex does, an extra step is needed to take that solution and create an extreme point solution.  Often, “real-life” linear programs are dual degenerate which means that there are multiple optimal solutions.  Interior point solutions tend to be far away from the extreme points of the convex optimal surface, and getting to any extreme point often takes a lot of computations.  To get to the extreme points, you need the simplex.  So by the time you find an optimal extreme point with the combination of interior point and simplex, you might as well just used the simplex.

 

The extreme points tend to be more “integer”.  More importantly, an extreme point is necessary for the simplex algorithm used in the branch and bound (and branch and cut) procedures.  The simplex works well since it can be warm-started – only a relatively few simplex iterations are needed to resolve.  But a consistently working warm-start strategy for interior points is elusive, leaving the simplex as the only real method for resolving a linear program after a branch or a cutting plan is added.

 

As I mentioned above, my knowledge is a bit old.  I would like hear from anyone else if there are advances in using interior point algorithms for integer programming.

 

-Marc

 

---

From: address@hidden [mailto:address@hidden On Behalf Of RC Loh
Sent: Wednesday, December 02, 2009 11:00 AM
To: Michael Hennebry; Andrew Makhorin; Jeffrey Kantor; Ali Baharev
Cc: address@hidden
Subject: Re: [Help-glpk] Linear Programming Relaxation

 

Hi Andrew, Michael, Jeffrey, Ali,

 

Thank you very much for all your information and advice.

 

So from what I gathered from all of you are that:

 

1) An Integer program can be solved using Interior Point method too. Not necessary solving an Integer program using Simplex method.

 

2) Simplex method under certain conditions also runs in polynomial time.

 

Some of the terms used by Michael confused me. Sorry that I am very new to this area. So I am not familiar with most of the terms.

 

What is convex and non-convex?

What is global optimum and local optimum?

 

Can you give me examples of global optimum, local optimum, convex and non-convex?

 

 

Hi Ali,

To answer your question, yes, I faced computational time problem when I have 2000 binary structural variables using Simplex method. It took more than 4 hours and still I could not obtain a result. So I terminated the execution pre-maturely.

 

I gathered that using Simplex method does not work for me because I have more than 300 similar problems to be solved.

 

Rdgs,

Paul

 

 

 

---

From: Michael Hennebry <address@hidden>
To: RC Loh <address@hidden>
Cc: Andrew Makhorin <address@hidden>; Jeffrey Kantor <address@hidden>; address@hidden
Sent: Wednesday, 2 December 2009 2:03:00
Subject: Re: [Help-glpk] Linear Programming Relaxation

On Tue, 1 Dec 2009, RC Loh wrote:

> Thank you for your suggestion. I am currently reading up on SOS1 and see whether it is applicable to my problem.

It is.

> According to Andrew, the SOS1 is implemented by a version of Simplex Method.
> Then what is the difference between using SOS1 with the Simplex Method compared to using Integer Programming?
> Integer Programming is also using the Simplex Method, isn't it?

Here be much conflation of problem type and solution method.

Integer programming is the solving of optimization problems
all of whose variables are required to be integers.
Mixed integer programming allows some variables to be real.
In either case, a simplex method might or might not be used.

SOS1 is a type of constraint.
It makes the feasible set non-convex.
Simplex methods find local optima.
That is global for a minimization problem
with a convex (e.g. linear) objective function.
It might not be good enough for a problem with an SOS constraint.

-- Michael  address@hidden
"Pessimist: The glass is half empty.
Optimist:  The glass is half full.
Engineer:  The glass is twice as big as it needs to be."

 

---

New Email names for you!
Get the Email name you've always wanted on the new @ymail and @rocketmail.
Hurry before someone else does!

 

----------------------------------------------------------------------------
This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail.

Thank you for your cooperation.
----------------------------------------------------------------------------