Re: [Help-glpk] Linear Programming Relaxation

[Michael Hennebry]

On Thu, 3 Dec 2009, RC Loh 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.

Note that an integer program is not necessarily an integer linear program,
e.g.:
min x**3 + y**3 + z**3
s.t.
    x**2 + y**2 +z**2 = 1096234
    x, y, z integer

By itself, an interior point method is not likely to solve a integer problem.
An interior point method can be used as the LP solver
within a branch and bound or cutting plane solver.
One reason simplex solvers are usually preferred
is that the dual simplex method is good when solving
a sequence of more and more constrained problems.
This occurs with both branch and bound and cutting plane solvers.

> 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?

Non-convex means not convex.

Since we are dealing with reals, I'll refer only to reals.

A convex subset of R**n has no hollows, coves, bays, etc.
If it's bounded and you shrink wrap it,
all the wrapping will touch the boundary
and all the boundary will touch the wrapping.
All filled triangles, ellipses, parallelograms
and straight hot dogs are convex.
Kidneys and bananas are not convex.
More precisely if S is a convex subset of R**n and x and y are members of S,
then the line segment between them is a subset of S.

A convex function is one for which linear interpolation produces a value
that is no less than the correct answer, e.g. connect the asterisks below.
*
  -
 *  -
      -
  *     -
   *      -
     *      -
        *     -
            *   -
                 *-
                      *
This implies that its domain is convex and that the set
{ (x, y) : y>=f(x) } is convex.
x need not be 1-dimensional.

> What is global optimum and local optimum?

A global optimum is what one usually means by optimum.
A local optimum is a best solution among it and those nearby.

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

If one is trying to minimize one's altitude on the surface of the earth,
the top of the ocean is a rather large local optimum.

sin(x) has many local minima, all of which are global minima.
sin(x)/(1+x**2) has one global minimum and lots of local minima.
sin(x) restricted to x in [-pi, 0] is convex.
It has one local minimum which is also its global minimum.
sin(x) restricted to x in [-1.5pi, 0.5pi] has one
local minimum which is also its global minimum.
It is not convex.

--
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."