1,721,001 research outputs found
A graph clustering based decomposition approach for large scale p-median problems
No full textThe p-median problem (PMP) is the well known network optimization problem of discrete location theory. In many real applications PMPs is defined on very large scale networks, for which ad-hoc exact and/or heuristic methods have to be developed. To this aim, in this work we propose a heuristic decomposition approach which exploits the decomposition of the network into disconnected components obtained by a graph clustering algorithm. Then, in each component several PMPs are solved for suitable ranges of p by a Lagrangian dual and simulated annealing based algorithm. The solution of the whole initial problem is obtained combining all the PMPs solutions through a multi-choice knapsack model. The proposed approach is tested using several graph clustering algorithms and compared with the results of the state-of-the-art heuristic methods
Valid inequalities for time-indexed formulations of the runway scheduling problem
Get PDFThe problem of sequencing and scheduling airplanes landing and taking off on a runway is under consideration. We propose a new family of valid inequalities which are obtained from the study of the single machine scheduling problem polytope
Polyhedral study of simple plant location problem with order
No full textThis paper is addressed to the generalization of simple plant location problem where customer's preferences are taken into account. Some basic polyhedral studies and a new family of facet-defining inequalities are given. The effectiveness of the proposed approach is illustrated by the computational experience
A computational study of exact knapsack separation for the generalized assignment problem
No full textGeneralized assignment problem, Cutting plane algorithm, Exact separation,
Computational testing of a separation procedure for the knapsack set with a single continuous variable
No full text We study an exact separation procedure—SEP-MK—for the knapsack set with a single continuous variable XMK. Then, we address the question of whether SEP-MK can be of practical use in tightening mixed-integer programming (MIP) formulations when using standard (floating-point) MIP solvers. To this purpose, we present a separation procedure for MIP problems—SEP-MIPMK—where we derive knapsack sets of the form XMK by aggregating the continuous variables in the mixed knapsack inequalities of the formulation. Then, we use SEP-MK to generate cutting planes. Before the continuous variables are aggregated, the mixed knapsack inequalities are modified through the use of a bound substitution procedure to take into account fixed and variable bounds on the continuous variables. Bound substitution is made according to some heuristic rules, so even if its basic component SEP-MK is “exact,” the overall separation procedure for MIP problems, SEP-MIPMK, is heuristic. We perform a computational study on a wide set of mixed-integer programming instances from the MIPLIB 2003 [Achterberg, T., T. Koch, A. Martin. 2006. Mixed Integer Problem Library (MIPLIB) 2003. Konrad-Zuse-Zentrum für Informationstechnik Berlin, Berlin. http://miplib.zib.de] and Mittelmann [Mittelmann, H. 2010. MILP testcases. http://plato.asu.edu/ftp/milp] benchmark sets. Computational experiments confirm that lifted cover and mixed-integer rounding (MIR) inequalities are effective from a computational viewpoint. Nevertheless, there are several instances where SEP-MIPMK is able to significantly raise the lower bounds given by lifted cover and MIR inequalities. </jats:p
The dispatching problem on multitrack territories: Heuristic approaches based on mixed integer linear programming
No full textTrains running through railway lines often accumulate some delay. When this happens, rescheduling and rerouting decisions must be quickly taken in real time. Despite the fact that even a single wrong decision may deteriorate the performance of the whole railway network, this complex optimization task is still basically performed by human operators. In very recent years, the interest of train operators to implement automated decision systems has grown. Not incidentally, the railway application section (RAS) of INFORMS has issued a challenge devoted to this problem concomitantly with the INFORMS Annual Meeting 2012. In this article, we describe two heuristic approaches to solve the RAS problem based on a mixed integer linear programming formulation, and we report computational results on the three RAS instances and on an additional set of instances defined on a more congested network. Computational results on the challenge test bed show that our algorithms positively compare with other approaches to the RAS problem
An aggregation heuristic for large scale p-median problem
No full textThe p-median problem (PMP) consists of locating p facilities (medians) in order to minimize the sum of distances from each client to the nearest facility. The interest in the large-scale PMP arises from applications in cluster analysis, where a set of patterns has to be partitioned into subsets (clusters) on the base of similarity. In this paper we introduce a new heuristic for large-scale PMP instances, based on Lagrangean relaxation. It consists of three main components: subgradient column generation, combining subgradient optimization with column generation; a ''core'' heuristic, which computes an upper bound by solving a reduced problem defined by a subset of the original variables chosen on a base of Lagrangean reduced costs; and an aggregation procedure that defines reduced size instances by aggregating together clients with the facilities. Computational results show that the proposed heuristic is able to compute good quality lower and upper bounds for instances up to 90,000 clients and potential facilities
- …
