Originally posted by: EdKlotz
>
> hi,
>
> I am trying to obtain an infeasibility certificate after network simplex reports CPX_STAT_INFEASIBLE. The documentation states that for CPXNETgetdj(), "If the solution is not feasible (CPXNETsolninfo returns 0 in argument pfeasind_p), the reduced costs are computed with respect to an objective function that penalizes infeasibilities." But as far as I can tell the pair of vectors returned by CPXNETgetpi() and CPXNETgetdj() are computed relative to the ordinary objective function...
To test if they are being computed relative to the phase II objective
function, try setting all of the phase II objective coefficients to 0. Then, if CPXNETgetpi
returns all zeros, you will have confirmed that. However, I expect you will
not see all zeros, as explained below.
I believe CPLEX's network optimizer actually uses a weighted
phase I/phaseII objective where it combines the two. The
documentation for CPXNETgetdj seems to imply that, as it says "
an objective
function". But, it doesn't provide much detail. Thus, I think you will see some
phase II information in there, so I don't think CPXNETgetpi and CPXNETgetdj
will provide you the dual way information that you seek. Perhaps you
should transfer the network basis to the regular LP API, then reoptimize
with the primal simplex iteration. Primal simplex should declare infeasibility
at iteration 0, so the only extra work really involves the basis factorization
(which won't take long, particularly given the network structure). Then you
can just use CPXgetpi and CPXgetdj, which will be computed relative to the
phase I objective that provides a dual ray.
Another approach would be to reset the phase II objective coefficients to
all zeros. Reoptimize from the advanced basis. Then, the weighted objective
that CPLEX uses will essentially be a phase I objective, and CPXNETgetpi
and getdj will return values that provide a dual ray.
>
> I don't think there is a problem in my code, because when I use the primal simplex LP solver (with a macro that changes CPXNET... into CPX..., and alternative code that sets up the problem using CPXnewrows instead of CPXNETaddnodes and CPXaddcols instead of CPXNETaddarcs), then everything works perfectly, including my assertions that ensure the result is really an unbounded dual ray.
Also, try to reproduce the unexpected behavior using interactive CPLEX.
That's one way to help confirm that a problem is not in your code. But,
I tend to agree that the issue doesn't involve your code. I think the
issue here is just that the network weighted
objective CPLEX uses doesn't provide a dual ray.
>
> Perhaps, the network solver is detecting infeasibility by some kind of preprocessing step before actually setting up the artificial arcs/phase 1 objective? I have presolve turned off (CPX_PARAM_PREIND), but is there another setting for network simplex presolve? I couldn't find one.
There is no special presolve for the network simplex method in CPLEX.
I don't think this explains what you see. If presolve detects infeasibility,
any call to a function (network or otherwise) to obtain solution values will
return an error status indicating no solution exists. Also, if this
were the case, you would see no network simplex iterations before the declaration of infeasibility. Is that the case?
>
> It does appear that I have run up against a CPLEX limitation, but if it might be a CPLEX bug instead, then I could test my code with CPLEX 10.0 intead of CPLEX 12.1 acadamic initiative, I thought I would check here for suggestions before trying any further debugging though. Note that I haven't checked CPXNETsolninfo as suggested in the docs for CPXNETgetdj(), but I am sure that CPXNETgetstat() is just as good. Also I don't have the latest fixpack, but my understanding is the fixpack is for 12.2 not 12.1 and anyway, only affects MIP.
Yes, the fixpack is for 12.2. Also, I don't see any bug fixes for the network optimizer between 12.1 and the fixpack for 12.2, so I don't expect downloading the latest version will "fix" the behavior you have encountered.
#CPLEXOptimizers#DecisionOptimization