The location-covering problem: A bicriterion interactive approach

The Location-Covering Problem (LCP) is a well-known combinatorial optimization problem and it is well studied for the original single criterion formulation. In this work the authors present a bicriteria integer formulation of the LCP (BLCP) and develop an interactive approach for BLCP. They propose an interactive method based upon the progressive and selective familiarization of the set of Pareto optimal or non-dominated solutions. In each step of the human/computer dialogue, the analyst just asks the Decision Maker (DM) to give indications about the sub regions to carry on the search for non-dominated solutions (nds). The process only ends when the DM considers to have ‘sufficient’ knowledge about the nds set. There are no irrevocable decisions along the process, and the method is not too demanding with respect to information required from the DM in each interaction. The method is well adapted to interactive dialogue. Another favorable aspect of this method is that a single-criterion 0-1 programming problem has to be solved at each step and the DM is able to find every non-dominated solution of the problem, namely the supported (those located on the convex hull) and the non supported (in the duality ‘gaps’ between the points that define the convex hull).