[Scip] why the optimal solution has varaible with negative reduced cost

[Ambros Gleixner]

Dear Xiangyong,

so this is not a numerical issue.  Everything is fine here: your 
variable is at its upper bound and hence may have negative reduced cost 
in an optimal solution.

Precisely speaking, an LP solution for a minimization problem is dual 
feasible if
- variables not at their upper bound have nonnegative reduced cost
- variables not at their lower bound have nonpositive reduced cost
- same for slacks of inequality constraints and their dual multipliers

You may want to read about lazy bounds, see the FAQ in the online 
documentation:

http://scip.zib.de/doc/html/FAQ.php

Kind regards,
Ambros


Am 12.08.2014 09:51, schrieb lixiangyong at 163.com:
> Dear Ambros:
>
> Attached please find the attach node lp.
> The optimal solution has non basic variable z_7_6 =1 with reduced cost
> -0.008333. It is strange!!
> Actually for my model, there several variables with negative reduced cost.
>
> Thanks,
>
>
> Xiangyong
>
>
>     *From:* Ambros Gleixner <mailto:gleixner at zib.de>
>     *Date:* 2014-08-12 15:45
>     *To:* scip <mailto:scip at zib.de>
>     *Subject:* Re: [Scip] why the optimal solution has varaible with
>     negative reduced cost
>     Dear Xiangyong,
>     Are the reduced costs very negative or only slightly?  They are allowed
>     to be negative up to minus the value given by the parameter
>     numerics/dualfeastol, i.e., -1e-7 by default (in SCIP 3.1).
>     This is because standard floating-point LP solvers can in general not
>     guarantee exact (primal and dual) feasibility.
>     Kind regards,
>     Ambros
>     Am 12.08.2014 02:14, schrieb lixiangyong at 163.com:
>      > Dear all,
>      >
>      >
>      > I am using SCIP with cplex to implement the branch and price for
>      > minimization problem.
>      >
>      > I found after several columns were added at each round,  the
>     resulting
>      > model has an optimal solution of which some variables have negative
>      > reduced cost (min problem).
>      >
>      > Thanks,
>      >
>      > Xiangyong
>      >
>      >
>      > _______________________________________________
>      > Scip mailing list
>      > Scip at zib.de
>      > http://listserv.zib.de/mailman/listinfo/scip
>      >
>     --
>     ____________________________________________________________
>     Ambros M. Gleixner
>     Zuse Institute Berlin - Matheon - Berlin Mathematical School
>     http://www.zib.de/gleixner
>     _______________________________________________
>     Scip mailing list
>     Scip at zib.de
>     http://listserv.zib.de/mailman/listinfo/scip
>

-- 
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner