Re: [Help-glpk] Initial starting point of simplex algorithm

[Andrew Makhorin]

> I have been looking for around a month into glpk, mainly minimizing a
> linear problem (no integer programming).
> Some times, the problem is infeasible, and i started looking into
> Chinneck  iis algorithms.
>  
> As a start, I started by implementing a relaxation of a large
> infeasible problem, 191255 rows, 68860 columns, 450946 non-zeros
> and stumbled on something i don't quite understand.
> The relaxed elasticity problem has a solution and the SINF is 0.
> This means that the feasible domain is not empty.
>  
> I imagine that the starting basis used is outside the feasible domain,
> and the minimisation of the objective funtion don't fall into the
> domain.
>  
> Looking into the help list it doesn't seem possible to explicitly
> specifiy a starting point of the algorithm, and i tried the
> glp_adv_basis to no success.
>  
> My idea was taking the non elastic variable from my relaxed problem,
> and input them as a starting point of the simplex algorithm.
> Can you advise me on this issue?

Your idea is unclear to me. In any case you need to solve an auxiliary
lp. What is the advantage?

>  
> PS: here is a small log of both problems
>  
> GLPK Simplex Optimizer, v4.47
> 191255 rows, 68860 columns, 450946 non-zeros
> 0: obj = 0.000000000e+000 infeas = 5.436e+009 (28783)
> ...
> 17761: obj = -8.927238865e+008 infeas = 2.030e+007 (14520)
> PROBLEM HAS NO FEASIBLE SOLUTION
>  
> Elasticity
> Addtional constraints 220038 for 191255 rows
> Current column size is 68860
> Additional Constraints 220038
> Current column size after resize is 288898
> GLPK Simplex Optimizer, v4.47
> 191255 rows, 288898 columns, 642201 non-zeros
> 0: obj = 0.000000000e+000 infeas = 5.436e+009 (28783)
> ...
> * 1552: obj = 0.000000000e+000 infeas = 1.490e-008 (28782)
> OPTIMAL SOLUTION FOUND
> Sinf is 0

It is hard to say what is wrong. On phase I the glpk primal simplex
minimizes the sum of infeasibilities ("infeas" in the terminal output),
which is exactly the sum of elastic variables. Please check your code
more carefully and make sure that all necessary transformations are
performed correctly. I'd also suggest to test your code first on small
instances.