Search

Recent theoretical research has employed the linear-quadratic model of dose-response in stochastic control formulations for spatiobiologically integrated radiotherapy. The goal is to maximize the expected tumor kill while limiting the biologically effective dose administered to nearby organs at risk under tolerable limits. This is attempted by adapting fluence maps to the uncertain evolution of tumor-cell densities observed in functional images acquired at the beginning of each treatment session. One limitation of this research is that the treatment planner is assumed to know the probability distribution of a crucial dose-response parameter in the linear-quadratic model. This paper proposes a Bayesian stochastic control framework to relax this assumption. An algorithm rooted in certainty-equivalent control is devised to simultaneously learn this probability distribution while adapting fluence maps based on dose-response data collected from functional images over the treatment course. This algorithm's performance is compared via numerical simulations with two other solution procedures that are also rooted in certainty equivalent control. The first one is a clairvoyant method. This assumes that the treatment planner knows the probability distribution, and hence serves as an idealized gold standard. The other one uses a fixed value of the dose-response parameter as available from the literature, and hence provides a natural benchmark without learning. The tumor kill achieved by the learning algorithm is statistically indistinguishable from the clairvoyant approach, whereas it can be about 20% higher than the no-learning benchmark. Both these conclusions bode well for individualized spatiobiologically integrated radiotherapy using functional images, at least in theory. [ABSTRACT FROM AUTHOR]

In this note we consider the validity of substituting a linear goal for a fractional goal in a mathematical program and provide a simple geometric interpretation that contrasts the essential differences between the two programs. [ABSTRACT FROM AUTHOR]

In this paper, we propose a two-stage robust optimization framework to evaluate widely controllable commuter flow strategies that can help mitigate uncertain disruption impacts on rail transit commuter flows. In the operation-as-usual stage, preemptive control strategies including timetable adjustment, commuter path choice diversion, and commuter trip starting time diversion are planned within budget and other requirement constraints. In the disruption stage, optimal contingency routing is derived to minimize disruption impacts. To this end, a linear programming model that simulates the commuter movement logic under train service and platform disruption events is developed, which is then integrated in a mixed-integer max-min optimization model to evaluate the worst-case impacts on commuter flows arising from a set of uncertain disruption scenarios. We show that the two-stage robust optimization framework can be solved by a cutting plane algorithm efficiently using high performance and parallel computing platforms. Finally, we demonstrate the application of the model in mitigating disruption impacts through computational studies based on an actual rail transit network. [ABSTRACT FROM AUTHOR]

Variable fixing by reduced costs is a popular technique for accelerating the solution process of mixed-integer linear programs. For vehicle-routing problems solved by branch-price-and-cut algorithms, it is possible to fix to zero the variables associated with all routes containing at least one arc from a subset of arcs determined according to the dual solution of a linear relaxation. This is equivalent to removing these arcs from the network used to generate the routes. In this paper, we extend this technique to routes containing sequences of two arcs. Such sequences or their arcs cannot be removed directly from the network because routes traversing only one arc of a sequence might still be allowed. For some of the most common vehicle-routing problems, we show how this issue can be overcome by modifying the route-generation labeling algorithm in order to remove indirectly these sequences from the network. The proposed acceleration strategy is tested on benchmark instances of the vehicle-routing problem with time windows (VRPTW) and four variants of the electric VRPTW. The computational results show that it yields a significant speedup, especially for the most difficult instances. [ABSTRACT FROM AUTHOR]

In this paper, we propose a general solution approach for a broad class of vehicle routing problems that all use a single vehicle, composed of a truck and a detachable trailer, to serve a set of customers with known demand and accessibility constraints. A more general problem, called the extended single truck and trailer routing problem (XSTTRP), is used as a common baseline to describe and model this class of problems. In particular, the XSTTRP contains, all together, a variety of vertex types previously considered only separately: truck customers, vehicle customers with and without parking facilities, and parking-only locations. To solve the XSTTRP, we developed a fast and effective hybrid metaheuristic, consisting of an iterative core part, in which routes that define high-quality solutions are stored in a pool. Eventually, a set-partitioning-based postoptimization selects the best combination of routes that forms a feasible solution from the pool. The algorithm is tested on extensively studied problems from the literature, such as the multiple depot vehicle routing problem, the location routing problem, the single truck and trailer routing problem with satellite depots, and the single truck and trailer routing problem. Finally, computational results and a thorough analysis of the main algorithm's components on newly designed XSTTRP instances are provided. The obtained results show that the proposed hybrid metaheuristic is highly competitive with previous approaches designed to solve specific specialized problems, both in terms of computing time and solution quality. [ABSTRACT FROM AUTHOR]

Air traffic management measures comprise tactical operating procedures to minimize delay costs and strategic scheduling interventions to control overcapacity scheduling. Although interdependent, these problems have been treated in isolation. This paper proposes an integrated model of scheduling and operations in airport networks that jointly optimizes scheduling interventions and ground-holding operations across airports networks under operating uncertainty. It is formulated as a two-stage stochastic program with integer recourse. To solve it, we develop an original decomposition algorithm with provable solution quality guarantees. The algorithm relies on new optimality cuts—dual integer cuts—that leverage the reduced costs of the dual linear programming relaxation of the second-stage problem. The algorithm also incorporates neighborhood constraints, which shift from exploration to exploitation at later stages. We also use a scenario generation approach to construct representative scenarios from historical records of operations—using integer programming. Computational experiments show that our algorithm yields near-optimal solutions for the entire U.S. National Airspace System network. Ultimately, the proposed approach enhances airport demand management models through scale integration (by capturing network-wide interdependencies) and scope integration (by capturing interdependencies between scheduling and operations). [ABSTRACT FROM AUTHOR]

