Home  About us  Contact
 

Oper Res (oper + res)

Distribution by Scientific Domains
Mathematics and Statistics75%

Selected Abstracts

Unsupervized aggregation of commensurate correlated attributes by means of the choquet integral and entropy functionals,

INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS, Issue 2 2008
Ivan Kojadinovic
In the framework of aggregation by the discrete Choquet integral, the unsupervized method for the identification of the underlying capacity initially put forward in Kojadinovic, Eur J Oper Res 2004; 155:741,751 is presented and improvements are proposed. The suggested approach consists in replacing the subjective notion of importance of a subset of attributes by that of information content of a subset of attributes, which can be estimated from the set of profiles by means of an entropy measure. An example of the application of the proposed methodology is given: in the absence of initial preferences, the approach is applied to the evaluation of students. © 2008 Wiley Periodicals, Inc. [source]

Noncooperative cost spanning tree games with budget restrictions

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 8 2008
Gustavo Bergantiños
Abstract We extend the noncooperative game associated with the cost spanning tree problem introduced by Bergantiños and Lorenzo (Math Method Oper Res 59(2004), 393,403) to situations where agents have budget restrictions. We study the Nash equilibria, subgame perfect Nash equilibria, and strong Nash equilibria of this game. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008 [source]

A generalization of the weighted set covering problem

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 2 2005
Jian Yang
Abstract We study a generalization of the weighted set covering problem where every element needs to be covered multiple times. When no set contains more than two elements, we can solve the problem in polynomial time by solving a corresponding weighted perfect b -matching problem. In general, we may use a polynomial-time greedy heuristic similar to the one for the classical weighted set covering problem studied by D.S. Johnson [Approximation algorithms for combinatorial problems, J Comput Syst Sci 9 (1974), 256,278], L. Lovasz [On the ratio of optimal integral and fractional covers, Discrete Math 13 (1975), 383,390], and V. Chvatal [A greedy heuristic for the set-covering problem, Math Oper Res 4(3) (1979), 233,235] to get an approximate solution for the problem. We find a worst-case bound for the heuristic similar to that for the classical problem. In addition, we introduce a general type of probability distribution for the population of the problem instances and prove that the greedy heuristic is asymptotically optimal for instances drawn from such a distribution. We also conduct computational studies to compare solutions resulting from running the heuristic and from running the commercial integer programming solver CPLEX on problem instances drawn from a more specific type of distribution. The results clearly exemplify benefits of using the greedy heuristic when problem instances are large. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2005 [source]

Path inequalities for the vehicle routing problem with time windows

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 4 2007
Brian Kallehauge
Abstract In this paper we introduce a new formulation of the vehicle routing problem with time windows (VRPTW) involving only binary variables. The new formulation is based on the formulation of the asymmetric traveling salesman problem with time windows by Ascheuer et al. (Networks 36 (2000) 69,79) and has the advantage of avoiding additional variables and linking constraints. In the new formulation, time windows are modeled using path inequalities that eliminate time and capacity infeasible paths. We present a new class of strengthened path inequalities based on the polyhedral results obtained by Mak (Ph.D. Thesis, 2001) for a variant of the TSP. We study the VRPTW polytope and determine its dimension. We show that the lifted path inequalities are facet defining under certain assumptions. We also introduce precedence constraints in the context of the VRPTW. Computational experiments are performed with a branch and cut algorithm on the Solomon test problems with wide time windows. Based on results on 25-node problems, the outcome is promising compared to leading algorithms in the literature. In particular, we report a solution to a previously unsolved 50-node Solomon test problem R208. The conclusion is therefore that a polyhedral approach to the VRPTW is a viable alternative to the path formulation of Desrochers et al. (Oper Res 40 (1992), 342,354). © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 273,293 2007 [source]