[Help-glpk] Initial starting point of simplex algorithm

[Rabih Chaar]

Hello Everyone,

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?

 

Thanks in advance.

 

Rabih

 

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