Recently on-demand food delivery service has become very popular in China. More than 30 million orders are placed by eaters of Meituan-Dianping everyday. Delicacies are delivered to eaters in 30 minutes on average. To...
详细信息
ISBN:
(纸本)9781450379984
Recently on-demand food delivery service has become very popular in China. More than 30 million orders are placed by eaters of Meituan-Dianping everyday. Delicacies are delivered to eaters in 30 minutes on average. To fully leverage the ability of our couriers and restaurants, delivery scope is proposed as an infrastructure product for on-demand food delivery area. A delivery scope based retrieval system is designed and built on our platform. In order to draw suitable delivery scopes for millions of restaurant partners, we propose a pioneering delivery scope generation framework. In our framework, a single delivery scope generation algorithm is proposed by using spatial computational techniques and data mining techniques. Moreover, a scope scoring algorithm and decision algorithm are proposed by utilizing machine learning models and combinatorialoptimization techniques. Specifically, we propose a novel delivery scope sample generation method and use the scope related features to estimate order numbers and average delivery time in a period of time for each delivery scope. then we formalize the candidate scopes selection process as a binary integerprogramming problem. Both branch&bound algorithm and a heuristic search algorithm are integrated in our system. Results of online experiments show that scopes generated by our new algorithm significantly outperform manual generated ones. Our algorithm brings more orders without hurt of users' experience. After deployed online, our system has saved thousands of hours for operation staff, and it is considered to be one of the most useful operation tools to balance demand of eaters and supply of restaurants and couriers.
We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. this resolves a long-standing open question posed in [Faigle, Kern, Fekete, Hochstattler, Mathemat...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
We provide an efficient algorithm for computing the nucleolus for an instance of a weighted cooperative matching game. this resolves a long-standing open question posed in [Faigle, Kern, Fekete, Hochstattler, Mathematical programming, 1998].
this paper focuses on a real case of connection of subsea oil wells to offshore platforms using pipe laying support vessels. the objective of this study is to maximize the oil production curve through an optimized use...
详细信息
ISBN:
(纸本)9783030587994;9783030587987
this paper focuses on a real case of connection of subsea oil wells to offshore platforms using pipe laying support vessels. the objective of this study is to maximize the oil production curve through an optimized use of the out-sourced fleet. Specific features of this scenario are considered, such as technical constraints of each vessel, the availability of the vessels, materials for connection, and the end of the previous phase, called completion. A mixed integer linear programming model is developed considering several constraints that structure this complex situation, among which a relevant characteristic of the problem: the increase of the production curve using injection wells to fight the natural decline of producing wells over time. this mathematical model was tested in small computational instances, showing adequate behavior, which demonstrates that it faithfully represents the situation portrayed and can be used, combined with more advanced computational resources, to achieve better results.
this paper, inspired by a real production process of steel hardening, investigates a scheduling problem to minimize the idle energy consumption of machines. the energy minimization is achieved by switching a machine t...
详细信息
ISBN:
(纸本)9789897583964
this paper, inspired by a real production process of steel hardening, investigates a scheduling problem to minimize the idle energy consumption of machines. the energy minimization is achieved by switching a machine to some power-saving mode when it is idle. For the steel hardening process, the mode of the machine (i.e., furnace) can be associated with its inner temperature. Contrary to the recent methods, which consider only a small number of machine modes, the temperature in the furnace can be changed continuously, and so an infinite number of the power-saving modes must be considered to achieve the highest possible savings. To model the machine modes efficiently, we use the concept of the energy function, which was originally introduced in the domain of embedded systems but has yet to take roots in the domain of production research. the energy function is illustrated with several application examples from the literature. Afterward, it is integrated into a mathematical model of a scheduling problem with parallel identical machines and jobs characterized by release times, deadlines, and processing times. Numerical experiments show that the proposed model outperforms a reference model adapted from the literature.
A clutter is identically self-blocking if it is equal to its blocker. We prove that every identically self-blocking clutter different from {{a}} is nonideal. Our proofs borrow tools from Gauge Duality and Quadratic Pr...
详细信息
ISBN:
(数字)9783030179533
ISBN:
(纸本)9783030179533;9783030179526
A clutter is identically self-blocking if it is equal to its blocker. We prove that every identically self-blocking clutter different from {{a}} is nonideal. Our proofs borrow tools from Gauge Duality and Quadratic programming. Along the way we provide a new lower bound for the packing number of an arbitrary clutter.
We examine how sparse feasible solutions of integer programs are, on average. Average case here means that we fix the constraint matrix and vary the right-hand side vectors. For a problem in standard form with m equat...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
We examine how sparse feasible solutions of integer programs are, on average. Average case here means that we fix the constraint matrix and vary the right-hand side vectors. For a problem in standard form with m equations, there exist LP feasible solutions with at most m many nonzero entries. We show that under relatively mild assumptions, integer programs in standard form have feasible solutions with O(m) many nonzero entries, on average. Our proof uses ideas from the theory of groups, lattices, and Ehrhart polynomials. From our main theorem we obtain the best known upper bounds on the integer Caratheodory number provided that the determinants in the data are small.
Given a factorable function f, we propose a procedure that constructs a concave underestimator of f that is tight at a given point. these underestimators can be used to generate intersection cuts. A peculiarity of the...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
Given a factorable function f, we propose a procedure that constructs a concave underestimator of f that is tight at a given point. these underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.
We consider integer linear programs whose solutions are binary matrices and whose (sub-)symmetry groups are symmetric groups acting on (sub-)columns. We propose a framework to build (sub-)symmetry-breaking inequalitie...
详细信息
ISBN:
(数字)9783030179533
ISBN:
(纸本)9783030179533;9783030179526
We consider integer linear programs whose solutions are binary matrices and whose (sub-)symmetry groups are symmetric groups acting on (sub-)columns. We propose a framework to build (sub-)symmetry-breaking inequalities for such programs, by introducing one additional variable per sub-symmetry group considered. the proposed framework is applied to derive inequalities breaking both symmetries and sub-symmetries in the graph coloring problem and in the ramp constrained min-up/min-down unit commitment problem.
this paper addresses the resolution of combinatorialoptimization problems presenting some kind of recurrent structure, coupled with machine learning techniques. Stemming from the assumption that such recurrent proble...
详细信息
ISBN:
(纸本)9789897583520
this paper addresses the resolution of combinatorialoptimization problems presenting some kind of recurrent structure, coupled with machine learning techniques. Stemming from the assumption that such recurrent problems are the realization of an unknown generative probabilistic model, data is collected from previous resolutions of such problems and used to train a supervised learning model for multi-label classification. this model is exploited to predict a subset of decision variables to be set heuristically to a certain reference value, thus becoming fixed parameters in the original problem. the remaining variables then form a smaller subproblem whose solution, while not guaranteed to be optimal for the original problem, can be obtained faster, offering an advantageous tool for tackling time-sensitive tasks.
We propose a Branch-and-Cut algorithm for the robust influence maximization problem. the influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
We propose a Branch-and-Cut algorithm for the robust influence maximization problem. the influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum number of other actors. We assume that the social network is given in the form of a graph with node thresholds to indicate the resistance of an actor to influence, and arc weights to represent the strength of the influence between two actors. In the robust version of the problem that we study, the node thresholds are affected by uncertainty and we optimize over a worst-case scenario within a given robustness budget. Numerical experiments show that we are able to solve to optimality instances of size comparable to other exact approaches in the literature for the non-robust problem, but in addition to this we can also tackle the robust version with similar performance.
暂无评论