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

[Ambros Gleixner]

Hi,

Am 12.08.2014 11:30, schrieb lixiangyong at 163.com:
> Dear Ambros,
>
> Thanks.
> I do not understand case 3:
> same for slacks of inequality constraints and their dual multipliers
> Could you please explain it?

- activities not at the right-hand side have nonnegative dual multiplier
- activities not at the left-hand side have nonpositive dual multiplier


> In my model, all x variables are binary. All z variables are continuous
> with bounds [0,1].
>
> Do you mean I should use lazy bound for x variables in my branch-and-price?

If the upper bounds x_i <= 1 are enforced by the constraints, then this 
is probably the most convenient way to handle it.

Cheers,
Ambros



>
>
> Thanks,
>
> Xiangyong
>
>     *From:* Ambros Gleixner <mailto:gleixner at zib.de>
>     *Date:* 2014-08-12 16:14
>     *To:* lixiangyong at 163.com <mailto:lixiangyong at 163.com>
>     *CC:* scip <mailto:scip at zib.de>
>     *Subject:* Re: [Scip] why the optimal solution has varaible with
>     negative reduced cost
>     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
>

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