Re: [Help-glpk] Use the best found integer solution regardless of mip gap

[Chris Matrakidis]

Dear Pietro,

Since nobody answered, I'll give it a try, although I'm not using C#. My understanding is that glpk-cli is a thin wrapper around glpk, and the behaviour should be the same: the best integer solution is always available when the solver terminates. So, there is no need for the more complicated schemes you are describing. Can you give more details on what you are observing when the solver reaches the time limit?

Best Regards,

Chris Matrakidis

On 5 March 2018 at 19:05, Pietro Scionti <address@hidden> wrote:

Hello,
I am solving a MIP problem giving it a certain time limit. I am using the library from a C# project calling the CLI interface (http://glpk-cli.sourceforge.net/) and my version is 4.60.

This problem sometimes (I think corresponding to whether certain "strange" constraints are activated or not) arrives just short of the optimal solution, then loops there until it stops due to the time limit. IE the console prints lines like these
+116950: mip =   1.500470000e+02 >=   1.500100000e+02 < 0.1% (2557; 2349)
+169952: mip =   1.500470000e+02 >=   1.500100000e+02 < 0.1% (3679; 3420)
+223563: mip =   1.500470000e+02 >=   1.500100000e+02 < 0.1% (4529; 4662)
+276156: mip =   1.500470000e+02 >=   1.500100000e+02 < 0.1% (5488; 5755)
+328782: mip =   1.500470000e+02 >=   1.500100000e+02 < 0.1% (6167; 6875)
For some time before "TIME LIMIT EXCEEDED. SEARCH TERMINATED".

Now, in these cases (or in general, every time it doesn't reach the wanted mip gap), I would like to be able to use the best found integer solution.
Basically, I came up with two possible approaches:
1) keeping a pointer to the best found solution inside my user-defined callback and use it if the b&c algorithm exits
2) somehow trick the solver into relaxing the mip gap condition when I see the time limit is approaching
3) stupid solution: memorize the best found mipgap, and restart the solver with the same input giving it a less restrictive mip gap. Obviously this solution would (at worst?) double the total time needed, so it's a last ditch effort

So, first question, is what I'm doing even possible? Especially the 2nd idea, since I haven't found something related to it in the documentation!!
And if so, are there better ideas?

Going on with the first approach, I defined this callback
                public void callback(glp_tree tree)
                {
                        // ..
                        int reason = GLPK.glp_ios_reason(tree);
                        if (reason == GLPK.GLP_IBINGO)
                                bingo = GLPK.glp_ios_get_prob(tree);
                }
The glp_prob bingo object is a private member of the class.
Then, inside the main method,

                ret = GLPK.glp_intopt(mip, iocp);
                // ..
                if (ret == GLPK.GLP_ETMLIM)
                                if (bingo != null)
                                _parserOutputBINGO?.Invoke(bingo, mip, result);

And finally, the _parserOutputBINGO method at some point calls

                int index = GLPK.glp_find_col(prob, colName);
                if (index == 0)
                           throw new Exception("Non-existing column " + colName);

                GLPK.glp_mip_col_val(bingo, index);

I know from the documentation that this problem is not necessarily the same as my original problem, so the parser method tries to reconcile the difference.
9 times out of 10, this call fails with a "System.AccessViolationException : Attempted to read or write protected memory. This is often an indication that other memory is corrupt. ", while the other time the method works as intented. I guess the bingo object has already been been disposed?

So, my further question is, can i trust to use this object outside the callback, or is it bound to be disposed at an unforeseeable time and thus this code could fail when it feels like it? Is there something I'm doing wrong?

Thank you very much

Pietro Scionti

_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk