Optimization method finds better decisions than past examples
Outperformance Inverse Optimization: Learning Objective Functions that Outperform Agent Decisions
Artificial Intelligence
Summary
Sometimes decisions we see are not the best possible, even though they look like they were chosen carefully. The authors propose a way to learn new decision-making rules that find solutions better in every way than the ones people originally took. Their method works even when decisions involve complicated yes/no choices and can improve predictions about better actions in new situations. They also show mathematically that the more examples they use, the more reliable their method becomes. Testing on both made-up and real data showed their approach often outperforms older methods.
What this means in practice
- •For supply chain planners: Improve decision models to find better inventory and routing plans than historical choices that may be suboptimal.
- •For financial portfolio managers: Generate improved investment strategies outperforming past portfolio allocations by learning better objective weights.
Authors
Akira Kitaoka
Abstract
Inverse optimization estimates the weights of an objective function that explain observed decisions as optimal solutions, and is used in a variety of fields. For mixed-integer linear programs (MILPs), existing methods aim to reproduce the observations as optimal solutions, and thus learn compromise weights when the observations are suboptimal. We propose outperformance inverse optimization, which instead seeks weights that induce, at each state, an optimal solution outperforming the observed action in every component. We give a loss function that can be evaluated with forward-problem oracles alone and is thus applicable to MILPs, together with gradient-based and DC optimization algorithms for minimizing it. For weights inducing a unique outperforming optimal solution at all observations, we prove that the probability of failing to induce such a solution at a new state (the generalization error) is bounded by a quantity inversely proportional to the number of observations, and that this bound is tight in the number of observations up to logarithmic factors. In experiments on synthetic and real data, the proposed methods improve the prediction of solutions outperforming the actions over existing methods.