[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Linear Programming Relaxation
From: |
Michael Hennebry |
Subject: |
Re: [Help-glpk] Linear Programming Relaxation |
Date: |
Tue, 1 Dec 2009 12:03:00 -0600 (CST) |
User-agent: |
Alpine 1.00 (DEB 882 2007-12-20) |
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."
- Re: [Help-glpk] Linear Programming Relaxation, Andrew Makhorin, 2009/12/01
- Re: [Help-glpk] Linear Programming Relaxation, RC Loh, 2009/12/01
- Re: [Help-glpk] Linear Programming Relaxation, Jeffrey Kantor, 2009/12/01
- Re: [Help-glpk] Linear Programming Relaxation,
Michael Hennebry <=
- Re: [Help-glpk] Linear Programming Relaxation, RC Loh, 2009/12/02
- Re: [Help-glpk] Linear Programming Relaxation, Michael Hennebry, 2009/12/02
- Re: [Help-glpk] Linear Programming Relaxation, Jeffrey Kantor, 2009/12/02
- RE: [Help-glpk] Linear Programming Relaxation, Meketon, Marc, 2009/12/02
- Re: [Help-glpk] Linear Programming Relaxation, Andrew Makhorin, 2009/12/02
- [Help-glpk] Binary Integer Program with Lagrange Multipliers, RC Loh, 2009/12/19
- Re: [Help-glpk] Binary Integer Program with Lagrange Multipliers, Andrew Makhorin, 2009/12/20