Adaptive Matching Under Uncertainties. Two-sided online markets often propose matches based on imperfect knowledge of the characteristics of the two parties to be matched. Such uncertainty may result in inferior matches and may in turn incur negative externalities: a matched resource becomes unavailable to a more suitable party, at least for a while. For example, in labour platforms, if an expert is matched to a task which does not meet his or her expertise, then the other tasks which meet the expert's expertise may suffer. Similarly, in hospitality platforms, an economical accommodation becomes unavailable to a financially constrained customer if it is matched to a flexible customer. Thus, to optimize the long-term efficiency, a platform needs to optimize exploration-exploitation trade-off while accounting for the resource usage. To address this challenge, the paper "Adaptive Matching for Expert Systems with Uncertain Task Types" develops a new model and optimal algorithm for a task-expert matching system, where a task is matched to an expert using not only the prior information about the task but also the feedback obtained from the past matches. A matching in a two-sided market often incurs an externality: a matched resource may become unavailable to the other side of the market, at least for a while. This is especially an issue in online platforms involving human experts, as the expert resources are often scarce. The efficient utilization of experts in these platforms is made challenging by the fact that the information available about the parties involved is usually limited. To address this challenge, we develop a model of a task-expert matching system where a task is matched to an expert using not only the prior information about the task but also the feedback obtained from the past matches. In our model, the tasks arrive online while the experts are fixed and constrained by a finite service capacity. For this model, we characterize the maximum task resolution throughput a platform can achieve. We show that the natural greedy approach where each expert is assigned a task most suitable to his or her skill is suboptimal, as it does not internalize the aforementioned externality. We develop a throughput-optimal backpressure algorithm which does so by accounting for the "congestion" among different task types. Finally, we validate our model and confirm our theoretical findings with data-driven simulations via logs of Math.StackExchange.com, a Stack Overflow forum dedicated to mathematics. [ABSTRACT FROM AUTHOR]

A New Algorithm for Static Bin Packing Static bin packing is the problem of partitioning a set of items (with scalar sizes) into identical bins of a given capacity, under the constraint that the total size of no partition exceeds the bin capacity. In the online variant, the list of items is revealed one at a time—an item must be assigned irrevocably to a partition at the time it is revealed. In "Interior-Point Based Online Stochastic Bin Packing," V. Gupta and A. Radovanović look at the online variant under the assumption that the item sizes are independent samples from a common unknown distribution. The authors show that a greedy heuristic that assigns items so as to minimize a carefully chosen penalized Lagrangian of the offline math program is asymptotically optimal. Since the proposed heuristic is greedy in nature, it extends readily to nonstationary item size sequences for which the authors prove a novel family of performance bounds. Bin packing is an algorithmic problem that arises in diverse applications such as remnant inventory systems, shipping logistics, and appointment scheduling. In its simplest variant, a sequence of T items (e.g., orders for raw material, packages for delivery) is revealed one at a time, and each item must be packed on arrival in an available bin (e.g., remnant pieces of raw material in inventory, shipping containers). The sizes of items are independent and identically distributed (i.i.d.) samples from an unknown distribution, but the sizes are known when the items arrive. The goal is to minimize the number of nonempty bins (equivalently waste, defined to be the total unused space in nonempty bins). This problem has been extensively studied in the operations research and theoretical computer science communities, yet all existing heuristics either rely on learning the distribution or exhibit o(T) additive suboptimality compared with the optimal offline algorithm only for certain classes of distributions (those with sublinear optimal expected waste). In this paper, we propose a family of algorithms that are the first truly distribution-oblivious algorithms for stochastic bin packing, and achieve O (T) additive suboptimality for all item size distributions. Our algorithms are inspired by approximate interior-point algorithms for convex optimization. In addition to regret guarantees for discrete i.i.d. sequences, we extend our results to continuous item size distribution with bounded density, and prove a family of novel regret bounds for non-i.i.d. input sequences. To the best of our knowledge, these are the first such results for non-i.i.d. and non-random-permutation input sequences for online stochastic packing. [ABSTRACT FROM AUTHOR]

In multiserver distributed queueing systems, the access of stochastically arriving jobs to resources is often regulated by a dispatcher, also known as a load balancer. A fundamental problem consists in designing a load-balancing algorithm that minimizes the delays experienced by jobs. During the last two decades, the power-of-d-choice algorithm, based on the idea of dispatching each job to the least loaded server out of d servers randomly sampled at the arrival of the job itself, has emerged as a breakthrough in the foundations of this area because of its versatility and appealing asymptotic properties. In this paper, we consider the power-of-d-choice algorithm with the addition of a local memory that keeps track of the latest observations collected over time on the sampled servers. Then, each job is sent to a server with the lowest observation. We show that this algorithm is asymptotically optimal in the sense that the load balancer can always assign each job to an idle server in the large-system limit. This holds true if and only if the system load λ is less than 1 − 1 d . If this condition is not satisfied, we show that queue lengths are bounded by ⌈ − log (1 − λ) log (λd + 1) ⌉ . This is in contrast with the classic version of the power-of-d-choice algorithm, in which, at the fluid scale, a strictly positive proportion of servers containing i jobs exists for all i ≥ 0 in equilibrium. Our results quantify and highlight the importance of using memory as a means to enhance performance in randomized load balancing. [ABSTRACT FROM AUTHOR]

For general multiobjective optimization problems, the usual goal is finding the set of solutions not dominated by any other solutions, that is, a set of solutions as good as any other solution in all objectives and strictly better in at least one objective. In this paper, we propose a novel performance metric called the domination measure to measure the quality of a solution, which can be intuitively interpreted as the probability that an arbitrary solution in the solution space dominates that solution with respect to a predefined probability measure. We then reformulate the original problem as a stochastic and single-objective optimization problem. We further propose a model-based approach to solve it, which leads to an ideal version algorithm and an implementable version algorithm. We show that the ideal version algorithm converges to a set representation of the global optima of the reformulated problem; we demonstrate the numerical performance of the implementable version algorithm by comparing it with numerous existing multiobjective optimization methods on popular benchmark test functions. The numerical results show that the proposed approach is effective in generating a finite and uniformly spread approximation of the Pareto optimal set of the original multiobjective problem and is competitive with the tested existing methods. The concept of domination measure opens the door for potentially many new algorithms, and our proposed algorithm is an instance that benefits from domination measure. [ABSTRACT FROM AUTHOR]

