Daniil Khachai

@article{ogorodnikov_3297,

title = {Fault-Tolerant Families of Production Plans: Mathematical Model, Computational Complexity, and Branch-and-Bound Algorithms},

author = {Yuri Ogorodnikov and Roman Rudakov and Daniil KHACHAI and M. Yu. KHACHAI},

url = {https://link.springer.com/article/10.1134/S0965542524700441#citeas},

year  = {2024},

date = {2024-07-01},

journal = {Computational Mathematics And Mathematical Physics},

volume = {64},

pages = {1193-1210},

abstract = {The design of fault-tolerant production and delivery systems is one of the priority areas in modern operations research. The traditional approach to modeling such systems is based on the use of stochastic models that describe the choice of a possible scenario of actions in the event of problems in a production or transportation network. Along with a number of advantages, this approach has a known drawback. The occurrence of problems of an unknown nature that can jeopardize the performance of the entire simulated system significantly complicates its use. This paper introduces the minimax problem of constructing fault-tolerant production plans (reliable production process design problem, RPPDP), the purpose of which is to ensure the uninterrupted operation of a distributed production system with minimal guaranteed cost. It is shown that the RPPDP is NP-hard in the strong sense and remains intractable under quite specific conditions. To find exact and approximate solutions with accuracy guarantees for this problem, branch-and-bound methods are developed based on the proposed compact model of the mixed integer linear program (MILP) and novel heuristic of adaptive search in large neighborhoods (adaptive large neighborhood search, ALNS) as part of extensions of the well-known Gurobi MIP solver. The high performance and complementarity of the proposed algorithms is confirmed by the results of numerical experiments carried out on a public library of benchmarking instances developed by the authors based on instances from the PCGTSPLIB library.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{khachai_3298,

title = {Discrete cutting path problems: a general solution framework and industrial applications},

author = {Daniil KHACHAI and Olga Battaia and Alexander Petunin and Michael Khachay},

url = {https://www.tandfonline.com/doi/full/10.1080/00207543.2024.2365360},

year  = {2024},

date = {2024-06-01},

journal = {International Journal Of Production Research},

pages = {1-21},

abstract = {The optimal tool routing for cutting machines, also known as cutting path optimisation is an important problem in production research. This problem is relevant in various manufacturing environments such as aeronautic, automotive, garment and semiconductor industries. In this paper, we introduce a general solution framework for the discrete Cutting Path Problem which includes: (i) the universal approach to reduce numerous settings of this problem to the appropriate auxiliary instances of the well-known Precedence Constrained Generalized Traveling Salesman Problem; (ii) the proposition of efficient solution methods for finding (sub-) optimal solutions. We carry out extensive computational experiments in order to evaluate performance of the proposed framework and the obtained results demonstrate its efficiency for real-life industrial instances.},

keywords = {},

pubstate = {online},

tppubtype = {article}

}

@article{khachai_3299,

title = {Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm},

author = {Daniil KHACHAI and Ruslan Sadykov and Olga Battaia and Michael Khachay},

url = {https://www.sciencedirect.com/science/article/abs/pii/S0377221723000735?via%3Dihub},

year  = {2023},

date = {2023-09-01},

journal = {European Journal Of Operational Research},

volume = {309},

number = {2},

pages = {488-505},

abstract = {The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) is an extension of two well-known combinatorial optimization problems - the Generalized Traveling Salesman Problem (GTSP) and the Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP), whose path version is known as the Sequential Ordering Problem (SOP). Similarly to the classic GTSP, the goal of the PCGTSP, for a given input digraph and partition of its node set into clusters, is to find a minimum cost cyclic route (tour) visiting each cluster in a single node. In addition, as in the PCATSP, feasible tours are restricted to visit the clusters with respect to the given partial order. Unlike the GTSP and SOP, to the best of our knowledge, the PCGTSP still remain to be weakly studied both in terms of polyhedral theory and algo-rithms. In this paper, for the first time for the PCGTSP, we propose several families of valid inequalities, establish dimension of the PCGTS polytope and prove sufficient conditions ensuring that the extended Balas' pi- and sigma-inequalities become facet-inducing. Relying on these theoretical results and evolving the state-of-the-art algorithmic approaches for the PCATSP and SOP, we introduce a family of MILP-models (formulations) and several variants of the branch-and-cut algorithm for the PCGTSP. We prove their high performance in a competitive numerical evaluation against the public benchmark library PCGTSPLIB, a known adaptation of the classic SOPLIB to the problem in question.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{khachay_3301,

title = {Efficient approximation of the metric CVRP in spaces of fixed doubling dimension},

author = {Michael Khachay and Yuri Ogorodnikov and Daniil KHACHAI},

url = {http://dx.doi.org/10.1007/s10898-020-00990-0},

year  = {2021},

date = {2021-07-01},

journal = {Journal Of Global Optimization},

volume = {80},

pages = {679-710},

abstract = {The capacitated vehicle routing problem (CVRP) is the well-known combinatorial optimization problem having numerous practically important applications. CVRP is strongly NP-hard (even on the Euclidean plane), hard to approximate in general case and APX-complete for an arbitrary metric. Meanwhile, for the geometric settings of the problem, there are known a number of quasi-polynomial and even polynomial time approximation schemes. Among these results, the well-known QPTAS proposed by Das and Mathieu appears to be the most general. In this paper, we propose the first extension of this scheme to a more wide class of metric spaces. Actually, we show that the metric CVRP has a QPTAS any time when the problem is set up in the metric space of any fixed doubling dimension d>1 and the capacity does not exceed polylog(n).},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{chentsov_3302,

title = {Relaxation of the Pursuit-Evasion Differential Game and Iterative Methods},

author = {Alexander Chentsov and Daniil KHACHAI},

url = {http://dx.doi.org/10.1134/S0081543820020042},

year  = {2020},

date = {2020-05-01},

journal = {Proceedings Of The Steklov Institute Of Mathematics},

volume = {308},

number = {Suppl 1},

pages = {35-57},

abstract = {A variant of the program iteration method called stability iterations is used for a differential game of pursuit-evasion. The successful solvability set of one of the problems generating the game is found as a limit of the iterative procedure in the space of sets whose elements are positions of the game. The game is defined by a pair of closed sets, one of the which is the target set in the pursuit problem (the first player's problem) and the other specifies the state constraints in this problem. For the positions not belonging to the solvability set of the pursuit problem, it is interesting to determine the smallest "size" of a neighborhood of the two mentioned sets for which the first player can implement the guidance to the neighborhood of the target set corresponding to this "size" within the similar neighborhood of the second set, i.e., the set specifying the state constraints. Similar constructions are considered for the sets realized at each stage of the iterative procedure. We use the connection of these constructions with the mentioned smallest "size" of neighborhoods of the sets that are parameters of the differential game in the sense of guaranteed realizability of guidance under the replacement of the original sets by these neighborhoods.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{khachay_3303,

title = {Attainable accuracy guarantee for the k-medians clustering in [0, 1]},

author = {Michael Khachay and Daniil KHACHAI},

url = {http://dx.doi.org/10.1007/s11590-018-1305-3},

year  = {2019},

date = {2019-11-01},

journal = {Optimization Letters},

volume = {13},

pages = {1837-1853},

abstract = {We consider the famous k-medians clustering problem in the context of a zero-sum two-player game, which is defined as follows. For given integers n > 1 and k > 1, strategy sets of the first and second players consist of n-samples drawn from the unit segment [0, 1] and partitions of the index set {1,..., n} into k nonempty subsets (clusters), respectively. As a payoff, we take a loss function of the k-medians clustering evaluated in terms of the sample chosen by the first player and the partition taken by the second one. Actually, the payoff coincides with the sum of distances between points of the sample and the nearest center of a cluster. It is easy to verify that this game has no value. In this paper, for any n > 1 and k > 1, we show that 0.5n/(2k - 1) is an upper bound for the lower value of this game. Furthermore, for any k, we prove attainability of this bound for some (n) over bar = (n) over bar (k) and an arbitrary n >= (n) over bar. As a consequence, we show that any n-sample from [0, 1] can be partitioned into k clusters, such that the value of k-medians clustering criterion does not exceed the bound obtained and this bound is tight for sufficiently large n.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{chentsov_3306,

title = {An exact algorithm with linear complexity for a problem of visiting megalopolises},

author = {Alexander Chentsov and M. Yu. KHACHAI and Daniil KHACHAI},

url = {https://link.springer.com/article/10.1134/S0081543816090054#citeas},

year  = {2017},

date = {2017-01-01},

journal = {Proceedings Of The Steklov Institute Of Mathematics},

volume = {295},

number = {Suppl 1},

pages = {38-46},

abstract = {A problem of visiting megalopolises with a fixed number of "entrances" and precedence relations defined in a special way is studied. The problem is a natural generalization of the classical traveling salesman problem. For finding an optimal solution, we give a dynamic programming scheme, which is equivalent to a method of finding a shortest path in an appropriate acyclic oriented weighted graph. We justify conditions under which the complexity of the algorithm depends on the number of megalopolises polynomially, in particular, linearly.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}