8

This may depend on how you define "reduced costs". If you mean reduced costs as computed by the simplex algorithm, then no, it is not possible that all are strictly positive due to the mechanics of the algorithm. If you mean $c^\prime - y^{*\prime}A$ for the original variables and $y^{*\prime} I$ for the surplus variables, where $y^*$ is any optimal dual ...


4

My guess would be that the variable is not basic, it is non-basic but at the upper bound of 1.0. Modern solvers use the generalized simplex method which allows for lower and upper bounds on a variable. If a variable is upper bounded, its optimal reduced cost needs to be non-positive. I can't say I fully understand the output you pasted, but it looks like ...


4

If your sub-problem is a shortest path problem on a complete graph, without resource constraints, you can delete vertices which don't decrease the reduced cost. Indeed, for any path containing such a vertex, removing the vertex gives another path which is both feasible for the sub-problem and which corresponds to a master problem column with smaller reduced ...


1

I think I have answered my own question over the last day. I found that fixing non-basic variable with non-zero reduced was enough to keep the optimal value of higher priority goals. The reason I was not getting the solution to retain the higher priority goal's optimality was due to a different reason. I have been using a tolerance to limit the upper bound ...


Only top voted, non community-wiki answers of a minimum length are eligible