[SCIP] How to get an accurate dual solution to a LP?

[Jakob Witzig]

Hi Sebastian,

since SCIP is MIP solver, it usually doesn't take too much care about 
dual solution values. Thus, I would recommend to solve your LPs with 
SoPlex directly or to change your setup and use SCIP as a 
branch-and-price framework. However, if you would like to stay with your 
current setup you also have to disable propagation:

propagating/maxrounds = 0
propagating/maxroundsroot = 0

With enabled propagation, only 1163 out of 66789 constraints enter the 
LP relaxation, all others were deleted / deactivated during propagation. 
Thus, you have solved a different problem and, of course, the dual 
multipliers may not match.

Best,
Jakob

Am 11.11.19 um 15:43 schrieb Sebastian Schmidt:
> Hi,
>
> I'm trying to swap from Gurobi to SCIP in my column generation based 
> algorithm for MinCostFlow. For this, I need SCIP to solve a linear 
> program and generate an accurate dual solution. The dual solution that 
> SCIP produces when presolving is disabled seems to be accurate, but 
> violates some dual constraints.
>
> I have set the relative gap limit to zero, and the absolute to 0.1, 
> half the value of the gcd of my weights and bounds.
>
> I have implemented column generation by regenerating the LP for every 
> round from scratch, so I don't use any more functionality of SCIP than 
> LP solving.
>
> I have a self-implemented abstract layer between the LP solver and the 
> LP generator, and I just swapped out the solver. Using Gurobi, 
> everything worked fine, so I'm sure there is no bug elsewhere.
>
> Is there any parameter I need to set to make SCIP produce a feasible 
> dual solution, besides setting the presolving maxrounds to zero?
>
> In case this is a bug in SCIP, I attached the problem that gets solved 
> wrongly. In the code, I set the bounds of all variables to >= 0 and <= 
> SCIPinfinity. Also I disabled presolving as described above.
> The problem is that the dual of Route_choice_constraint_0x5621d4278800 
> gets set to 193. But by the goal function coeffecient of the primal 
> variable Route_choice_0x5621d4278800_1 which is 191, it should be 
> bound to 191. This variable appears besides in the goal function only 
> in constraint Route_choice_constraint_0x5621d4278800. So in the dual 
> problem there must be a constraint 
> Route_choice_constraint_0x5621d4278800 <= 191.
>
> Kind Regards,
> Sebastian Schmidt
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip

-- 
Jakob Witzig

Zuse Institute Berlin (ZIB)

Division Mathematical Optimization and Scientific Information
Research Group Mathematical Optimization Methods

Takustrasse 7
14195 Berlin

Tel. : +49 (0)30 84185-416
Fax  : +49 (0)30 84185-269
email: witzig at zib.de

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