[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Stop criteria for MIP integer solution?

From: Andrew Makhorin
Subject: Re: [Help-glpk] Stop criteria for MIP integer solution?
Date: Tue, 13 Aug 2002 14:23:02 +0400

>I'm wondering if I can let the solver (for MIP) stop when it reaches the
>first solution "better than the currently known optimum" ?
>(I've found the time limit parameter...)

This feature is not implemented in the branch-and-bound solver.
However, this can be easily done by modifying the source code a bit.
If you wish hacking, please inform me, and I'll say what you need to

>And in relation with this, can the solver continue from where it stopped
>(after time exceeded, for instance) by calling lpx_integer() a second time?

No, it can't, because the branch-and-bound tree is not kept on exit.
But even if the tree were kept, you couldn't modify the problem, so it'd
be the same as solving the problem to the end without interruption.

>The reason I ask is the nature of my specific problem: the (binary)
>variables are time-indexed variables, and the objective is to minimize a
>"time". So when a feasible solution is found (with objective value T), I
>tell for sure that the decision variables related to times > T are certain
>be 0 in the optimum (and in this feasible solution).
>This knowledge would allow me to "reduce" the problem (= removing variables
>deleting columns from the constraint matrix).  I could then try to find the
>first feasible solution for the reduced problem with objective < T etc...
>This way, I will iteratively try to find a solution for problems that keep
>getting smaller, and I suppose that this could be a lot faster than trying
>find the optimum to the original large problem?

Using the branch-and-bound method you can't change the original problem
during the search, so after fixing some variables you need to
re-optimize the problem from scratch. However, your approach looks like
fixing variable by a certain logical condition. Could you classify your
problem, i.e. point out its canonical form known in the literature?

reply via email to

[Prev in Thread] Current Thread [Next in Thread]