Search results for "Operations Research"
showing 10 items of 1297 documents
Solving the discrete multiple criteria problem using linear prospect theory
1994
Abstract Prospect theory developed by Kahneman and Tversky is a popular model of choice in decision problems under uncertainty. Prospect theory has recently been extended to multiple criteria choice problems. In this paper, an interactive method for solving discrete multiple criteria decision problems, based on prospect theory type value functions, has been developed. Piecewise linear marginal value functions are assumed to approximate the S-shaped value functions of prospect theory. Therefore, the proposed procedure is valid only for convex preferences.
A note on the separation of subtour elimination constraints in elementary shortest path problems
2013
Abstract This note proposes an alternative procedure for identifying violated subtour elimination constraints (SECs) in branch-and-cut algorithms for elementary shortest path problems. The procedure is also applicable to other routing problems, such as variants of travelling salesman or shortest Hamiltonian path problems, on directed graphs. The proposed procedure is based on computing the strong components of the support graph. The procedure possesses a better worst-case time complexity than the standard way of separating SECs, which uses maximum flow algorithms, and is easier to implement.
GRASP and path relinking for the matrix bandwidth minimization
2004
In this article we develop a greedy randomized adaptive search procedure (GRASP) for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix, which keeps the nonzero elements in a band that is as close as possible to the main diagonal. The proposed method may be coupled with a Path Relinking strategy to search for improved outcomes. Empirical results indicate that the proposed GRASP implementation compares favourably to classical heuristics. GRASP with Path Relinking is also found to be competitive with a recently published tabu search algorithm that is considered one of the best currently available for band…
Lower bounds and heuristics for the Windy Rural Postman Problem
2020
[EN] In this paper we present several heuristic algorithms and a cutting-plane algorithm for the Windy Rural Postman Problem. This problem contains several important Arc Routing Problems as special cases and has very interesting real-life applications. Extensive computational experiments over different sets of instances are also presented.
Tabu search and GRASP for the maximum diversity problem
2007
In this paper, we develop new heuristic procedures for the maximum diversity problem (MDP). This NP-hard problem has a significant number of practical applications such as environmental balance, telecommunication services or genetic engineering. The proposed algorithm is based on the tabu search methodology and incorporates memory structures for both construction and improvement. Although proposed in seminal tabu search papers, memory-based constructions have often been implemented in naive ways that disregard important elements of the fundamental tabu search proposals. We will compare our tabu search construction with a memory-less design and with previous algorithms recently developed for…
A heuristic to schedule flexible job-shop in a glass factory
2005
We describe the design and implementation of a scheduling system in a glass factory. The factory produces a large variety of manufactured glass objects in a complex process ranging from melting the glass in the furnaces and blowing it automatically or manually to decorating, assembling and packing it. The structure basically corresponds to a flexible job-shop scheduling problem with some special characteristics. On the one hand, dealing with hot liquid glass imposes no-wait constraints on some operations. On the other hand, skilled workers performing some manual tasks are modelled as special machines. The system produces approximate solutions in very short computing times, trying to minimiz…
A purification algorithm for semi-infinite programming
1992
Abstract In this paper we present a purification algorithm for semi-infinite linear programming. Starting with a feasible point, the algorithm either finds an improved extreme point or concludes with the unboundedness of the problem. The method is based on the solution of a sequence of linear programming problems. The study of some recession conditions has allowed us to establish a weak assumption for the finite convergence of this algorithm. Numerical results illustrating the method are given.
Separating capacity constraints in the CVRP using tabu search
1998
Abstract Branch and Cut methods have shown to be very successful in the resolution of some hard combinatorial optimization problems. The success has been remarkable for the Symmetric Traveling Salesman Problem (TSP). The crucial part in the method is the cutting plane algorithm: the algorithm that looks for valid inequalities that cut off the current nonfeasible linear program (LP) solution. In turn this part relies on a good knowledge of the corresponding polyhedron and our ability to design algorithms that can identify violated valid inequalities. This paper deals with the separation of the capacity constraints for the Capacitated Vehicle Routing Problem (CVRP). Three algorithms are prese…
A tabu search algorithm for a two-dimensional non-guillotine cutting problem
2007
In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.
A review on discrete diversity and dispersion maximization from an OR perspective
2022
Abstract The problem of maximizing diversity or dispersion deals with selecting a subset of elements from a given set in such a way that the distance among the selected elements is maximized. The definition of distance between elements is customized to specific applications, and the way that the overall diversity of the selected elements is computed results in different mathematical models. Maximizing diversity by means of combinatorial optimization models has gained prominence in Operations Research (OR) over the last two decades, and constitutes nowadays an important area. In this paper, we review the milestones in the development of this area, starting in the late eighties when the first…