help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] infeasible ray


From: Andrew Makhorin
Subject: Re: [Help-glpk] infeasible ray
Date: Thu, 23 Oct 2008 18:50:26 +0300

>> Ray assumes unboundedness, which, in turn, assumes feasibility (either
>> in the primal or dual space).
> I use a wider definition for the primal ray:
> Given the following LP problem:
> lhs <= Ax <= rhs
> l <= x <= u
> min cx
> A primal ray is such an x vector, which fulfills the following problem:
> lhs' <= Ax <= rhs'
> l' <= x <= u',
> cx < 0

> where one component of lhs' or l' is -INF, if the corresponding component of
> lhs or l is -INF, and 0, if the corresponding component is finite. Similarly
> the components of rhs' and u' are 0 or +INF, depending on whether the original
> component is finite or +INF.

> In my point of view, this is a better definition in theoretical sense, because
> we can obtain a proof about the correctness of the solution, if we use this
> definition.

> There are the following cases:
> a) primla-dual feasible problem => the correctness can be checked with the
> equality of the primal and dual objective values
> b) primal feasible, dual infeasible problem => the correctness can be checked
> with a primal feasible solution and a primal ray
> c) dual feasible, primal infeasible problem => the correctness can be checked
> with a dual feasible solution and a dual ray
> d) primal-dual infeasible => a primal and a dual ray provides the proof

> However your definition does not cover the case d).

>> Your question is not quite clear. Which analysis do you need to
>> perform? Note that you always can make lp primal feasible replacing
>> rhs's in all constraints and bounds of all variables by zeros that
>> does not affect the dual polyhedron. Similarly, you can make lp dual
>> feasible replacing all objective coefficients by zeros that does not
>> change the primal polyhedron.
> I will describe my idea more detailed. In the glpk-4.32 on
> glpspx01.c:2768 line we can assume, that the current dual solution
> is a solution for my dual ray definition. However in the 2770-2771
> lines, the dual solution is reset to 0, and therefore the
> glp_get_dual_row() will give back zero for each component.

The dual solution is not reset. If the primal simplex detects primal
infeasibility, it nevertheless computes reduced costs for the original
objective to provide correct basic solution components corresponding
to the final basis reported on exit. Another way could be keeping
reduced costs corresponding to an auxiliary objective, which is the
sum of primal infeasibilities (as, for example, cplex does). However,
I do not think that that would be a good idea, because auxiliary
objective coefficients are computed internally and therefore they
are useless, because the application knows nothing about them.

> Fortunately the primal solution is not reset, and I think it is a
> solution, which minimizes the sum of constraints
> violations(set_aux_obj()).

Note that minimizing the sum of primal infeasibilities is not the
only technique to find a primal feasible basis.

>  If it is true and we can compute the dual
> pair of a given primal solution, then maybe the original dual can be
> set back. This would be more efficient then solving an other
> optimization problem.

In principle, if you need to compute reduced costs for the sum of
infeasibilities, you may simply change the objective coefficients and
then call glp_simplex with itlim = 0 to compute corresponding reduced
costs for the current basis. Another, more efficient way to do the same
is to use the advanced api routine lpx_transform_row (see its
description in the reference manual), which allows computing reduced
costs corresponding to an explictly specified vector of objective
coefficients. In the latter case the problem object remains unchanged.





reply via email to

[Prev in Thread] Current Thread [Next in Thread]