amplglpkfeasibilitymathprog

Print something completely different when the LP is infeasible in MathProg

I’m using MathProg (a language specific to the GLPK library, resembling a subset of AMPL) to find topological ranking of vertices of a graph. It’s an assignment for my linear programming class. It’s an introductory exercise to make sure we can formulate a simple linear program and solve it using GLPK.

I’ve written a Perl script that generates the linear program in MathProg for a given graph. It prints values of the variables (ranks of vertices) via printf. If it’s feasible, that’s exactly what I want; otherwise it prints all zeros, but I want to print just Infeasible, has cycles or loops..

I managed to do it in a hacky way (see below). How to do it more elegantly, without repeating the condition for feasibility? Is there a way to detect infeasibility that does not depend on the problem being solved?

param Vsize := 3;
set V "Vertices" := (0..Vsize-1);
set E "Edges" within V cross V := {(0, 1), (1, 2), (2, 0)};

var v{i in V} >= 0;
minimize rank_total: sum{i in V} v[i];
edge{(i, j) in E}: v[j] - v[i] >= 1;

solve;

printf "#OUTPUT:\n";
printf (if ((exists{i in V} v[i] >= 1) or card(E) = 0) then "" else "Infeasible, has cycles or loops.\n");
printf{i in V} (if ((exists{j in V} v[j] >= 1) or card(E) = 0) then "v_%d: %d\n" else ""), i, v[i];
printf "#OUTPUT END\n";

end;

I tried to declare param Feasible binary := (exists{i in V} v[i] >= 1) or card(E) = 0; but GLPK refused it with Model processing error. When I declared it before solve, it said operand preceding >= has invalid type, when after, it said expression following := has invalid type. I was seeking something like a variable in common programming languages.

Solution

  • In AMPL you can check the built-in parameter solve_result to see if the problem is infeasible:

    if solve_result = 'infeasible' then
  print 'Infeasible, has cycles or loops.';

    However, I'm not sure if GLPK supports this parameter in which case you might need to check for feasibility manually.

    As for the error, since exists is a logical expression you can't use it as a numeric one. The fix is to simply put logical expression in if:

    param Feasible binary :=
  if (exists{i in V} v[i].val >= 1) or card(E) = 0 then 1;