This paper explores the connections between the classical maximum clique problem and its edge-weighted generalization, the maximum edge weight clique (MEWC) problem. As a result, a new analytic upper bound on the clique number of a graph is obtained and an exact algorithm for solving the MEWC problem is developed. The bound on the clique number is derived using a Lagrangian relaxation of an integer (linear) programming formulation of the MEWC problem. Furthermore, coloring-based bounds on the clique number are used in a novel upper-bounding scheme for the MEWC problem. This scheme is employed within a combinatorial branch-and-bound framework, yielding an exact algorithm for the MEWC problem. Results of computational experiments demonstrate a superior performance of the proposed algorithm compared with existing approaches. [ABSTRACT FROM AUTHOR]

The bilinear assignment problem (BAP) is a generalization of the well-known quadratic assignment problem. In this paper, we study the problem from the computational analysis point of view. Several classes of neighborhood structures are introduced for the problem along with some theoretical analysis. These neighborhoods are then explored within a local search and variable neighborhood search frameworks with multistart to generate robust heuristic algorithms. In addition, we present several very fast construction heuristics. Our systematic experimental analysis disclosed some interesting properties of the BAP, different from those of comparable models. We have also introduced benchmark test instances that can be used for future experiments on exact and heuristic algorithms for the problem. [ABSTRACT FROM AUTHOR]

This paper considers the vehicle routing problem with stochastic demands under optimal restocking. We develop an exact algorithm that is effective for solving instances with many vehicles and few customers per route. In our experiments, we show that in these instances, solving the stochastic problem is most relevant (i.e., the potential gains over the deterministic equivalent solution are highest). The proposed branch-price-and-cut algorithm relies on an efficient labeling procedure, exact and heuristic dominance rules, and completion bounds to price profitable columns. Instances with up to 76 nodes could be solved in less than five hours, and instances with up to 148 nodes could be solved in long runs of the algorithm. The experiments also allowed new findings on the problem. The solution to the stochastic problem is up to 10% less costly than the deterministic equivalent solution. Opening new routes reduces restocking costs and in many cases results in solutions with less transportation costs. When the number of routes is not fixed, the optimal solutions under detour-to-depot and optimal restocking are nearly equivalent. However, when the number of routes is limited and the expected demand along a route is allowed to exceed the vehicle capacity, optimal restocking may be significantly more cost-effective than the detour-to-depot policy. [ABSTRACT FROM AUTHOR]

This paper, for the first time, studies vehicle routing problems with synchronized visits (VRPS) and stochastic travel and service times. In addition to considering a home healthcare scheduling problem, we introduce an operating room scheduling problem with stochastic durations as a novel application of VRPS. We formulate VRPS with stochastic times as a two-stage stochastic integer programming model that, unlike the deterministic models in the VRPS literature, does not have any big-M constraints. This advantage comes at the cost of a large number of second-stage integer variables. We prove that the integrality constraints on second-stage variables can be relaxed, and therefore, we can apply the L-shaped algorithm and its branch-and-cut implementation to solve the problem. We enhance the model by developing valid inequalities and a lower bounding functional. We analyze the subproblems of the L-shaped algorithm and devise a specialized algorithm for them that is significantly faster than standard linear programming algorithms. Computational results show that the branch-and-cut algorithm optimally solves stochastic home healthcare scheduling instances with 15 patients and 10%–30% of synchronized visits. It also finds solutions with an average optimality gap of 3.57% for instances with 20 patients. Furthermore, the branch-and-cut algorithm optimally solves stochastic operating room scheduling problems with 20 surgeries. [ABSTRACT FROM AUTHOR]

Robust optimization has emerged in the operations research literature as a tractable and practical way to model uncertainty in optimization problems. Early approaches focused on relative worst-case objective functions, where the value of a solution is measured versus the best-possible solution over an uncertainty set of scenarios. However, over the past ten years the focus has primarily been on absolute worst-case objective functions, which have generally been considered to be more tractable. In this paper, we demonstrate that for many problems of interest, including some adaptive robust optimization problems, that considering relative objective functions does not significantly increase the computational cost over absolute objective functions. We use combinations of absolute and relative worst-case objective functions to find Pareto-efficient solutions that combine aspects of both, which suggests an approach to distinguish between otherwise very similar robust solutions. We provide reformulation and cutting plane approaches for these problems and demonstrate their efficacy with experiments on minimum-cost flow, inventory control, and facility location problems. These case studies show that solutions corresponding to relative objective functions may be a better match for a decision maker's risk preferences than absolute. [ABSTRACT FROM AUTHOR]

We retrospectively explore the effectiveness of various probabilistic opinion pools against a set of insider threat detection modeling data from a recently completed, multiyear, sponsored research effort. We explored four opinion pools: the linear opinion pool (likely the most popular), the beta-transformed linear opinion pool, the geometric opinion pool, and a multiplicative method based on odds called Bordley's formula. The data for our study came from our recent work in the inference of insider threats for our research sponsor. In this work, we created a multimodeling inference enterprise modeling (MIEM) process to either predict threats within a population or, given the threats, predict how well the enterprise system can detect those threats. As part of larger research challenges designed by the research sponsor, we applied the MIEM process quarterly to respond to a sequence of varying challenge problems (CPs). Via MIEM, we developed multiple, independent computation forecast models. These models generated certainty intervals to answer CP questions. These intervals were fused into a single interval for each question via an expert panel prior to submission. The sponsors scored the responses against ground truth. In this paper, we (a) ask which pooling functions work best on these data and consider why, and (b) compare this performance to the actual submissions to determine if one of the pooling functions performed better than our judgment-based fusion. [ABSTRACT FROM AUTHOR]

