[SCIP] Could you please tell me what is a pesudo solution (non-fixed integer solution) ?

Mon Dec 18 18:00:42 CET 2017

Dear Zhu Waiming,

there are some occasions when no fractional variables are available for 
branching. In this case, the BRANCHEXECPS callback is called that is 
supposed to branch on an unfixed integer variable.

What are those occasions? First, it may happen that SCIP encounters 
numerical troubles when solving the LP and the LP solver cannot return a 
feasible and optimal solution. In this case, SCIP performs pseudo 
solution branching in the hope that afterwards, the LP is numerically 
better conditioned.

In your case, it looks like there are no variables with fractional value 
in the LP solution. However, SCIP does not seem to use the LP solution 
as a dual bound. I would assume that your pricer does not set the result 
flag to SCIP_SUCCESS when you did not find a solution. If it would, you 
would signal SCIP that you proved that there is no improving column and 
thus, the master LP was solved to optimality. If you do not set it to 
SCIP_SUCCESS, SCIP must assume that you just stopped pricing, but there 
might be improving variables (this is sometimes called "early 
branching"). However, if this is the case, the LP solution does not 
provide a valid dual bound.

I would suggest you check if you set the result pointer. If you forgot 
this although you priced to the end, SCIP should be finished in the root 
node directly after applying the dual bound (which should match the 
primal bound for this run). If you indeed intended to perform early 
branching, please try to continue pricing to allow SCIP to obtain dual 
bounds. Alternatively, you can also set a dual bound via the lowerbound 
pointer.

Best,
Gerald

On 04.12.2017 08:16, 朱外明 wrote:
> Dear Ambros,
>
>     Thanks very much for your kind answering me on foregoing 
> questions. Now my program is OK on running but abnormal on solving the 
> problem. At the begining of branch and price, SCIP would produce 
> pesudo solutions (non-fixed integer solutions). As a result, I must 
> realize a BRANCHEXECPS branching method (I used the _SCIPbranchVar_ 
> <http://scip.zib.de/doc/html/group__PublicBranchingMethods.php#gabb0e80df81b921f02e8d63ec44de609c> 
> method inside this branching). Then the searching steps into 
> BRANCHEXECLP branching in which fractional variable values are available.
>
>     Here is something difficult to be understood. What is a pesudo 
> solution? Does not SCIP solve the linear relaxation of master problem 
> directly? If yes, fractional variable values should be avalaible at 
> the root node. Why it is not the truth from my experience? Dear 
> Ambros, could you please tell me something about this ?
> *
> *
>     Some displaying information are listed:
>
> --------------------------------------------------------------------------------------------------------------------------
> SCIP> read data/data.scp
> read problem <data/data.scp>
> ============
> original problem has 5 variables (5 bin, 0 int, 0 impl, 0 cont) and 15 
> constraints
> SCIP> optimize
> feasible solution found by trivial heuristic after 0.0 seconds, 
> objective value 5.000000e+04
> presolving:
>    (0.0s) probing cycle finished: starting next cycle
> presolving (1 rounds: 1 fast, 1 medium, 1 exhaustive):
>  0 deleted vars, 0 deleted constraints, 0 added constraints, 0 
> tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
>  0 implications, 0 cliques
> presolved problem has 5 variables (5 bin, 0 int, 0 impl, 0 cont) and 
> 15 constraints
>      15 constraints of type <setppc>
> transformed objective value is always integral (scale: 1)
> Presolving Time: 0.01
> transformed 1/1 original solutions to the transformed problem space
>  time | node  | left  |LP iter|LP it/n| mem |mdpt |frac |vars |cons 
> |cols |rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap
>   0.0s|     1 |     0 |    12 |     - | 918k|   0 |   0 | 110 | 15 | 
> 110 |  15 |   0 |   0 |   0 |      --      | 5.000000e+04 |    Inf
> r 0.0s|     1 |     0 |    12 |     - | 921k|   0 |   0 | 110 | 15 | 
> 110 |  15 |   0 |   0 |   0 |      --      | 5.000000e+00 |    Inf
>   0.0s|     1 |     0 |    12 |     - | 921k|   0 |   0 | 110 | 15 | 
> 110 |  15 |   0 |   0 |   0 |      --      | 5.000000e+00 |    Inf
> [src/branch_scp.c:219] debug: start BRANCHEXECPS branching !
> [src/branch_scp.c:356] debug:  -> 110 candidates, selected candidate 
> 109: variable <>
>   0.0s|     1 |     2 |    12 |     - | 922k|   0 |   0 | 110 | 15 | 
> 110 |  15 |   0 |   0 |   0 |      --      | 5.000000e+00 |    Inf
> [src/branch_scp.c:219] debug: start BRANCHEXECPS branching !
> [src/branch_scp.c:356] debug:  -> 109 candidates, selected candidate 
> 108: variable <>
> [src/branch_scp.c:219] debug: start BRANCHEXECPS branching !
> ......
> [src/branch_scp.c:356] debug:  -> 62 candidates, selected candidate 
> 61: variable <>
> [src/branch_scp.c:219] debug: start BRANCHEXECPS branching !
> [src/branch_scp.c:356] debug:  -> 61 candidates, selected candidate 
> 60: variable <>
>
> [src/branch_scp.c:77] debug:  start BRANCHEXECLP branching 
> ![src/branch_scp.c:85] debug: start branching at node 96, depth 50
> .............
> --------------------------------------------------------------------------------------------------------------------------
>
>     Thank you.
>
>     With best regards!
>
>
> -----------------------------------------------
> Your sincerely follower, Zhu Waiming
> zhuwaiming at mail.hfut.edu.cn
> Hefei University of technology, China
> orcid.org/0000-0001-7134-6584
> _https://www.researchgate.net/profile/Zhu_Waiming_
> 2017-12-04
> */_
> _/*
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20171218/e12f26dd/attachment.html>