Joint Learning and Optimization of Unknown Combinatorial Utility Functions

This work considers the problem of automatically discovering the solution preferred by a decision maker (DM). Her preferences are formalized as a combinatorial utility function, but they are not fully defined at the beginning and need to be learnt during the search for the satisficing solution. The initial information is limited to a set of catalog features from which the decisional variables of the DM are to be selected. An interactive optimization procedure is introduced, which iteratively learns an approximation of the utility function modeling the quality of candidate solutions and uses it to generate novel candidates for the following refinement. The source of learning signals is the decision maker, who is fine-tuning her preferences based on the learning process triggered by the presentation of tentative solutions. The proposed approach focuses on combinatorial utility functions consisting of a weighted sum of conjunctions of predicates in a certain theory of interest. The learning stage exploits the sparsity-inducing property of 1-norm regularization to learn a combinatorial function from the power set of all possible conjunctions of the predicates up to a certain degree. The optimization stage consists of maximizing the learnt combinatorial utility function to generate novel candidate solutions. The maximization is cast into an Optimization Modulo Theory problem, a recent formalism allowing to efficiently handle both discrete and continuous-valued decisional features. Experiments on realistic problems demonstrate the effectiveness of the method in focusing towards the optimal solution and its ability to recover from suboptimal initial choices.