Search results for "Mathematical optimization"
showing 10 items of 1300 documents
The directed profitable rural postman problem with incompatibility constraints
2017
[EN] In this paper, we study a variant of the directed rural postman problem (RPP) where profits are asso- ciated with arcs to be served, and incompatibility constraints may exist between nodes and profitable arcs leaving them. If convenient, some of the incompatibilities can be removed provided that penalties are paid. The problem looks for a tour starting and ending at the depot that maximizes the difference between collected profits and total cost as sum of traveling costs and paid penalties, while satisfying remaining incompatibilities. The problem finds application in the domain of road transportation service, and in particular in the context of horizontal collaboration among carriers …
The periodic rural postman problem with irregular services on mixed graphs
2019
Abstract In this paper, we deal with an extension of the rural postman problem in which some links of a mixed graph must be traversed a given number of times over a time horizon. These links represent entities that must be serviced a specified number of times in some subsets of days (or periods) of the time horizon. The aim is to design a set of minimum-cost tours, one for each day/period of the time horizon, that satisfy the service requirements. We refer to this problem as the periodic rural postman problem with irregular services (PRPP–IS). Some practical applications of the problem can be found in road maintenance operations and road network surveillance, for example. In order to solve …
Efficient Linear-Scaling Density Functional Theory for Molecular Systems
2013
Despite recent progress in linear scaling (LS) density function theory (DFT), the computational cost of the existing LS methods remains too high for a widespread adoption at present. In this work, we exploit nonorthogonal localized molecular orbitals to develop a series of LS methods for molecular systems with a low computational overhead. High efficiency of the proposed methods is achieved with a new robust two-stage variational procedure or by replacing the optimization altogether with an accurate nonself-consistent approach. We demonstrate that, even for challenging condensed-phase systems, the implemented LS methods are capable of extending the range of accurate DFT simulations to molec…
Modélisation du comportement des agriculteurs face au risque dans un modèle de programmation mathématique positive (PMP) à grande échelle
2017
Agricultural production is characterized for being a risky business due to weather variability, market instability, plant diseases as well as climate change and political economy uncertainty. The modelling of risk at farm level is not new, however, the inclusion of risk in Positive Mathematical Programming (PMP) models is particularly challenging. Most of the few existing PMP-risk approaches have been conducted at farm-type level and for a very limited and specific sample of farms. This implies that the modelling of risk and uncertainty at individual farm level and in a large scale system is still a challenging task. The aim of this paper is to formulate, estimate and test a robust methodol…
Non-convex power allocation games in MIMO cognitive radio networks
2013
Consideramos un escenario de reparto del espectro, basado en la detección, en una red de radio cognitiva MIMO donde el objetivo general es maximizar el rendimiento total de cada usuario de radio cognitiva optimizando conjuntamente la operación de detección y la asignación de potencia en todos los canales, bajo una restricción de interferencia para los usuarios primarios. Los problemas de optimización resultantes conducen a un juego no convexo, que presenta un nuevo desafío a la hora de analizar los equilibrios de este juego. Con el fin de hacer frente a la no convexidad del juego, utilizamos un nuevo concepto relajado de equilibrio, el equilibrio cuasi-Nash (QNE). Se demuestran las condicio…
Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem
2017
[EN] The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distan…
A heuristic algorithm for project scheduling with splitting allowed
1996
In this article, we analyze the precedence diagramming method, the only published algorithm for time-only project scheduling with activity splitting allowed. The criteria used in this method (forward and backward pass computations) for deciding when an activity has to be interrupted are shown to be invalid in some situations. We look into the causes of these failures and propose new formulae that always provide feasible solutions. The new algorithm has been tested on 240 randomly generated problems ranging up to 600 activities and 7,200 precedence relationships, resulting in an average deviation from optima of less than 1 percent.
Adaptive memory programing for the robust capacitated international sourcing problem
2008
The International Sourcing Problem consists of selecting a subset from an available set of potential suppliers internationally located. The selected suppliers must meet the demand for items from a set of plants, which are also located worldwide. Since the costs are affected by macroeconomic conditions in the countries where the supplier and the plant are located, the formulation considers the uncertainty associated with changes in these conditions. We formulate the robust capacitated international sourcing problem by means of a scenario-optimization approach. When dealing with uncertainty, one of the most common approaches in the literature is to formulate the problem via a set of possible …
Scatter Search and Path Relinking: Foundations and Advanced Designs
2004
Scatter Search and its generalized form Path Relinking, are evolutionary methods that have been successfully applied to hard optimization problems. Unlike genetic algorithms, they operate on a small set of solutions and employ diversification strategies of the form proposed in Tabu Search, which give precedence to strategic learning based on adaptive memory, with limited recourse to randomization. The fundamental concepts and principles were first proposed in the 1970s as an extension of formulations, dating back to the 1960s, for combining decision rules and problem constraints. (The constraint combination approaches, known as surrogate constraint methods, now independently provide an impo…
Determining the Parameters of a Sugeno Fuzzy Controller Using a Parallel Genetic Algorithm
2013
Developed in the mid 1970s, the technique based on genetic algorithms proved its usefulness in finding optimal or near optimal solutions to problems for which accurate solving strategies are either non-existent or require excessively long running time. We implemented a genetic algorithm to determine the parameters of a Sugeno fuzzy controller for the Truck Backer-Upper problem (This problem is considered an acknowledged benchmark in nonlinear system identification.). Less known at first than Mamdami fuzzy controllers, Sugeno fuzzy controllers became popular once they were included into the ANFIS neuro-fuzzy Matlab library. By their nature, Sugeno controllers can be regarded as interpolation…