search

coin-or / SHOT

A solver for mixed-integer nonlinear optimization problems
https://shotsolver.dev
Eclipse Public License 2.0
117 stars 25 forks source link

fix handling of semicontinuous variables; add support for semiinteger variables #122

Closed svigerske closed 3 years ago

svigerske commented 3 years ago

This adds handling of semiContinuous variables to the Cbc interface.

But more importantly, SHOT itself didn't seem to take much into account that the bounds stored for a semicontinuous variable were not the actual bounds, i.e., the feasible 0 point seem to have been ignored. So with the changes here, the variable bounds are now the actual bounds also for a semicontinuous variable and another member semiBound is added to store the (typically) lower bound if not away from 0.

Also change code so that semicontinuous variables {0} or in [lb,ub] with ub < 0 should be possible.

If I run this on meanvarxsc with CPLEX, things look good. With Cbc, it doesn't (valgrind reports invalid reads when eval a quadratic expr with an auxvar; asserts in Cbc fail, and more from the address sanitizer).

Since I was here anyway, I also added support for seminteger variables by just duplicating code for semicontinuous vars.

andreaslundell commented 3 years ago

Now it seems it is working for meanvarxsc for Gurobi and CPLEX through GAMS. Unsure about Cbc still since it does not seem to write out the semicontinuous variables to lp-format. I will need to check this next week and add support for OSiL. Do you have any code for AMPL and semicontinuous variables @svigerske?

svigerske commented 3 years ago

Now it seems it is working for meanvarxsc for Gurobi and CPLEX through GAMS. Unsure about Cbc still since it does not seem to write out the semicontinuous variables to lp-format. I will need to check this next week and add support for OSiL. Do you have any code for AMPL and semicontinuous variables @svigerske?

Since Cbc doesn't actually know semi-continuous vars, but only these more lotsize objects, it doesn't seem to bother to try to figure out which of its lotsize objects it could write as semi-continuous into an lp file.

AMPL doesn't support passing semi-continuous or -integer variables to the solver, as far as I know.

andreaslundell commented 3 years ago

This adds handling of semiContinuous variables to the Cbc interface.

But more importantly, SHOT itself didn't seem to take much into account that the bounds stored for a semicontinuous variable were not the actual bounds, i.e., the feasible 0 point seem to have been ignored. So with the changes here, the variable bounds are now the actual bounds also for a semicontinuous variable and another member semiBound is added to store the (typically) lower bound if not away from 0.

Also change code so that semicontinuous variables {0} or in [lb,ub] with ub < 0 should be possible.

If I run this on meanvarxsc with CPLEX, things look good. With Cbc, it doesn't (valgrind reports invalid reads when eval a quadratic expr with an auxvar; asserts in Cbc fail, and more from the address sanitizer).

Since I was here anyway, I also added support for seminteger variables by just duplicating code for semicontinuous vars.

I fixed some issues with Cbc, but I still get some Valgrind errors:

