[Scip] why the optimal solution has varaible with negative reduced cost
lixiangyong at 163.com
lixiangyong at 163.com
Tue Aug 12 11:30:36 CEST 2014
Dear Ambros,
Thanks.
I do not understand case 3:
same for slacks of inequality constraints and their dual multipliers
Could you please explain it?
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?
Thanks,
Xiangyong
From: Ambros Gleixner
Date: 2014-08-12 16:14
To: lixiangyong at 163.com
CC: scip
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20140812/7eaee60c/attachment.html>
More information about the Scip
mailing list