1,721,161 research outputs found
A branch-and-bound algorithm for the linear ordering problem with cumulative costs
No full textThe linear ordering problem with cumulative costs is an -hard combinatorial optimization problem arising from an application in UMTS mobile-phone communication systems. This paper presents a polynomially computable lower bound that is particularly effective when embedded in a branch-and-bound algorithm. The same idea can be further exploited to sort the children nodes at each node of the search tree, in order to find the optimal solution earlier. A suitable truncation of the resulting branch-and-bound algorithm results in a fast constructive heuristic
A network flow model of the Northern Italy waterway system
Full text linkThe objective of this study was to develop a mathematical programming model, namely a network flow model, to provide insight into the potential capacity of the Northern Italy waterway system. We estimate the potential flow that can be transferred between the Adriatic sea and inland harbors through the waterway system made of the river Po and its surrounding canals. For this purpose a network flow model was developed, where the capacity of each arc depends on specific characteristics such as the presence of locks or one-way transit bottlenecks. The capacity of the harbors was modeled according to the number of quays and cranes available for freight transfer operations. The mathematical formulation of the problem leads to a variation of the classical maximum flow problem on capacitated networks that is easily solvable to proven optimality in a negligible computing time by any linear programming solver. Several scenarios were studied, with and without navigation in the Adriatic sea, with limited or unlimited navigation along given parts of the river. Future possible scenarios were also considered to evaluate the impact of infrastructure interventions to empower some inland harbors and to make some parts of river Po adapt to higher class barges. This mathematical programming approach based on a network flow model allows for quickly solving realistic problem instances; furthermore it provides quantitative information about bottlenecks, corresponding to binding constraints, owing to post-optimal sensitivity analysis. This provides useful indications for a rational allocation of scarce financial resources to make the waterway system a viable and convenient alternative to other transportation means
Efficient optimization of the Held–Karp lower bound
Full text linkGiven a weighted undirected graph G = (V,E), the Held–Karp lower bound for the Traveling Salesman Problem (TSP) is
obtained by selecting an arbitrary vertex p 2 V , by computing a minimum cost tree spanning V {p} and adding two
minimum cost edges adjacent to p. In general, different selections of vertex p provide different lower bounds. In this paper
it is shown that the selection of vertex p can be optimized, to obtain the largest possible Held–Karp lower bound, with
the same worst-case computational time complexity required to compute a single minimum spanning tree. Although
motivated by the optimization of the Held–Karp lower bound for the TSP, the algorithm solves a more general problem,
allowing for the efficient pre-computation of alternative minimum spanning trees in weighted graphs where any vertex can
be deleted
A mathematical programming solution to the Mars Express memory dumping problem
No full textThe problem of computing a schedule of maximum robustness for the Mars Express mission is formulated and solved via linear programming (LP). We also provide a characterization of ??easy?? and ??difficult?? instances such that the former ones can be solved to optimality directly, without having recourse to any optimization algorithm. In both cases, provably optimal solutions are obtained in shorter computing time compared to previously published approaches. Starting from the simplified model already described in the literature, we extend it to consider real constraints. For this purpose, we define an integer LP model with four different objective functions and develop a decision support system based on hierarchical optimization of the first two objectives and multicriteria optimization of the other two
An optimization algorithm for a penalized knapsack problem
No full textWe study a variation of the knapsack problem in which each item has a profit, a weight and a penalty; the sum of profits of the selected items minus the largest penalty associated with the selected items must be maximized. We present an ILP formulation and an exact optimization algorithm
A combinatorial optimization problem arising from text classification
No full textWe study a combinatorial optimization problem related to the automatic classification of texts. The problem consists of covering a given text using strings from a given set, where a cost is incurred for each type of string used. We give a 0-1 linear programming formulation and we report on computational experiences on very large instances using two different Lagrangean relaxations and heuristic algorithms based on simulated annealing and threshold accepting
A branch-and-price algorithm for the multi-source Weber problem
No full textWe present a branch-and-price algorithm for the exact solution of the multi-source Weber problem, a classical NP-hard optimisation problem in location science with binary variables and non-linear objective. The algorithm is based on a set covering reformulation whose linear relaxation is solved via column generation at every node of a search tree. The pricing subproblem is equivalent to a single-source Weber problem with limited distances. The algorithm solved to optimality several previously unsolved instances with some thousands of points and some hundreds of sources. Computational experiments show that the algorithm is particularly effective at solving instances in which the ratio between the number of sources and the number of points is high
Dynamic programming algorithms for the elementary shortest path problem with resource constraints
No full textWhen vehicle routing problems with additional constraints (e.g. capacities or time windows) are solved via column generation and branch-and-price, it is common that the pricing problem requires
the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the nodes. The pricing problem is usually solved via dynamic programming in two possible ways: requiring elementary paths or allowing paths with cycles. We experimentally compare these two strategies and we evaluate the effectiveness of some algorithmic ideas to improve their performance
A note on the approximation of the Asymmetric Traveling Salesman Problem
No full textWe show that some asymmetric traveling salesman problem (ATSP) instances are approximable within bounds equal to 3 and 9/5, when they satisfy sufficient conditions more restrictive than the triangle inequality, very simple to test and nicely structured: they only depend on a measure of satisfaction of the triangle inequality and a measure of the graph asymmetry. We discuss the applicability of such conditions and we present two preprocessing linear programs to reformulate ATSP instances into equivalent ones achieving data-dependent bounds by the same approximation algorithms
- …
