Re: [Help-glpk] Linear Programming Relaxation

[Jeffrey Kantor]

Comments embedded below ---

On Wed, Dec 2, 2009 at 11:00 AM, RC Loh <address@hidden> wrote:

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.

Given our correspondence to date, I'm completely sure we've expressed the relationship between linear programming with integers and real numbers. There are many approaches,

and you may want to get familiar with basic branch and bound techniques to understand

how this all works. 

 

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

Simplex method can be quite efficient for a wide class of medium and even large scale problems. But from below, the computational challenge of your problem is dealing

with 2000 binary variables.   

 

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?

In my view, save these issues for a later time. You've got other problems to deal with first.

 

 

 

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.

Holy smokes!  You've got a big problem on your hands.

* I hate to keep harping on this question, but what is it you need to do?  Do you need to get a complete solution to each of the 300 problems? Or do you just need to know which of the 300 cases provide the best solution for your application?  These are different things, and invite different approaches.

* For each problem, do you know a feasible solution before you start the calculation?

* Implementing SOS constraints may make a big difference in your problem.  glpk is very good solver, but there are others out there that may be more suited to your application.  You might consider testing your problem with lp_solve or with the cbc/clp from the coin-or project.

If you like, I'd be glad to exchange emails directly without have to engage the whole list-serve in this continuing dialog.

Jeff

 

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!