Andrew, I do not agree.
You should convert your infeasible model to the feasible
problem. In this new problem object function should minimize total discrepancy
or number of conflicting constraints.
If your have some inequality then you should add 1 variable.
The constraint
a(i, 1)*x(i, 1)+ a(i, 2)*x(i, 2)+. . .+ a(i, n)*x(i, n) <= b(i)
should be converted to
a(i, 1)*x(i, 1)+ a(i, 2)*x(i, 2)+. . .+ a(i, n)*x(i, n) –(y(i)-p(i)) = b(i),
where
y(i) is additional variable; p(i)
– some constant.
If your have some equation then you should add 2
variables. The constraint
a(i, 1)*x(i, 1)+ a(i, 2)*x(i, 2)+. . .+ a(i, n)*x(i, n) = b(i)
should be converted to
a(i, 1)*x(i, 1)+ a(i, 2)*x(i, 2)+. . .+ a(i, n)*x(i, n) –(y(i)-p(i))+z(i)= b(i)
where
y(i) and z(i) are
additional variables; p(i) – some constant.
At first you should find p(i) for each row. Each variable x(j)
should be assigned to anyone allowable value; all variables y(i) and z(i) should be assigned to
zero. So p(i) can be
calculated from row i. And you have a feasible
solution.
At second you should solve the new problem with
variables x(j), y(i) and z(i). You should minimize sum of y(i) and z(i) (original object
function is ignored). If in the final solution y(i) or z(i) is grate than zero
then constraint i is conflicting. Variables x(i) may be integer . . . What is
the problem?
Of course you can use other object function on contradictory
constraints finding. For example, in the objective function you can weighting y(i) and z(i)
correspondently to numbers of variables of constraint i.
Or/and use addition pseudoboolean variables b(i):
y(i)<=Inf*b(i),
z(i)<= Inf
*b(i)
Sum(i in 1..m) v(i)*b(i) --> min
where
Inf – “Infinity”value”,
v(i) – number of variables x(j) in constraint i.
Of course some special technique should be used for
constraints with “infinite” constants.
Sergey.
No, currently the infeasibility analysis is not implemented in glpk.
Would like to note that IIS is applicable to pure lp, but not to mip.
In case of mip a similar analysis is impractical (except some trivial
cases).
> My name is Roman, I #39;m an Economics student at Tel-Aviv University. I
> #39;m working on solving a MILP problem which involves devising an
> algorithm to solve problems in which initially there are no feasible
> solutions.
> I #39;ve been using Lindo as a basis for this, but later found your
> algorithm - GLPK.
> The problem is as follows: Lindo gives feedback when the constraint set
> is infeasible (using some sort of IIS module)- it tells you what are the
> necessary or sufficient constraints to remove to achieve a solution.
> Your algorithm doesn #39;t have this option, or at least I wasn #39;t
> able to locate such an option. I find this feedback from Lindo to
> be extremely valuable to my work.
> Does GLPK has something of this sort?