3.7.207. Regret based heuristics in matrix problems

Assume you have a discrete optimisation problem involving a matrix $ℳ$ of decision variables such that there is a cost variable attached to each row of $ℳ$. Moreover assume that the cost associated with each row corresponds to a sum of elementary costs connected with each decision variable of the same row (e.g., we have a $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚌𝚝𝚛}$ or a $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚠𝚒𝚝𝚑}_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ constraint on each row of $ℳ$). Now, suppose we want to use a heuristics for fixing the decision variables of matrix $ℳ$ row by row. In this context a question is which row to select first. Since the cost variable ${c}_{r}$ associated with a row $r$ corresponds to a sum of elementary costs, it is very unlikely that the cost variable ${c}_{r}$ has a hole in its domain. Consequently, we cannot any more use a conventional regret based heuristics which relies on the fact that we have holes in the domains of the cost variables. We still want to use the idea of finding the variable that would potentially cause the biggest increase in cost in the worst case, i.e. if it would have to be assigned to its maximum value. For this purpose we consider the variable for which the difference between its largest value and its smallest value is maximal. In our context we select the row $r$ for which the corresponding cost variable maximises such difference. First we enumerate in increasing value order on the cost variable associated with row $r$. Second we fix all decision variables of row $r$, using for instance the heuristics described in labelling by increasing cost. Using such cost based heuristics has both some advantage and some drawback:

• The big potential advantage is that, if we can find a first solution at all, then this solution should have a rather small overall cost.

• The potential drawback is that, depending on how strong the row constraints propagate from the maximum total cost associated with a row back to the decision variables of the row, it may be very difficult to find a feasible solution (since assigning the cost variable of a row to its minimum value potentially creates an infeasible problem for which we need to develop a large search tree).