Search results for "Optimization problem"
showing 10 items of 281 documents
A novel strategy for solving the stochastic point location problem using a hierarchical searching scheme
2014
Stochastic point location (SPL) deals with the problem of a learning mechanism (LM) determining the optimal point on the line when the only input it receives are stochastic signals about the direction in which it should move. One can differentiate the SPL from the traditional class of optimization problems by the fact that the former considers the case where the directional information, for example, as inferred from an Oracle (which possibly computes the derivatives), suffices to achieve the optimization-without actually explicitly computing any derivatives. The SPL can be described in terms of a LM (algorithm) attempting to locate a point on a line. The LM interacts with a random environme…
Optimistic NAUTILUS navigator for multiobjective optimization with costly function evaluations
2022
AbstractWe introduce novel concepts to solve multiobjective optimization problems involving (computationally) expensive function evaluations and propose a new interactive method called O-NAUTILUS. It combines ideas of trade-off free search and navigation (where a decision maker sees changes in objective function values in real time) and extends the NAUTILUS Navigator method to surrogate-assisted optimization. Importantly, it utilizes uncertainty quantification from surrogate models like Kriging or properties like Lipschitz continuity to approximate a so-called optimistic Pareto optimal set. This enables the decision maker to search in unexplored parts of the Pareto optimal set and requires …
ELECTRE III to dynamically support the decision maker about the periodic replacements configurations for a multi-component system
2013
The problem tackled by the present paper concerns the selection of the elements of a repairable and stochastically deteriorating multi-component system to replace (replacements configuration) during each scheduled and periodical system stop within a finite optimization cycle, by ensuring the simultaneous minimization of both the expected total maintenance cost and the system unavailability. To solve the considered problem, a combined approach between multi-objective optimization problem (MOOP) and multi-criteria decision making (MCDM) resolution techniques is proposed. In particular, the @e constraint method is used to single out the optimal Pareto frontier whereas the ELECTRE III multi-cri…
Some recent contributions to routing and location problems
2003
CORAL 2003, a Conference on Routing and Location, washeld in Puerto de la Cruz (Tenerife, Spain) from February24–26, 2003. A wonderful place, close to the black sand ofthe beach, and a nice temperature welcomed a group ofsenior and young researchers from Canada, England,France, Germany, and Spain. Social activities were alsoprovided and sponsored by the Cabildo Insular de Tenerife(the local government) and TITSA (the public bus transpor-tation company on the island). The conference corre-sponded to the third annual meeting of a research project,funded by the Spanish Ministry of Science and Technology,developing a Decision Support System for Vehicle Routingand Facility Location Problems (SAD…
An Optimized Roadside Units (RSU) Placement for Delay-Sensitive Applications in Vehicular Networks
2015
International audience; Over the last few years, a lot of applications have been developed for Vehicular Ad Hoc NETworks (VANETs) to exchange information between vehicles. However, VANET is basically a Delay Tolerant Network (DTN) characterized by intermittent connectivity, long delays and message losses especially in low density regions [1]. Thus, VANET requires the use of an infrastructure such as Roadside Units (RSUs) that permits to enhance the network connectivity. Nevertheless, due to their deployment cost, RSUs need to be optimally deployed. Hence, the main objective of this work is to provide an optimized RSUs placement for delay-sensitive applications in vehicular networks that imp…
Logical definability of NP-optimisation problems with monadic auxiliary predicates
1993
Given a first-order formula ϕ with predicate symbols e1...el, so,...,sr, an NP-optimisation problem on -structures can be defined as follows: for every -structure G, a sequence of relations on G is a feasible solution iff satisfies ϕ, and the value of such a solution is defined to be ¦S0¦. In a strong sense, every polynomially bounded NP-optimisation problem has such a representation, however, it is shown here that this is no longer true if the predicates s1, ...,sr are restricted to be monadic. The result is proved by an Ehrenfeucht-Fraisse game and remains true in several more general situations.
On the hardness of optimization in power-law graphs
2008
Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…
Optimal paths in weighted timed automata
2004
AbstractWe consider the optimal-reachability problem for a timed automaton with respect to a linear cost function which results in a weighted timed automaton. Our solution to this optimization problem consists of reducing it to computing (parametric) shortest paths in a finite weighted directed graph. We call this graph a parametric sub-region graph. It refines the region graph, a standard tool for the analysis of timed automata, by adding the information which is relevant to solving the optimal-reachability problem. We present an algorithm to solve the optimal-reachability problem for weighted timed automata that takes time exponential in O(n(|δ(A)|+|wmax|)), where n is the number of clock…
Discrete-mathematical approach to formal description of measurement procedure
1996
The discrete-mathematical model of measurement procedure is developed for facilitating the description of measurements in both quantitative and qualitative scales. On the basis of this model the Measurement Problem is formulated. It is shown that the problem can be considered, in the general case, as one of the discrete optimization problems. The suggested approach brings closer the concepts of a computing algorithm and measurement procedure so that it permits the application of similar tools for the analysis and development of both of them.
Determination of Pareto frontier in multi-objective maintenance optimization
2011
Abstract The objective of a maintenance policy generally is the global maintenance cost minimization that involves not only the direct costs for both the maintenance actions and the spare parts, but also those ones due to the system stop for preventive maintenance and the downtime for failure. For some operating systems, the failure event can be dangerous so that they are asked to operate assuring a very high reliability level between two consecutive fixed stops. The present paper attempts to individuate the set of elements on which performing maintenance actions so that the system can assure the required reliability level until the next fixed stop for maintenance, minimizing both the globa…