==806== Invalid read of size 8
==806==    at 0x4842A87: memmove (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==806==    by 0xAF0A1A2: CbcModel::setBestSolution(double const*, int, double, bool) (in /opt/cbc-2.10/lib/libCbc.so.0.0.0)
==806==    by 0xADF0AF6: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (in /opt/cbc-2.10/lib/libCbcSolver.so.0.0.0)
==806==    by 0x559E9C2: SHOT::MIPSolverCbc::solveProblem() (MIPSolverCbc.cpp:695)
==806==    by 0x559449B: SHOT::TaskSolveIteration::run() (TaskSolveIteration.cpp:135)
==806==    by 0x5534857: SHOT::SolutionStrategyMultiTree::solveProblem() (SolutionStrategyMultiTree.cpp:330)
==806==    by 0x5235077: SHOT::Solver::solveProblem() (Solver.cpp:597)
==806==    by 0x3683F9: main (SHOT.cpp:694)
==806==  Address 0xdc64be8 is 0 bytes after a block of size 216 alloc'd
==806==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==806==    by 0xAF09BC6: CbcModel::saveExtraSolution(double const*, double) (in /opt/cbc-2.10/lib/libCbc.so.0.0.0)
==806==    by 0xAF0A4A7: CbcModel::saveBestSolution(double const*, double) (in /opt/cbc-2.10/lib/libCbc.so.0.0.0)
==806==    by 0xAF10CDC: CbcModel::setBestSolution(CBC_Message, double&, double const*, int) (in /opt/cbc-2.10/lib/libCbc.so.0.0.0)
==806==    by 0xAF12A2B: CbcModel::doHeuristicsAtRoot(int) (in /opt/cbc-2.10/lib/libCbc.so.0.0.0)
==806==    by 0xAF25EFA: CbcModel::branchAndBound(int) (in /opt/cbc-2.10/lib/libCbc.so.0.0.0)
==806==    by 0xADEFD2C: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (in /opt/cbc-2.10/lib/libCbcSolver.so.0.0.0)
==806==    by 0x559E9C2: SHOT::MIPSolverCbc::solveProblem() (MIPSolverCbc.cpp:695)
==806==    by 0x559449B: SHOT::TaskSolveIteration::run() (TaskSolveIteration.cpp:135)
==806==    by 0x5534857: SHOT::SolutionStrategyMultiTree::solveProblem() (SolutionStrategyMultiTree.cpp:330)
==806==    by 0x5235077: SHOT::Solver::solveProblem() (Solver.cpp:597)
==806==    by 0x3683F9: main (SHOT.cpp:694)

These disappear if I do not add any MIP starting point. As far as I know, I am adding the solution correctly (unless there is some string-related issue)... Any suggestions?

I do not know if it is related, but Cbc is not able to close the objective gap for meanvarxsc, but I will investigate this further. For CPLEX and Gurobi everything is nice and well.

svigerske commented 3 years ago

Which version of Cbc 2.10 is this? The current stable/2.10?

I sometimes see people having problems with mipstart on the Cbc issue tracker. That seems to be a rather fragile code (even for Cbc standards) and stable/2.10 is sometimes not fixed anymore. If it doesn't come up with Cbc/master, then maybe just disable mipstart if Cbc is 2.10 and there are semicontinuous/integer variables or SOS? If it also happens with Cbc/master, then I can try to debug.

andreaslundell commented 3 years ago

It seems to be fixed in Cbc/master. Now I only have a memory leak

==22516== 4,800 bytes in 19 blocks are definitely lost in loss record 14 of 17
==22516==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==22516==    by 0xAE0E073: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (in /opt/cbc-master/lib/libCbcSolver.so.0.0.0)
==22516==    by 0x559E9C2: SHOT::MIPSolverCbc::solveProblem() (MIPSolverCbc.cpp:695)
==22516==    by 0x559449B: SHOT::TaskSolveIteration::run() (TaskSolveIteration.cpp:135)
==22516==    by 0x5534857: SHOT::SolutionStrategyMultiTree::solveProblem() (SolutionStrategyMultiTree.cpp:330)
==22516==    by 0x5235077: SHOT::Solver::solveProblem() (Solver.cpp:597)
==22516==    by 0x3683F9: main (SHOT.cpp:694)

left which I cannot find the reason for.

svigerske commented 3 years ago

You would need a build of Cbc with --enable-debug to see more.

However, there is also yet another Cbc development branch (refactor) that changes a lot in CbcMain1, so not sure how much it is worth to investigate this.

andreaslundell commented 3 years ago

I compiled with --enable-debug in the Cbc/master branch, and got 

==2793== 976 bytes in 5 blocks are definitely lost in loss record 13 of 16
==2793==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2793==    by 0xAE461F8: double* CoinCopyOfArray<double>(double const*, int) (CoinHelperFunctions.hpp:216)
==2793==    by 0xAE607DB: putBackOtherSolutions(CbcModel*, CbcModel*, CglPreProcess*) (CbcSolver.cpp:346)
==2793==    by 0xAE87CFC: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (CbcSolver.cpp:8065)
==2793==    by 0x559E9C2: SHOT::MIPSolverCbc::solveProblem() (MIPSolverCbc.cpp:695)
==2793==    by 0x559449B: SHOT::TaskSolveIteration::run() (TaskSolveIteration.cpp:135)
==2793==    by 0x5534857: SHOT::SolutionStrategyMultiTree::solveProblem() (SolutionStrategyMultiTree.cpp:330)
==2793==    by 0x5235077: SHOT::Solver::solveProblem() (Solver.cpp:597)
==2793==    by 0x36A3F9: main (SHOT.cpp:694)

So, I would assume this is not a problem with SHOT... Also, SHOT seems to run fine, but it could of course affect the stability when running longer problems. However, this problem is always there (not only with semicont./int. variables) and even with the MIP start functionality disabled.

I do not know which version you are building Cbc in GAMS based on, but be aware that this leak is there in master. I did not try the refactor-branch.

svigerske commented 3 years ago

I compiled with --enable-debug in the Cbc/master branch, and got

==2793== 976 bytes in 5 blocks are definitely lost in loss record 13 of 16
==2793==    at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==2793==    by 0xAE461F8: double* CoinCopyOfArray<double>(double const*, int) (CoinHelperFunctions.hpp:216)
==2793==    by 0xAE607DB: putBackOtherSolutions(CbcModel*, CbcModel*, CglPreProcess*) (CbcSolver.cpp:346)
==2793==    by 0xAE87CFC: CbcMain1(int, char const**, CbcModel&, int (*)(CbcModel*, int), CbcSolverUsefulData&) (CbcSolver.cpp:8065)
==2793==    by 0x559E9C2: SHOT::MIPSolverCbc::solveProblem() (MIPSolverCbc.cpp:695)
==2793==    by 0x559449B: SHOT::TaskSolveIteration::run() (TaskSolveIteration.cpp:135)
==2793==    by 0x5534857: SHOT::SolutionStrategyMultiTree::solveProblem() (SolutionStrategyMultiTree.cpp:330)
==2793==    by 0x5235077: SHOT::Solver::solveProblem() (Solver.cpp:597)
==2793==    by 0x36A3F9: main (SHOT.cpp:694)

So, I would assume this is not a problem with SHOT... Also, SHOT seems to run fine, but it could of course affect the stability when running longer problems. However, this problem is always there (not only with semicont./int. variables) and even with the MIP start functionality disabled.

Of course that's not SHOT.

So putBackOtherSolutions() of Cbc creates a copy of some solution and passes it on:

    double *bestSolution = CoinCopyOfArray(presolvedModel->bestSolution(), numberColumns);
...
    presolvedModel->solver()->setColSolution(bestSolution);

but noone seems to feel responsible to free it again. Maybe @jjhforrest has some idea how to fix this.

I do not know which version you are building Cbc in GAMS based on, but be aware that this leak is there in master. I did not try the refactor-branch.

We are still on some old version of Cbc 2.10. I'm waiting for a new stable branch from Cbc master to do an update.

andreaslundell commented 3 years ago

I am happy with this now since it now also works with Cbc, so I am merging it...