{
  "id": "2304.01343",
  "version": "v1",
  "published": "2023-04-03T20:18:41.000Z",
  "updated": "2023-04-03T20:18:41.000Z",
  "title": "Distributionally robust mixed-integer programming with Wasserstein metric: on the value of uncertain data",
  "authors": [
    "Sergey S. Ketkov"
  ],
  "categories": [
    "math.OC",
    "cs.DM"
  ],
  "abstract": "This study addresses a class of linear mixed-integer programming (MIP) problems that involve uncertainty in the objective function coefficients. The coefficients are assumed to form a random vector, which probability distribution can only be observed through a finite training data set. Unlike most of the related studies in the literature, we also consider uncertainty in the underlying data set. The data uncertainty is described by a set of linear constraints for each random sample, and the uncertainty in the distribution (for a fixed realization of data) is defined using a type-1 Wasserstein ball centered at the empirical distribution of the data. The overall problem is formulated as a three-level distributionally robust optimization (DRO) problem. We prove that for a class of bi-affine loss functions the three-level problem admits a linear MIP reformulation. Furthermore, it turns out that in several important particular cases the three-level problem can be solved reasonably fast by leveraging the nominal MIP problem. Finally, we conduct a computational study, where the out-of-sample performance of our model and computational complexity of the proposed MIP reformulation are explored numerically for several application domains.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-04-03T20:18:41.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "distributionally robust mixed-integer programming",
      "uncertain data",
      "wasserstein metric",
      "mip reformulation",
      "three-level problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}