1,720,979 research outputs found
Emerging optimization problems for distribution in same-day delivery
No full textSame-day delivery (SDD) has become a new standard to satisfy the "instant gratification" of online customers. Despite existing powerful technologies deployed in last-mile delivery, SDD services face new decision-making challenges on the tradeoff between delivery costs and time. In addition, new concerns on environmental issues, customer satisfaction, and fairness arise. Researchers have explored various approaches to face these challenges in SDD, where data uncertainty plays a fundamental role. In this paper, we carefully review the emerging routing problems and solutions proposed in the existing literature for SDD services. We survey papers on how to manage dynamic order arrivals, how to allocate time slots for deliveries, how to select the right delivery options, how to design pickup and delivery routes, and how to partition delivery areas and decide the composition of the fleet. We also propose mathematical formulations for representative problems. Finally, we sketch managerial insights and identify future research directions
Reinforcement Learning Approaches for the Orienteering Problem with Stochastic and Dynamic Release Dates
No full textIn this paper, we study a sequential decision-making problem faced by e-commerce carriers related to when to send out a vehicle from the central depot to serve customer requests and in which order to provide the service, under the assumption that the time at which parcels arrive at the depot is stochastic and dynamic. The objective is to maximize the expected number of parcels that can be delivered during service hours. We propose two reinforcement learning (RL) approaches for solving this problem. These approaches rely on a look-ahead strategy in which future release dates are sampled in a Monte Carlo fashion, and a batch approach is used to approximate future routes. Both RL approaches are based on value function approximation: One combines it with a consensus function (VFA-CF) and the other one with a two-stage stochastic integer linear programming model (VFA-2S). VFA-CF and VFA-2S do not need extensive training as they are based on very few hyperparameters and make good use of integer linear programming (ILP) and branch-and-cut-based exact methods to improve the quality of decisions. We also establish sufficient conditions for partial characterization of optimal policy and integrate them into VFA-CF/VFA-2S. In an empirical study, we conduct a competitive analysis using upper bounds with perfect information. We also show that VFA-CF and VFA-2S greatly outperform alternative approaches that (1) do not rely on future information (2) are based on point estimation of future information, (3) use heuristics rather than exact methods, or (4) use exact evaluations of future rewards
On integer and bilevel formulations for the k-vertex cut problem
Get PDFThe family of critical node detection problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problem asks for determining the minimum weight subset of nodes whose removal disconnects a graph into at least k components. We provide two new integer linear programming formulations, along with families of strengthening valid inequalities. Both models involve an exponential number of constraints for which we provide poly-time separation procedures and design the respective branch-and-cut algorithms. In the first formulation one representative vertex is chosen for each of the k mutually disconnected vertex subsets of the remaining graph. In the second formulation, the model is derived from the perspective of a two-phase Stackelberg game in which a leader deletes the vertices in the first phase, and in the second phase a follower builds connected components in the remaining graph. Our computational study demonstrates that a hybrid model in which valid inequalities of both formulations are combined significantly outperforms the state-of-the-art exact methods from the literature
Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem
Get PDFGiven an undirected graph, we study the capacitated vertex separator problem
that asks to find a subset of vertices of minimum cardinality, the removal of which induces a
graph having a bounded number of pairwise disconnected shores (subsets of vertices) of
limited cardinality. The problem is of great importance in the analysis and protection of communication or social networks against possible viral attacks and for matrix decomposition algorithms. In this article, we provide a new bilevel interpretation of the problem and model it
as a two-player Stackelberg game in which the leader interdicts the vertices (i.e., decides on
the subset of vertices to remove), and the follower solves a combinatorial optimization problem on the resulting graph. This approach allows us to develop a computational framework
based on an integer programming formulation in the natural space of the variables. Thanks
to this bilevel interpretation, we derive three different families of strengthening inequalities
and show that they can be separated in polynomial time. We also show how to extend these
results to a min-max version of the problem. Our extensive computational study conducted
on available benchmark instances from the literature reveals that our new exact method is
competitive against the state-of-the-art algorithms for the capacitated vertex separator problem and is able to improve the best-known results for several difficult classes of instances.
The ideas exploited in our framework can also be extended to other vertex/edge deletion/
insertion problems or graph partitioning problems by modeling them as two-player Stackel-
berg games and solving them through bilevel optimization
Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems
Get PDFWe study a family of discrete optimization problems asking for the maximization of
the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set
of coefficients taking values from a discrete set of scenarios. The function models the
utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of metaitems. This
problem generalizes the problem introduced by Ahmed S, Atamtürk A (Mathematical
programming 128(1-2):149–169, 2011), and it can be modeled as a mixed integer
nonlinear program involving binary decision variables associated with the items and
metaitems. Its goal is to find a subset of metaitems that maximizes the total utility
corresponding to the items it covers. It has applications to, among others, maximal
covering location, and influence maximization problems. In the paper, we propose a
double-hypograph decomposition which allows for projecting out the variables associated with the items by separately exploiting the structural properties of the utility
function and of the set-union operator. Thanks to it, the utility function is linearized via
an exact outer-approximation technique, whereas the set-union operator is linearized in two ways: either (i) via a reformulation based on submodular cuts, or (ii) via a
Benders decomposition. We analyze from a theoretical perspective the strength of the
inequalities of the resulting reformulations, and embed them into two branch-and-cut
algorithms. We also show how to extend our reformulations to the case where the
utility function is not necessarily increasing. We then experimentally compare our
algorithms inter se, to a standard reformulation based on submodular cuts, to a state-of-the-art global-optimization solver, and to the greedy algorithm for the maximization
of a submodular function. The results reveal that, on our testbed, the method based
on combining an outer approximation with Benders cuts significantly outperforms the
other ones
Mathematical programming formulations for the Collapsed k-Core Problem
No full textIn social network analysis, the size of the k-core, i.e., the maximal induced subgraph of the network with minimum degree at least k, is frequently adopted as a typical metric to evaluate the cohesiveness of a community. We address the Collapsed k-Core Problem, which seeks to find a subset of b users, namely the most critical users of the network, the removal of which results in the smallest possible k-core. For the first time, both the problem of finding the k-core of a network and the Collapsed k-Core Problem are formulated using mathematical programming. On the one hand, we model the Collapsed k-Core Problem as a natural deletion-round-indexed Integer Linear formulation. On the other hand, we provide two bilevel programs for the problem, which differ in the way in which the k-core identification problem is formulated at the lower level. The first bilevel formulation is reformulated as a single-level sparse model, exploiting a Benders-like decomposition approach. To derive the second bilevel model, we provide a linear formulation for finding the k-core and use it to state the lower-level problem. We then dualize the lower level and obtain a compact Mixed-Integer Nonlinear single-level problem reformulation. We additionally derive a combinatorial lower bound on the value of the optimal solution and describe some pre-processing procedures, and valid inequalities for the three formulations. The performance of the proposed formulations is compared on a set of benchmarking instances with the existing state-of-the-art solver for mixed-integer bilevel problems proposed in (Fischetti, Ljubić, Monaci, and Sinnl, 2017)
An exact method for binary fortification games
Get PDFA fortification game (FG) is a three-level, two-player hierarchical game, also known as defender-attacker- defender game, in which at the uppermost level, the defender selects some assets to be protected from potential malicious attacks. At the middle level, the attacker solves an interdiction game by depreciating unprotected assets, i.e., reducing the values of such assets for the defender, while at the innermost level the defender solves a recourse problem over the surviving or partially damaged assets. Fortification games have applications in various important areas, such as military operations, design of survivable networks, protection of facilities or power grid protection. In this work, we present an exact solution algorithm for FGs, in which the recourse problems correspond to (possibly NP-hard) combinatorial optimization prob- lems. The algorithm is based on a new generic mixed-integer linear programming reformulation in the natural space of fortification variables. Our new model makes use of fortification cuts that measure the contribution of a given fortification strategy to the objective function value. These cuts are generated when needed by solving separation problems, which correspond to (modified) middle-level interdiction games. We design a branch-and-cut-based solution algorithm based on fortification cuts, their strength- ened versions and other speed-up techniques. We present a computational study using the knapsack for- tification game and the shortest path fortification game. For the latter one, we include a comparison with a state-of-the-art solution method from the literature. Our algorithm outperforms this method and allows us to solve previously unsolved instances with up to 330 386 nodes and 1 202 458 arcs to optimality
A Bilevel Approach for Compensation and Routing Decisions in Last-Mile Delivery
No full textIn last-mile delivery logistics, peer-to-peer logistic platforms play an important role in connecting senders, customers, and independent carriers to fulfill delivery requests. As the carriers are not under the platform's control, the platform has to anticipate their reactions while deciding how to allocate the delivery operations. Indeed, carriers' decisions largely affect the platform's revenue. In this paper, we model this problem using bilevel programming. At the upper level, the platform decides how to assign the orders to the carriers; at the lower level, each carrier solves a profitable tour problem to determine which offered requests to accept, based on her own profit maximization. Possibly, the platform can influence carriers' decisions by determining also the compensation paid for each accepted request. The two considered settings result in two different formulations: the bilevel profitable tour problem with fixed compensation margins and with margin decisions, respectively. For each of them, we propose single-level reformulations and alternative formulations where the lower-level routing variables are projected out. A branch-and-cut algorithm is proposed to solve the bilevel models, with a tailored warm-start heuristic used to speed up the solution process. Extensive computational tests are performed to compare the proposed formulations and analyze solution characteristics
A new branch-and-bound algorithm for the maximum edge-weighted clique problem
Get PDFWe study the maximum edge-weighted clique problem, a problem related to the maximum (vertex-weighted) clique problem which asks for finding a complete subgraph (i.e., a clique) of maximum total weight on its edges. The problem appears in a wide range of applications, including bioinformatics, material science, computer vision, robotics, and many more. In this work, we propose a new combinatorial branch-and-bound algorithm for the problem which relies on a novel bounding procedure capable of pruning a very large amount of nodes of the branch-and-bound tree. Extensive computational experiments on random and structured graphs, encompassing standard benchmarks used in the literature as well as recently introduced real-world large-scale graphs, show that our new algorithm outperforms the state-of-the-art by several orders of magnitude on many instances
- …
