• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedUser profile (HSE staff only)SearchMenu

Combinatorial oOptimization Problems with Probability Constraints

Student: Andrey Shilov

Supervisor: Sergey Ketkov

Faculty: Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod)

Educational Programme: Data Mining (Master)

Year of Graduation: 2021

The application of the Distributionally Robust Optimization approach to the problem of linear combinatorial optimization with incomplete data sets is studied in this work. This paper aims at finding the procedure for the transformation of the finite data set to the least conservative estimate of the minimized function, which satisfies the specified asymptotic guarantees. In contrast to the related studies, presented in the literature, we consider the incomplete data sets, i. e. such sets that the number of observations of each component of the random cost vector may vary. We argue that such problem setting might be more applicable to practical conditions. We introduce the algorithm of solving the outlined problem, obtaining a particular distributionally robust optimization problem. More specifically, the decision-maker optimizes the worst-case estimate across all probability distributions with given component-wise relative entropy distance from the empirical marginal distribution for each component. We prove the weak optimality of the outlined method and the asymptotical exponential decrease of the error probability when the size of the data set grows. Finally, we conduct the numerical experiments, which compare our methods with the analogues, presented in the literature.

Student Theses at HSE must be completed in accordance with the University Rules and regulations specified by each educational programme.

Summaries of all theses must be published and made freely available on the HSE website.

The full text of a thesis can be published in open access on the HSE website only if the authoring student (copyright holder) agrees, or, if the thesis was written by a team of students, if all the co-authors (copyright holders) agree. After a thesis is published on the HSE website, it obtains the status of an online publication.

Student theses are objects of copyright and their use is subject to limitations in accordance with the Russian Federation’s law on intellectual property.

In the event that a thesis is quoted or otherwise used, reference to the author’s name and the source of quotation is required.

Search all student theses