This paper deals with a class of biobjective mixed binary linear programs having a multiple-choice constraint, which are found in applications such as Pareto set–reduction problems, single-supplier selection, and investment decisions, among others. Two objective space–search algorithms are presented. The first algorithm, termed line search and linear programming filtering, is a two-phase procedure. Phase 1 searches for supported Pareto outcomes using the parametric weighted sum method, and Phase 2 searches for unsupported Pareto outcomes by solving a sequence of auxiliary mixed binary linear programs. An effective linear programming filtering procedure excludes any previous outcomes found to be dominated. The second algorithm, termed linear programming decomposition and filtering, decomposes the mixed binary problem by iteratively fixing binary variables and uses the linear programming filtering procedure to prune out any dominated outcomes. Computational experiments show the effectiveness of the linear programming filtering and suggest that both algorithms run faster than existing general-purpose objective space–search procedures. [ABSTRACT FROM AUTHOR]

Applications of the pickup and delivery problem with time windows and last-in-first-out (LIFO) loading (PDPTWL) constraints can be found in the transportation of animals, heavyweight goods, and hazardous materials, where unloading vehicles requires more time and special handling. Examples include carrying livestock, cars, and chemical containers. Research on exact methods to solve the pickup and delivery problem with time windows (PDPTW) and its variants has mainly focused on branch-and-price-and-cut algorithms. In this paper, we propose a novel exact approach based on fragments—a series of pickup and delivery requests starting and ending with an empty vehicle. We use fragments to formulate a relaxed network flow model with side constraints. Lazy constraints are used to cut off any illegal solution that may occur while solving the integer program. Extensive computational experiments show that the proposed approach is superior to the current state-of-the-art method. [ABSTRACT FROM AUTHOR]

Unmanned aircraft systems (UASs) are a promising new mode of transportation for cargo delivery. Although control, navigation, and communication technologies are becoming available on individual flight units, system-level motion management for dense UAS traffic remains an open question. This paper presents a motion-planning model based on nonlinear optimization techniques to centrally coordinate paths for all vehicles traversing a shared two-dimensional (2D) space. An exact bound is derived to characterize the discrete-time separation constraints, and a set of new metrics is proposed to measure 2D traffic flow efficiency. The grand goal is to make all vehicles that come under dispatch reach their respective destinations quickly and efficiently while maintaining a safe intervehicle separation at all times. This infinite-horizon operational problem is formulated as a nonlinear nonconvex optimization model that must be solved in a progressive, receding-horizon fashion. To ensure feasibility and overcome path deadlocks attributed to local optima, a series of heuristic measures are developed. By pivoting on artfully coined intermediate feasibility, the algorithm is able to circumvent imminent deadlocks in a predictive manner and progressively construct the solution with guaranteed feasibility. Simulation experiments are performed at various traffic density levels to generate useful insights for airspace regulators and traffic managers. [ABSTRACT FROM AUTHOR]

Vehicle scheduling is a central problem in transportation. As railways and the airspace become increasingly congested, it is crucial to develop mathematical tools to better schedule trains and airplanes off-line (timetabling) and online (dispatching). These traffic-management problems can be modeled as job-shop scheduling problems, which, in turn, can be solved using mixed-integer linear programming (MILP). The two most successful and widespread formulations in the past decades are the big-M and the time-indexed methods, each with its strengths and weaknesses. However, there have been few advancements in either approach in recent years. In this paper, we introduce an alternative formulation, obtained by strengthening and lifting the Benders' reformulation of a natural initial formulation. This new approach improves performances on our real-life test bed and opens up interesting research directions. A central problem in traffic management is that of scheduling the movements of vehicles so as to minimize the cost of the schedule. It arises in important applications such as train timetabling, rescheduling, delay and disruption management, airplane surface routing, runway scheduling, air-traffic control, and more. This problem can be modeled as a job-shop scheduling problem. We introduce a new mixed-integer linear program (MILP) formulation for job-shop scheduling, which is an alternative to classical approaches, namely, big-M and time-indexed formulations. It does not make use of artificially large coefficients, and its constraints correspond to basic graph structures, such as paths, cycles, and trees. The new formulation can be obtained by strengthening and lifting the constraints of a classical Benders' reformulation. Tests on a large set of real-life instances from train rescheduling show that the new approach performs on average better than our previous approaches based on big-M formulations and particularly better on a class of instances with nonconvex costs very common in the practice. [ABSTRACT FROM AUTHOR]

Most real-world optimization problems are multi-objective by nature, with conflicting and incomparable objectives. Solving a multi-objective optimization problem requires a method that can generate all rational compromises between the objectives. This paper proposes two distinct bound set-based branch-and-cut algorithms for general bi-objective combinatorial optimization problems based on implicit and explicit lower-bound sets. The algorithm based on explicit lower-bound sets computes, for each branching node, a lower-bound set and compares it with an upper-bound set. The other fathoms branching nodes by generating a single point on the lower-bound set for each local nadir point. We outline several approaches for fathoming branching nodes, and we propose an updating scheme for the lower-bound sets that prevents us from solving the bi-objective linear programming relaxation of each branching node. To strengthen the lower-bound sets, we propose a bi-objective cutting-plane algorithm that adjusts the weights of the objective functions such that different parts of the feasible set are strengthened by cutting planes. In addition, we suggest an extension of the branching strategy "Pareto branching." We prove the effectiveness of the algorithms through extensive computational results. [ABSTRACT FROM AUTHOR]

