[Cbc] getting solution to original problem from Cbc/Clp
Kish Shen
kisshen at cisco.com
Fri Nov 9 13:31:50 EST 2007
Hi John,
Thanks for your quick reply!
John J Forrest wrote:
>
> Kish,
>
> a) postprocessing deletes the solver it is given which is why you get
> error in getNumCols() as that just asks current solver how many columns
> it has.
Thanks!
> b) On first inspection of your code it looks as if the solution should
> be back in lpd->lp->solver. One way to check would be to put garbage in
> the solution before postprocess (setColSolution) and see if it changes.
> If so it should be correct.
> c) It is more likely that - shock, horror - there is a bug in
> preprocessing. I am fairly sure at least one bug has been fixed since
> June. If the user can give you the problem that fails try with
> cbc-stable/2.0 and cbc-trunk.
>
This particular set of problems take several hours to run through, and
about 10% of them were giving errors when the solution was checked. I
had not looked at this in detail, because the checks are performed at
the ECLiPSe level (the Constraint Logic Programming language I am
interfacing COIN to), and I need to look at them to map the problems to
the MIP model passed to Cbc.
However, I donnloaded the latest trunk branch Cbc with svn today, and
the errors are no longer there when I reran the user's program, so it
seems that it was indeed caused by a bug that you have fixed already.
Thanks again!
Cheers,
Kish
> John
>
>
> *Kish Shen <kisshen at cisco.com>*
>
> 11/08/2007 12:58 PM
>
>
> To
> John J Forrest/Watson/IBM at IBMUS
> cc
> cbc at list.coin-or.org
> Subject
> Re: [Cbc] getting solution to original problem from Cbc/Clp
>
>
>
>
>
>
>
>
> Hi John,
>
> I have not had time to look into my problem again in detail until now,
> so sorry for the delay in this follow-up...
>
> John J Forrest wrote:
> >
> > Kish,
> >
> > It sounds as if you are using presolve rather than CglPreProcess. This
> > could give wrong results as you describe.
> >
> > Look at Cbc/examples/sample2.cpp and try with PREPROCESS defined to 1 or
> > 2 to see two ways of using CglPreProcess.
> >
> > As to your questions.
> >
> > 1) The solver can in some circumstances not have an integer solution -
> > bestSolution is what is needed but it must go through post processing.
>
>
> I think it is best if I actually show what exactly I am doing in my
> code. Here is a brief outline of what I do:
>
> Types of variables used:
>
> OsiClpSolverInterface * lpd->lp->Solver <--- the original problem
>
> OsiSolverInterface * mipsolver
> CbcModel * lpd->lp->mipmodel
> CbcModel * model
> CglPreProcess process
>
> 1. I first preprocess the original problem:
>
> mipsolver = process.preProcess(*lpd->lp->Solver, false, 5);
>
> 2. I then put this preprocessed problem into a CbcModel (unless
> preprocess failed, in which case I abort):
>
> lpd->lp->mipmodel = new
> CbcModel(static_cast<OsiSolverInterface
> &>(*mipsolver));
> CbcModel* model = lpd->lp->mipmodel;
>
> The lpd->lp->mipmodel is to allow me to access the model later in the
> code, whereas model is used locally..
>
> 3. this is followed by some more optimisations etc., based on the
> example2 code, and then branchAndBound is called:
>
> model->branchAndBound();
>
> In some cases, the branchAndBound may time-out early, because a timeout
> is set.
>
> 4. the problem is post-processed (this is always done, even if the
> problem was timed out, or is infeasible):
>
> process.postProcess(*model->solver());
>
> looking at the comment of example2, this will put the post-processed
> solution back into lpd->lp->Solver. I then subsequently access this via
> lpd->lp->Solver->getColSolution().
>
> My user have reported that the solution returned may sometimes be wrong
> because it seems to violate some the constraints in the original
> problem. This is why I thought I may be returning a relaxed solution
> from a node in the branch and bound (e.g. when the problem was timed
> out), rather than the best integer solution. This is why I want to use
> bestSolution to return the solution.
>
> However, bestSolution is a method for CbcModel, and not OSI, I think,
> and the solution in the CbcModel (the one in model in my code) is still
> the preprocessed problem, rather than the original problem, even after
> the postProcess call in 4. I checked this by returning the column number
> for model before and after the post-processing, and it is the same (and
> less than the original problem's).
>
> Is there any way I can be certain I am getting the best integer solution
> found by the branchAndBound, in the original problem form, rather than
> the preprocessed one?
>
> In checking the column numbers, I was somewhat surprised that I got an
> error in the second call to getNumCols:
>
> std::cout<< "before:"<<mipsolver->getNumCols()<<std::endl;
> process.postProcess(*model->solver());
> >>> std::cout<<
> "after:"<<mipsolver->getNumCols()<<std::endl;
>
> here is the output from running this:
>
> before:16
> pure virtual method called
> after:Signal 6
>
> I am not sure this is directly related to my problem, but is this
> expected behaviour?
>
> I think I am using a Cbc that I download in June this year.
>
> Thanks in advance for any information/help!
>
> Cheers,
>
> Kish
>
>
>
>
> > 2) The result should be correct for problem with all integer variables
> > fixed to correct values.
> >
> >
> > John Forrest
> >
> >
> > *Kish Shen <kisshen at cisco.com>*
> > Sent by: cbc-bounces at list.coin-or.org
> >
> > 10/19/2007 12:03 PM
> >
> >
> > To
> > cbc at list.coin-or.org
> > cc
> >
> > Subject
> > [Cbc] getting solution to original problem from Cbc/Clp
> >
> >
> >
> >
> >
> >
> >
> >
> > Hi,
> >
> > I am using CBC with CLP as the linear solver. CLP is accessed via OSI
> > i.e. OsiClpSolverInterface), but CBC is accessed directly, instead of
> > via OSI.
> >
> > I have been obtaining the solution state for MIP problems via the OSI
> > calls, e.g. getColSolution(), getRowPrice(), etc.. One of our users
> > reported that some of the solution is incorrect, e.g. variables that
> > should be integers are not, and some constraints are violated.
> >
> > I suspected that this is because the OSI calls are via
> > OsiClpSolverInterface, and so I am obtaining the state from the most
> > recent LP relaxation, rather than the most recent MIP solution. I
> > therefore changed the code to obtain the solution state via Cbc calls,
> > for example, bestSolution() of CbcModel instead of getColSolution().
> >
> > Unfortunately, in this case, the number of columnssiz in the problem
> > seems to be much smaller: in one example, the original problem had 945
> > columns, and the MIP solution of the problem has only 205 columns. I
> > assume this is because presolve reduced the problem, and bestSolution()
> > returns the solution for the presolved matrix.
> >
> > Questions:
> >
> > 1) Am I correct that OSIClpSolverInterface's methods, such as
> > getColSolution(), is returning the state from the LP relaxation, rather
> > than the MIP solution? [If not, then there is something wrong with the
> > MIP solution produced]
> >
> > 2) How can I obtain the MIP solution state (solution values, row price,
> > row activity, reduced cost [and basis status for the LP relaxation that
> > produced the MIP solution, if this is available], for the original
> > problem (and not the presolved problem)?
> >
> > Thanks in advance for any help/information!
> >
> > Cheers,
> >
> > Kish Shen
> > _______________________________________________
> > Cbc mailing list
> > Cbc at list.coin-or.org
> > http://list.coin-or.org/mailman/listinfo/cbc
> >
> >
> > ------------------------------------------------------------------------
> >
> > _______________________________________________
> > Cbc mailing list
> > Cbc at list.coin-or.org
> > http://list.coin-or.org/mailman/listinfo/cbc
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Cbc mailing list
> Cbc at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/cbc
More information about the Cbc
mailing list