Solving MIP problems with Branch and Bound

[afish]

Hi! I'm looking for a way to use qsopt-ex to solve MIP problems. I can see that -I flag is commented out in the esolver application in https://github.com/jonls/qsopt-ex/blob/master/esolver/esolver.c#L66 and so it cannot solve MIP (only LP is supported).

Do you have a snippet for solving MIP problem? I can see that original (?) solver.c has some code for it in https://github.com/jonls/qsopt-ex/blob/master/tests/solver.c#L185 but I got multiple complication errors when compiling it. Similarly, I haven't found MIP examples in https://github.com/jonls/python-qsoptex

To give you some more context: I'm looking for an exact MIP solver on Windows platform. I'm positive qsopt-ex can do it (it is available in NEOS) and SCIP has a fork to support exact calculations (based on SCIP 3) but I haven't found any precompiled libraries for Windows so I'm compiling them using Cygwin. I'd like to give qsopt-ex a try before spending couple hours on compiling SCIP.

Thanks!

[jonls]

Hello! MIP is disabled in qsopt-ex in this repo as you already noted and it's not possible to enable as far as I can tell. I don't believe any part of MIP solving is implemented but there may be some leftovers from qsopt from before qsopt-ex was forked from that code base.

Regarding NEOS/SCIP, I'm not sure where the MIP support is coming from. Is it possible that they are using a later version of qsopt-ex created by the original developers? I haven't looked into any of these but if there's source code available it would be easy to check if it's a different code base. The code in this repo is based on the most recent GPL licensed qsopt-ex code base that I was able to find but if there's a more recent release with MIP support that is also open source, that would be pretty exciting.

[afish]

Thanks for answering! Too bad MIP isn't implemented. I gave it a try with super simple snippet copied from solver.c and adapted to esolver.c [1] but this didn't work (it said variables are unbounded even though they are). No surprise as this was a bit of a "I have no idea what I'm doing" approach.

I don't know what NEOS uses. The output I got [2] confirms I selected qsoptex but at the same time mentions mpq and dbl_ functions. I don't know the codebase enough to tell if these mpq_* functions (like mentioned "mpq_ILLlp_add_logicals") are from qsopt-ex or from the older part.

You can also see it mentions "using EGlib (build Mar 12 2007-07:22:24)" so I think the codebase is older than yours but I'm not sure either.

As a side note I think there must have been some codebase of qsopt-ex for MIP problems as it is mentioned in couple papers.

Anyway, thanks again for your reply. Feel free to resolve this issue.

[1]

mpq_t value; 
mpq_init(value);
EGcallD(mpq_QSget_objval(p_mpq, &value));
rval = mpq_ILLmip_bfs (p_mpq->qslp, &value, x_mpq, &(p_mpq->itcnt));
ILL_CLEANUP_IF (rval);

[2]

using EGlib (build Mar 12 2007-07:22:24)
Host: neos, Current process id: 15996
Cur data limit -1,-1 (soft,hard)
New data limit 2000000000,-1 (soft,hard) Cur address space limit -1,-1 (soft,hard) New address space limit 2000000000,-1 (soft,hard) Options for /home/neos8/bin/bbsolver_st
    Show Version            : 0
    Input filename          : sample.mps
    Solve MIP               : 1
    MIP bound               : 1.79769e+308
    B&B rule                : 0
    Max Solutions           : 4294967295
    Max Running time 1      : 1.79769e+308
    Max Running time 2      : 1.79769e+308
    Gomory Cuts             : 3
    Use conflict graph      : 0
    Cover Cuts              : 1
    Local Cuts              : 0
    K-Local Cuts            : 0
    Conflict Graph L.C.     : 0
    Simple Local Cuts       : 0
    Nacify Cuts             : 0
    Detect Integral Salcks  : 1
    Cutting Cycle           : Partial
    Using Scaling           : 1
    Simplex Algorithm       : 1
    Simplex primal strategy : 3
    Simplex dual strategy   : 7
    MPF starting precision  : 128
    Print solution          : 1
    Read root-LP basis      : no
    Write root-LP basis     : no
    Maximum allowed memory    : 2000000000
mpq_ILLlp_add_logicals ...
Time for SOLVER_READ_MPQ: 0.00 seconds.
================================================================================
    Trying double precision
================================================================================
starting dbl_ILLsimplex on scaled_lp...
Problem has 2 rows and 3 cols and 4 nonzeros starting primal phase I
(0): primal infeas =  3.5000000 3.5
primal phase I seemingly done
retesting soln
starting primal phase II
problem seemingly solved
seemingly opt = -5.500000
retesting soln
completed dbl_ILLsimplex
scaled_lp: time = 0.000, pI = 2, pII = 2, dI = 0, dII = 0, opt = -5.500000 starting dbl_ILLsimplex on dbl_problem...
Problem has 2 rows and 3 cols and 4 nonzeros completed dbl_ILLsimplex
dbl_problem: time = 0.000, pI = 0, pII = 0, dI = 0, dII = 0, opt = -5.500000 LP Value: -5.500000, status 1 ================================================================================
    Problem Solved Exactly
================================================================================
Time for SOLVER: 0.00 seconds.
  Iter TotNod ReaNod ActNod  NFrac LPcuts  Acuts  Tcuts Prec        Node LP             LB             UB   Int-Infeas         GAP%      TIME
     0      1      1      1      0      0      0      0    0           -Inf           -Inf            Inf 0            1.000000e+02      0.00
     1      1      1      0      1      0      0      0  128      -5.500000      -5.500000            Inf 0.5          1.000000e+02      0.00
     1      1      1      0      0      8      8      8  128      -5.000000      -5.500000            Inf 0            1.000000e+02      0.00
New integer Solution found -5.000000
     1      1      1      0      0      8      0      8  128      -5.000000      -5.000000      -5.000000 0            0.000000e+00      0.00
B&B done
Best Integer Solution -5
Best Bound -5
Number of integer solutions found 1
Cover Cuts
    Found                   : 0
    Globally valid          : 0
    Locally valid           : 0
    Continuous Lifting      : 0
    Discard by slack        : 0
    Discard by fractionality: 0
    Discard by redundancy   : 0
Gomory Cuts
    Found                   : 8
    Discard by slack        : 0
    Discard by fractionality: 7
    Discard by coefficients : 0
    Discard by bounds       : 0
Gomory-2 Cuts
    Found                   : 0
    Discard by slack        : 0
    Discard by fractionality: 0
    Discard by coefficients : 0

*** You chose the QSopt_EX solver ***

[jonls]

Thanks for the details, that's interesting. Now that I'm looking in binary.c it does seem like there may be a branch and bound implementation in there though I'm not sure if it's complete. You might be able to get it working on a floating point problem at least. It doesn't seem like the exact solver in exact.c is trying to solve it as a MIP but what you tried seems to be the right first step but there's probably more to do in exact.c.