I'm trying to understand a paper (Systems Analysis and Optimization of Local Water Supplies in Los Angeles http://ascelibrary.org/doi/10.1061/%28ASCE%29WR.1943-5452.0000803) that seems to use optimization in a curious way. Although parts of the study are somewhat complex, the study appears to ultimately use a relatively straight-forward, linear, network flow problem. Screengrab of model formulation. Later in the paper, the authors' explain how the linear program has no primal feasible solution, so they select a feasible dual solution instead:

Notably, Artes does not report optimal solutions. The formulation and constraints typically result in a primal infeasible solution, i.e., no solution exists that satisfies all of the requirements. Constraints for observed flows in subwatersheds and demands for some smaller retailers such as mutual water companies and selected municipal utilities cannot be met through the model configuration based on available data. Gurobi uses the Simplex method to solve linear programming problems. Upon determining infeasibility for the current basis, Gurobi iterates through pivots until identifying a feasible solution for the dual or primal problems. For this analysis, Gurobi consistently identified a feasible solution to the dual problem while the primal problem remained infeasible and thus not optimal because noted constraints are not met. Presented results are feasible dual problem solutions that, despite nonoptimality, yield insights for urban water management. Relaxing key constraints could improve performance.

I understand the fundamentals of linear programming, including the concept of duality. What I don't understand is how selecting a feasible dual solution provides useful information in the context of understanding the system. My understanding is that the Duality Theorem of Linear Programming indicates that if the primal (dual) is infeasible, then the dual (primal) has an unbounded objective, so a dual (primal) feasible solution seems arbitrary and meaningless.

In short, I am puzzled that the paper uses this optimization method at all given primal infeasibility. In either the specific context of this paper--or in any optimization problem generally--what useful insights can a feasible dual solution provide when the primal is infeasible?

Thanks in advance for your consideration and input!

  • 1
    $\begingroup$ This does seem peculiar to me. It seems like if you have a primal infeasible problem then you need to go back to the modeling level to think about relaxing your constraints. (For example, replace strict equalities with penalties for deviation). $\endgroup$ – Ian Sep 14 '17 at 16:08
  • $\begingroup$ Thanks, @Ian, for your input. I think your idea of using a penalty method would make a lot of sense. $\endgroup$ – user89413 Sep 14 '17 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.