Optimal transport has been very successful for various machine learning tasks; however, it is known to suffer from the curse of dimensionality. Hence, dimensionality reduction is desirable when applied to high-dimensional data with low-dimensional structures. The kernel max-sliced (KMS) Wasserstein distance is developed for this purpose by finding an optimal nonlinear mapping that reduces data … Read more
The concept of counterfactual explanations (CE) has emerged as one of the important concepts to understand the inner workings of complex AI systems. In this paper, we translate the idea of CEs to linear optimization and propose, motivate, and analyze three different types of CEs: strong, weak, and relative. While deriving strong and weak CEs … Read more
We propose a criterion space search algorithm for bi-objective mixed integer linear programming problems. The Pareto frontier of these problems can have a complex structure, as it can include isolated points, open, half-open and closed line segments. Therefore, its exact detection is an achievable though hard computational task. Our algorithm works by alternating the resolution … Read more
Security agencies throughout the world use bodyguards to protect government officials and public figures. In this paper, we consider a two-person zero-sum game between a defender who allocates such bodyguards to protect several targets and an attacker who chooses one target to attack. Because the number of feasible bodyguard allocations grows quickly as either the … Read more
Problem description: We study the problem of designing large-scale resilient relay logistics hub networks. We propose a model of Capacitated Relay Network Design under Stochastic Demand and Consolidation-Based Routing (CRND-SDCR), which aims to improve a network’s efficiency and resilience against commodity demand variability through integrating tactical decisions. Methodology: We formulate CRND-SDCR as a two-stage stochastic … Read more
Dantzig-Wolfe decomposition is a well-known classical method for solving huge linear optimization problems with a block-angular structure. The most computationally expensive process in the method is pricing: solving block subproblems for a dual variable to produce new columns. Therefore, when we want to solve a slightly perturbated problem in which the block-angular structure is preserved … Read more
Last-mile delivery services worldwide have embraced crowdshipping, which involves both regular and occasional drivers to reduce transportation costs and potentially ensure timely deliveries. However, real-world uncertainty in travel times leads to delays in deliveries. Motivated by empirical studies on customer impatience with late deliveries, this paper focuses on a service-centric Vehicle Routing Problem with Crowdshipping … Read more
Goldstein’s 1977 idealized iteration for minimizing a Lipschitz objective fixes a distance – the step size – and relies on a certain approximate subgradient. That “Goldstein subgradient” is the shortest convex combination of objective gradients at points within that distance of the current iterate. A recent implementable Goldstein-style algorithm allows a remarkable complexity analysis (Zhang … Read more
We consider geodesically convex optimization problems involving distances to a finite set of points A in a CAT(0) cubical complex. Examples include the minimum enclosing ball problem, the weighted mean and median problems, and the feasibility and projection problems for intersecting balls with centers in A. We propose a decomposition approach relying on standard Euclidean … Read more
Heterogeneous datasets emerge in various machine learning or optimization applications that feature different data sources, various data types and complex relationships between variables. In practice, heterogeneous datasets are often partitioned into smaller well-behaved ones that are easier to process. However, some applications involve expensive-to-generate or limited size datasets, which motivates methods based on the whole … Read more