Potential solutions of linear systems: The multi-criteria multiple constraint levels program

The realistic modeling of decision problems requires considerable flexibility in the model structure. Frequently one is faced with problems involving multiple criteria for which the constraint level is acceptable if a certain parameter (which may be a random variable) lies within a prescribed set. Furthermore, in formulating the problem, the criteria and constraints may be interchangeable. This requires a treatment which is more general than the nondominated solution in a multicriteria problem. We shall introduce the concept of a potential solution to cope with the above problem. To effectively locate these potential solutions, a generalization of the multicriteria (MC) simplex method, which handles multiple constraint levels (right hand sides) is developed. Geometric properties of adjacent potential solutions will be described together with a computational procedure which is based on the “connectedness” of the set of potential solutions. The natural duality relationship which exists in the double-MC simplex method and its consequences are also explored.