Re: [Help-glpk] Two questions about optimize

[Andrew Makhorin]

> 1. I have solved a complex problem which takes more than 30000 seconds,
> but when use this command ‘--mipgap 0.19’, it consumes only 322s and
> these two answers are completely the same. Why does this happen?

In the former case the solver solves the instance to optimality and
thereby proves that the solution is optimal. In the latter case you
cannot be sure that you obtained optimal solution; you can be sure only
in that that there is no integer feasible solution which is 19% better
than the one reported by the solver. (It even may happen that the solver
finds optimal solution quickly, say, with a primal heuristic, and 99% of
the solution time is taken just to prove its optimality.)

> 2. This problem is non-convex because of constraints, but I found that
> even if I make the problem convex by removing the constraints, the answer
> is satisfied to the constraints, and the time is very short. However, the
> objectives of them are different a lot, should they be the same? Thank
> you very much!

If you relax the original problem by removing some constraints and
obtain solution which is optimal to the relaxed formulation and satisfies
to all removed constraints, then your solution is also optimal to the
original problem.