Motivated by a class of applied problems arising from physical layer based security in a digital communication system, in particular, by a secrecy sum-rate maximization problem, this paper studies a nonsmooth, difference-of-convex (dc) minimization problem. The contributions of this paper are (i) clarify several kinds of stationary solutions and their relations; (ii) develop and establish the convergence of a novel algorithm for computing a d-stationary solution of a problem with a convex feasible set that is arguably the sharpest kind among the various stationary solutions; (iii) extend the algorithm in several directions including a randomized choice of the subproblems that could help the practical convergence of the algorithm, a distributed penalty approach for problems whose objective functions are sums of dc functions, and problems with a specially structured (nonconvex) dc constraint. For the latter class of problems, a pointwise Slater constraint qualification is introduced that facilitates the verification and computation of a B(ouligand)-stationary point. [ABSTRACT FROM AUTHOR]

The question of aggregating pairwise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers (e.g., MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining a ranking, finding 'scores' for each object (e.g., player's rating) is of interest for understanding the intensity of the preferences. In this paper, we propose Rank Centrality, an iterative rank aggregation algorithm for discovering scores for objects (or items) from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with an edge present between a pair of objects if they are compared; the score, which we call Rank Centrality, of an object turns out to be its stationary probability under this random walk. To study the efficacy of the algorithm, we consider the popular Bradley-Terry-Luce (BTL) model (equivalent to the Multinomial Logit (MNL) for pairwise comparisons) in which each object has an associated score that determines the probabilistic outcomes of pairwise comparisons between objects. In terms of the pairwise marginal probabilities, which is the main subject of this paper, the MNL model and the BTL model are identical. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. In particular, the number of samples required to learn the score well with high probability depends on the structure of the comparison graph. When the Laplacian of the comparison graph has a strictly positive spectral gap, e.g., each item is compared to a subset of randomly chosen items, this leads to dependence on the number of samples that is nearly order optimal. Experimental evaluations on synthetic data sets generated according to the BTL model show that our algorithm performs as well as the maximum likelihood estimator for that model and outperforms other popular ranking algorithms. [ABSTRACT FROM AUTHOR]

China has recently developed a large-scale high-speed railway (HSR) network that not only revolutionizes the perception of long-haul transport but also fundamentally improves the emergency response capability of the country. This gives rise to a problem of scheduling a set of emergency trains within the predefined HSR timetable. According to different degrees of disturbance of the timetable, this paper identifies three kinds of solutions, named, ideal, quasi-ideal, and feasible solutions, to the problem. We define a "headroom" function for computing the maximum number of emergency trains that can be inserted between two adjacent regular trains without any disturbance, from which a linear algorithm for finding ideal solutions is derived. By identifying the scope of changes to each regular train, quasi-ideal and feasible solutions can be found based on the ideal solutions on a set of alternative timetables. Numerical experiments demonstrate that our method is very efficient for supporting near-immediate emergency responses. We have used the solution method to evaluate the emergency capacity of most HSR lines in China. In particular, we successfully applied the method to schedule emergency trains in the rescue operation of the 2015 Tianjin chemical explosion. The online appendix is available at https://doi.org/10.1287/trsc.2017.0794. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of routing in-house transport vehicles that feed parts to workstations in assembly plants or workshops just in time. The capacitated vehicles, typically so-called tow trains, perform their assigned route cyclically without break and provide each station with the exact quantity of parts required until the next arrival of the vehicle. Hence, the demand of each station depends on the duration of the route serving the station: The longer the route duration, the less frequently the station is visited and the higher its demand. The goal is to minimize first the number of vehicles and second the total route duration, while respecting given minimum service frequencies at the stations. We provide a mathematical formulation of this novel problem and address it by means of a large neighborhood search. The algorithm is able to solve realistic instances in acceptable time and vastly outperforms a default solver. We discuss two variants of the problem, one in which split deliveries to stations are allowed and another assuming that all stations lie on a straight line. Finally, we investigate the extent to which assuming constant demand rates may lead to problems during the day-to-day operations of the part-feeding system, where demands are not necessarily constant. [ABSTRACT FROM AUTHOR]

The Inventory Routing Problem (IRP) involves the distribution of one or more products from a supplier to a set of clients over a discrete planning horizon. Each client has a known demand to be met in each period and can only hold a limited amount of stock. The product is shipped through a distribution network by one or more vehicles of limited capacity. The objective is to find replenishment decisions minimizing the sum of the storage and distribution costs. In this paper, we present IRP reformulations under the Maximum Level replenishment policy, derived from a single-period substructure. We define a generic family of valid inequalities, and then introduce two specific subclasses for which the separation problem of generating violated inequalities can be effectively solved. A basic Branch-and-Cut algorithm has been implemented to demonstrate the strength of the single-period reformulations. We present computational results for the benchmark instances with 50 clients and 3 periods and 30 clients and 6 periods. [ABSTRACT FROM AUTHOR]

We study a class of problems with both binary selection decisions and associated continuous choices that result in stochastic rewards and costs. The rewards are received based on the decision maker's selection, and the costs depend both on the decisions and realizations of the stochastic variables. We consider a family of risk-based objective functions that contains the traditional risk-neutral expected-value objective as a special case. A combination of rounding and sample average approximation is used to produce solutions that are guaranteed to be close to the optimal solution with high probability. We also provide an empirical comparison of the performance of the algorithms on a set of randomly generated instances of a supply chain example problem. The computational results illustrate the theoretical claims in the paper that, for this problem, high-quality solutions can be found with small computational effort. [ABSTRACT FROM AUTHOR]

Although evidence-based algorithms consistently outperform human forecasters, people often fail to use them after learning that they are imperfect, a phenomenon known as algorithm aversion. In this paper, we present three studies investigating how to reduce algorithm aversion. In incentivized forecasting tasks, participants chose between using their own forecasts or those of an algorithm that was built by experts. Participants were considerably more likely to choose to use an imperfect algorithm when they could modify its forecasts, and they performed better as a result. Notably, the preference for modifiable algorithms held even when participants were severely restricted in the modifications they could make (Studies 1-3). In fact, our results suggest that participants' preference for modifiable algorithms was indicative of a desire for some control over the forecasting outcome, and not for a desire for greater control over the forecasting outcome, as participants' preference for modifiable algorithms was relatively insensitive to the magnitude of the modifications they were able to make (Study 2). Additionally, we found that giving participants the freedom to modify an imperfect algorithm made them feel more satisfied with the forecasting process, more likely to believe that the algorithm was superior, and more likely to choose to use an algorithm to make subsequent forecasts (Study 3). This research suggests that one can reduce algorithm aversion by giving people some control--even a slight amount--over an imperfect algorithm's forecast. [ABSTRACT FROM AUTHOR]

Recent research on location-routing problems has been focusing on locating facilities as the starting and end point of routes. In this paper, we investigate a new type of location-routing problem. In the location-routing problem with intra-route facilities, the location of depots is known, whereas the location of facilities for intermediate stops has to be determined to keep vehicles operational. We present an adaptive large neighborhood search which is enhanced by local search and dynamic programming components, and derive new penalty functions for time-efficient neighborhood evaluation. We show that this algorithm is suitable for solving various problems with intra-route facilities by deriving new best known solutions for the recently published electric location-routing problem with time windows and partial recharging, as well as for the battery swap station electric vehicle location-routing problem. Additionally, we create new real-world benchmark instances and show results as well. Furthermore, we assess the competitiveness of our algorithm on the electric vehicle routing problem with time windows for full and partial recharging, and derive new best known solutions for both problem variants. [ABSTRACT FROM AUTHOR]

The planning of outbound baggage handling at international airports is challenging. Outgoing flights have to be assigned and scheduled to handling facilities at which the outgoing baggage is loaded into containers. To avoid disruptions of the system the objective is to minimize workload peaks over the entire system. The resource demand of the jobs that have to be scheduled depends on the arrival process of the baggage. In this paper we present a time-indexed mathematical programming formulation for planning the outbound baggage. We propose an innovative decomposition procedure in combination with a column generation scheme to solve practical problem instances. The decomposition significantly reduces the symmetry effect in the time-indexed formulation and also speeds up the computational time of the corresponding Dantzig-Wolfe formulation. To further improve our column generation algorithm we propose state-of-the-art acceleration techniques for the primal problem and the pricing problem. Computational results based on real data from a major European airport show that the proposed procedure reduces the maximal workloads by more than 60% compared to the current assignment procedure used. The online appendix is available at . [ABSTRACT FROM AUTHOR]

In this paper, we use the penalty approach in order to study constrained minimization problems in infinite dimensional spaces. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper, we establish the exact penalty property for a large class of inequality-constrained minimization problems. [ABSTRACT FROM AUTHOR]

In designing ideal multiple recursive random number (RN) generators (MRGs), the best set of multipliers, in terms of the lattice structure of the RNs produced, is sought. As the order of the MRG increases, the number of possible sets of multipliers to be examined grows exponentially This paper proposes a genetic algorithm for designing good MRGs. The set of multipliers associated with the MRG is encoded as a binary string. Via the operations of reproduction, crossover, and mutation, new sets of multipliers are generated. The spectral values of the MRGs are calculated to guide the search process. As an illustration, the proposed algorithm is employed to find good sets of multipliers for MRGs of orders three and four. The results are better than those derived from other studies. To conclude, this paper not only finds better MRGs of orders three and four, but also develops an algorithm for designing MRGs of higher orders. [ABSTRACT FROM AUTHOR]

Recommendation stability measures the extent to which a recommendation algorithm provides predictions that are consistent with each other. Several approaches have been proposed in prior work to defining, measuring, and improving the stability of recommendation algorithms. Previous studies have focused primarily on understanding and evaluating recommendation stability in prediction-oriented settings, i.e., recommendation settings where it is crucial to provide the precise prediction of a user's preference rating for an item. However, the research literature has been largely silent on the topic of recommendation stability in other important types of settings, such as classification-oriented (i.e., where it is important to accurately classify the item as relevant versus irrelevant, without having to quantify the user's preference precisely), ranking-oriented (i.e., where it is important to provide accurate relative ranking of items to users), or top-K oriented (i.e., where it is important to suggest K items that are most appealing to the user). Therefore, this paper builds on prior work by generalizing the notion of stability to a broader set of recommendation settings and developing corresponding stability metrics. The paper also provides a comprehensive empirical analysis of classification, ranking, and top-K stability performance of popular recommender algorithms on real-world rating data sets under a variety of settings. [ABSTRACT FROM AUTHOR]

Floating-point computations are quickly finding their way in the design of safety- and mission-critical systems, despite the fact that designing floating-point algorithms is significantly more difficult than designing integer algorithms. For this reason, verification and validation of floating-point computations are hot research topics. An important verification technique, especially in some industrial sectors, is testing. However, generating test data for floating-point intensive programs proved to be a challenging problem. Existing approaches usually resort to random or search-based test data generation, but without symbolic reasoning it is almost impossible to generate test inputs that execute complex paths controlled by floating-point computations. Moreover, because constraint solvers over the reals or the rationals do not natively support the handling of rounding errors, the need arises for efficient constraint solvers over floating-point domains. In this paper, we present and fully justify improved algorithms for the propagation of arithmetic IEEE 754 binary floating-point constraints. The key point of these algorithms is a generalization of an idea by B. Marre and C. Michel that exploits a property of the representation of floating-point numbers. [ABSTRACT FROM AUTHOR]

In this paper we introduce the time window assignment vehicle routing problem (TWAVRP). In this problem, I time windows have to be assigned before demand is known. Next, a realization of demand is revealed, and a vehicle routing schedule is made that satisfies the assigned time windows. The objective is to minimize the expected traveling costs. We propose a branch-price-and-cut algorithm to solve the TWAVRP to optimality. We provide results of computational experiments performed using this algorithm. Finally, we offer insight on the value of an exact approach for the TWAVRP by comparing the optimal solution to the solution found by assigning time windows based on solving a vehicle routing problem with time windows with average demand. [ABSTRACT FROM AUTHOR]

This paper considers infinite-horizon finite state-and-action Markov population decision chains (MPDCs) in which the goal is to find a stationary stopping policy with maximum stopping value, that is, with maximum value over all deterministic Markov stopping policies. A policy is stopping if the resulting expected population size in a period diminishes to zero as the period converges to infinity. The paper shows that the following are equivalent: (a) there is a stationary maximum-stopping value policy; (b) the maximum stopping value is finite; (c) there is a stopping policy and an excessive point of the optimal return operator; and (d) the maximum stopping value is the least excessive (resp., fixed) point of the optimal return operator. The paper shows how to use linear programming, policy improvement and successive approximations to solve the problem. The problem arises in stopping a Markov chain, as in optimally eradicating a pest or disease. The problem is one of two key subproblems used repeatedly to find Blackwell and Cesàro-overtaking optimal policies in finite Markov decision chains (MDCs), both of which, with their generalizations, have a vast number of applications. The problem for MDCs and/or MPDCs has been studied under various conditions, and over the years, by many investigators including Bellman, Bertsekas, Blackwell, Dantzig, Denardo, d‘Epenoux, Derman, Dynkin, Eaton, Erickson, Ford, Hordijk, Howard, Kallenberg, Manne, O‘Sullivan, Rothblum, Shoemaker, Strauch, Tsitsiklis, Veinott, Wagner, and Zadeh. [ABSTRACT FROM AUTHOR]

This paper reviews studies from the past 30 years that use operations research methods to tackle containership routing and scheduling problems at the strategic, tactical, and operational planning levels. These problems are first classified and summarized, with a focus on model formulations, assumptions, and algorithm design. The paper then gives an overview of studies on containership fleet size and mix, alliance strategy, and network design (at the strategic level); frequency determination, fleet deployment, speed optimization, and schedule design (at the tactical level); and container booking and routing and ship rescheduling (at the operational level). The paper further elaborates on the needs of the liner container shipping industry and notes the gap between existing academic studies and industrial practices. Research on containership routing and scheduling lags behind practice, especially in the face of the fast growth of the container shipping industry and the advancement of operations research and computer technology. The purpose of this paper is to stimulate more practically relevant research in this emerging area. [ABSTRACT FROM AUTHOR]

We consider an online retailer facing heterogeneous customers with initially unknown product preferences. Customers are characterized by a diverse set of demographic and transactional attributes. The retailer can personalize the customers' assortment offerings based on available profile information to maximize cumulative revenue. To that end, the retailer must estimate customer preferences by observing transaction data. This, however, may require a considerable amount of data and time given the broad range of customer profiles and large number of products available. At the same time, the retailer can aggregate (pool) purchasing information among customers with similar product preferences to expedite the learning process. We propose a dynamic clustering policy that estimates customer preferences by adaptively adjusting customer segments (clusters of customers with similar preferences) as more transaction information becomes available. We test the proposed approach with a case study based on a data set from a large Chilean retailer. The case study suggests that the benefits of the dynamic clustering policy under the MNL model can be substantial and result (on average) in more than 37% additional transactions compared to a data-intensive policy that treats customers independently and in more than 27% additional transactions compared to a linear-utility policy that assumes that product mean utilities are linear functions of available customer attributes. We support the insights derived from the numerical experiments by analytically characterizing settings in which pooling transaction information is beneficial for the retailer, in a simplified version of the problem. We also show that there are diminishing marginal returns to pooling information from an increasing number of customers. The online appendix is available at https://doi.org/10.1287/mnsc.2018.3031. This paper was accepted by Gad Allon, operations management. [ABSTRACT FROM AUTHOR]

In this paper, we describe data collected from five U.S. properties of a major hotel chain that can be used to benchmark the performance of choice-based revenue management (RM) algorithms. The process used to collect this data illustrates subtle complexities involved in extracting product availability information from current RM systems and sheds new light on practical issues that need to be addressed to successfully implement choice-based RM systems. The data described in this paper is publicly available at the journal's website at http://msom.pubs.informs.org. [ABSTRACT FROM AUTHOR]

This paper proposes a general framework for a large class of multiperiod principal-agent problems. In this framework, a principal has a primary stake in the performance of a system but delegates its control to an agent. The underlying system is a Markov decision process, where the state of the system can only be observed by the agent but the agent's action is observed by both parties. This paper develops a dynamic programming algorithm to derive optimal long-term contracts for the principal. The principal indirectly controls the underlying system by offering the agent a menu of continuation utility vectors along public information paths; the agent's best response, expressed in his choice of continuation utilities, induces truthful state revelation and results in actions that maximize the principal's expected payoff. This problem is meaningful to the operations research community because it can be framed as the problem of optimally designing the reward structure of a Markov decision process with hidden states and has many applications of interest as discussed in this paper [ABSTRACT FROM AUTHOR]

The importance of historical travel demand has been well recognized by transportation researchers and practitioners. This paper presents a new nonlinear demand estimator that can be applied in both ground and air transportation. The estimator is formulated such that the distribution of the estimated demand follows a nested logit model. To solve the demand estimator, we develop an exact solution algorithm, which maximizes its dual problem sequentially along unit directions and keeps some of the first-order optimality conditions satisfied for the estimator. We investigate the convergence of the algorithm. We prove that all of the accumulation points produced by the solution algorithm satisfy some optimality conditions. A large example (a real U.S. network), which contains 66,767 origin-destination pairs, is presented. [ABSTRACT FROM AUTHOR]

The ℓ0-minimization problem that seeks the sparsest point of a polyhedral set is a long-standing, challenging problem in the fields of signal and image processing, numerical linear algebra, and mathematical optimization. The weighted ℓ1-method is one of the most plausible methods for solving this problem. In this paper we develop a new weighted ℓ1-method through the strict complementarity theory of linear programs. More specifically, we show that locating the sparsest point of a polyhedral set can be achieved by seeking the densest possible slack variable of the dual problem of weighted ℓ1-minimization. As a result, ℓ0-minimization can be transformed, in theory, to ℓ0-maximization in dual space through some weight. This theoretical result provides a basis and an incentive to develop a new weighted ℓ1-algorithm, which is remarkably distinct from existing sparsity-seeking methods. The weight used in our algorithm is computed via a certain convex optimization instead of being determined locally at an iterate. The guaranteed performance of this algorithm is shown under some conditions, and the numerical performance of the algorithm has been demonstrated by empirical simulations. [ABSTRACT FROM AUTHOR]

Nonstationary queueing networks are often difficult to approximate. Recent novel methods for approximating the moments of nonstationary queues use the functional version of the Kolmogorov forward equations in conjunction with orthogonal polynomial expansions. However, these methods require closed form expressions for the expectations that appear in the functional Kolmogorov forward equations. When closed form expressions cannot be easily derived, these methods cannot be used. In this paper, we present a new sampling algorithm to overcome this difficulty; our sampling algorithm accurately estimates the expectations using simulation. We apply our algorithm to priority queues, which are useful for modeling hospital triage systems. We show that our sampling algorithm accurately estimates the mean and variance of the priority queue without spending significantly more computational time than integrating ordinary differential equations. Last, we compare our sampling algorithm to the closed form analytical approximations for the Erlang-A queueing model and find that our method is comparable in time and accuracy. [ABSTRACT FROM AUTHOR]

This paper focuses on revealed preference tests of the collective model of household consumption. We start by showing that the decision problems corresponding to testing collective rationality are NP-complete. This makes the application of these tests problematic for (increasingly available) large(r)-scale data sets. We then present two approaches to overcome this negative result. First, we introduce exact algorithms based on mixed-integer programming (MIP) formulations of the collective rationality tests, which can be usefully applied to medium-sized data sets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model in the case of large data sets. We illustrate our methods by a number of computational experiments based on Dutch labor supply data. [ABSTRACT FROM AUTHOR]

Effective route planning for battery electric commercial vehicle (ECV) fleets has to take into account their limited autonomy and the possibility of visiting recharging stations during the course of a route. In this paper, we consider four variants of the electric vehicle-routing problem with time windows: (i) at most a single recharge per route is allowed, and batteries are fully recharged on visit of a recharging station; (ii) multiple recharges per route, full recharges only; (iii) at most a single recharge per route, and partial battery recharges are possible; and (iv) multiple, partial recharges. For each variant, we present exact branch-price-and-cut algorithms that rely on customized monodirectional and bidirectional labeling algorithms for generating feasible vehicle routes. In computational studies, we find that all four variants are solvable for instances with up to 100 customers and 21 recharging stations. This success can be attributed to the tailored resource extension functions (REFs) that enable efficient labeling with constant time feasibility checking and strong dominance rules, even if these REFs are intricate and rather elaborate to derive. The studies also highlight the superiority of the bidirectional labeling algorithms compared to the monodirectional ones. Finally, we find that allowing multiple as well as partial recharges both help to reduce routing costs and the number of employed vehicles in comparison to the variants with single and with full recharges. [ABSTRACT FROM AUTHOR]

This paper deals with nonhomogeneous Markov decision processes with Borel state space and nonuniformly bounded rewards under the average criterion. First, under the minorant-type assumption we prove the existence of an appropriate solution to the optimality equations. Second, from the optimality equations we also establish the existence of ε(≥ 0)-optimal Markov policies under the additional conditions. Third, some sufficient conditions for the validity of the assumptions in this paper and several examples such as inventory/production systems are provided. Finally, as an application of the optimality equations, a rolling horizon algorithm is given. [ABSTRACT FROM AUTHOR]

This paper deals with undiscounted infinite stage two-person zero-sum stochastic games with finite state and action spaces. It was recently shown that such games possess a value. But in general there are no optimal strategies. We prove that for each player there exists a nonempty set of easy initial states, i.e. starting states for which the player possesses an optimal stationary strategy. This result is proved with the aid of facts derived by Bewley and Kohlberg for the limit discount equation for stochastic games. [ABSTRACT FROM AUTHOR]

The problem of determining continuous flows of minimum cost in a network with convex cost functions is considered. The approach used is that of finding, for any given feasible flow, circuit flows of negative incremental costs. In the main theoretical result of this paper, it is proved that if at each stage, given a feasible nonoptimal flow X, the circuit flow with most negative incremental cost is added to X, linear convergence to the optimal solution will be obtained. In addition, this most negative incremental cost determines an upper bound on the difference in cost between the given feasible solution and the optimal. Based on these concepts, an algorithm, which preserves linear convergence, is presented to determine minimum cost flows in networks with convex costs in the arcs. Results of computer runs made for this algorithm are given. The special case of networks with linear costs is also considered. [ABSTRACT FROM AUTHOR]

The main purpose of this paper is to delineate an algorithm for fractional programming with nonlinear as well as linear terms in the numerator and denominator. The algorithm presented is based on a theorem by Jagannathan [7] concerning the relationship between fractional and parametric programming. This theorem is restated and proved in a somewhat simpler way. Finally, it is shown how the given algorithm can be related to the method of Isbell and Marlow [6] for linear fractional programming and to the quadratic parametric approach by Ritter [10]. The Appendix contains a numerical example. [ABSTRACT FROM AUTHOR]

Commentary is presented for an article published in the July 1960 issue of "Management Science," written by L. V. Kantorovich with an introductory note by T. C. Koopmans. According to the author, in his introduction Koopmans addresses in particular a linear programming problem and a matrix game presented by Kantorovich. Also presented is an interpretation of the article's treatment of decision variables and mathematical optimization. The author notes that the article presents algorithms that have been improved from their contemporary presentations.