Re: [Help-glpk] Linear Integer Arithmetic

[Brady Hunsaker]

Paulo Jorge Matos wrote:
> Hi all,
> 
> First time using glpk I have a question which was already made here
> some times (some results came up on archives search).
> I'm working on Linear Integer Arithmetic and I've seen that in glpk to
> solve such a problem you first relax it with simplex and then use
> lpx_integer. Can I use interior point instead of simplex in this case
> (guess not but need oppinions)? (Would it be faster? In general
> problems, the manual asserts this is the case).
> 

In order to use an interior-point algorithm with branch-and-bound, you
typically need a "crossover" routine, which converts the final LP
solution to be a basic solution.  GLPK doesn't currently have a
crossover routine, so I don't think this is possible now.

The reason for this is that the simplex algorithm (which uses only basic
solutions) is good at resolving problems when small changes are made,
which is what happens in the branch-and-bound algorithm.

> As you might imagine Linear Integer Arithmetic is 'not' Linear
> Programming so I don't have an objective function. What's the best way
> to say I don't need an objective function?
> In cplex I do: 'maximize 0'
> 

The same method should work.

> Now, the central issue has to do with strict inequalities. Are they
> supported in glpk? I've seen on some posts (some of them years ago,
> 2002) that they are not but I've also read about a function able to
> read cplex files and cplex files accept strict inequalities so... how
> does glpk handle this? Andrew Mahhorin on Aug 9th 2002 mentioned a
> solution to solve this issue which was solved by adding an epsilon to
> the constraint bound. Is this 'still' the number one solution for us
> all with glpk?
> 

Strict inequalities are not possible in linear programming.  What's the
solution to max x, with x < 1 ?   There is none; any solution can be beat.

In what sense do you need a strict inequality?  How to model your
problem depends on your answer.  Adding small epsilon values is one
possibility, but may not be the best.

If you only have integer values, then a strict inequality is fine, but
it should be converted to the equivalent weak inequality.

Brady