On a multicriteria shortest path problem

Multicriteria shortest path problems have not been treated intensively in the specialized literature, despite their potential applications. In fact, a single objective function may not be sufficient to characterize a practical problem completely. For instance, in a road network several parameters (as time, cost, distance, etc.) can be assigned to each arc. Clearly, the shortest path may be too expensive to be used. Nevertheless the decision-maker must be able to choose some solution, possibly not the best for all the criteria.In this paper we present two algorithms for this problem. One of them is an immediate generalization of the multiple labelling scheme algorithm of Hansen for the bicriteria case. Based on this algorithm, it is proved that any pair of nondominated paths can be connected by nondominated paths. This result is the support of an algorithm that can be viewed as a variant of the simplex method used in continuous linear multiobjective programming. A small example is presented for both algorithms.     

Existence of an outcome- and risk-guaranteed solution to a multicriteria problem

A multicriteria decision-making problem under uncertainty in a class of Borel measurable counterstrategies is considered. The concept of an outcome- and risk-guaranteed solution is introduced and an existence theorem is proved.     

A network solution to a general vehicle scheduling problem

Dantzig and Fulkerson and later Bellmore et al. have shown that certain vehicle (tanker) scheduling problems can be formulated as minimum cost flow problems on a network. In this paper, the results of Dantzig and Fulkerson are extended to the case where more than one type of vehicle can be used in the determination of an optimal fleet. (In tanker scheduling terminology; how many small, medium and large tankers would form an optical fleet.) It is seen how the problem can be formulated as a modified transportation problem where flow in some arcs is conditioned to there being flow on certain other arcs. These “conditional” transportation problems were solved directly as linear programs and showed the peculiarity of terminating all integer in spite of having a constraint matrix, which does not satisfy the well known sufficient conditions for urimodularity. We discuss the implementation of the model and its empirical results.     

Approximate solution of a resource-constrained scheduling problem

This paper is devoted to the approximate solution of a strongly NP-hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact solution methods, extensive computational results demonstrating its practical ability to produce acceptable solutions, in a precisely defined sense. Additionally, our experiments are in remarkable agreement with certain theoretical properties of our simulated annealing scheme. The paper concludes with a short discussion on further research. This research was supported in part by Association Nationale de la Recherche Technique grant CIFRE-121/2004.     

On the number of non-dominated points of a multicriteria optimization problem

This work proposes an upper bound on the maximal number of non-dominated points of a multicriteria optimization problem. Assuming that the number of values taken on each criterion is known, the criterion space corresponds to a comparability graph or a product of chains. Thus, the upper bound can be interpreted as the stability number of a comparability graph or, equivalently, as the width of a product of chains. Standard approaches or formulas for computing these numbers are impractical. We develop a practical formula which only depends on the number of criteria. We also investigate the tightness of this upper bound and the reduction of this bound when feasible, possibly efficient, solutions are known.     

A stabilization method for solution of a parametric multicriteria equilibrium programming problem

A multicriteria equilibrium programming problem comprising a mathematical programming problem as a particular case, a multicriteria Pareto-point search problem, a minimization problem with equilibrium selection of the feasible set, etc., is considered. It is assumed that the initial data are known only approximately. In view of the fact that the considered problem is generally unstable with respect to the input data, a regularization method, which is a generalization of the Tikhonov stabilization method, is proposed. Conditions for matching the method parameters to the error in the input data are presented. The convergence of this method is analyzed.     

An interactive solution approach for a bi-objective semi-desirable location problem

In this study, we consider a semi-desirable facility location problem in a continuous planar region considering the interaction between the facility and the existing demand points. A facility can be defined as semi-desirable if it has both undesirable and desirable effects to the people living in the vicinity. Our aim is to maximize the weighted distance of the facility from the closest demand point as well as to minimize the service cost of the facility. The distance between the facility and the demand points is measured with the rectilinear metric. For the solution of the problem, a three-phase interactive geometrical branch and bound algorithm is suggested to find the most preferred efficient solution. In the first two phases, we aim to eliminate the parts of the feasible region the inefficiency of which can be proved. The third phase has been suggested for an interactive search in the remaining regions with the involvement of a decision maker (DM). In the third phase, the DM is given the opportunity to use either an exact or an approximate procedure to carry out the search. The exact procedure is based on the reference point approach and guarantees to find an efficient point as the most preferred solution. On the other hand, in the approximate procedure, a hybrid methodology is used to increase the efficiency of the reference point approach. The approximate procedure can be used when the DM prefers to see locally efficient solutions so as to save computation time. We demonstrate the performance of the proposed method through example problems.     

An interactive dynamic programming approach to multicriteria discrete programming

Several interactive schemes for solving multicriteria discrete programming problems are developed under a dynamic programming framework. It is assumed that the decision maker's preference structure satisfies the conditions of transitivity, monotonicity, and nonsatiation. Hybrid procedures are also structured by including branch and bound ideas into the recursions. Initial computational results are offered.     

On the second solution to a critical growth Robin problem

We investigate the existence of the second mountain-pass solution to a Robin problem, where the equation is at critical growth and depends on a positive parameter λ. More precisely, we determine existence and nonexistence regions for this type of solutions, depending both on λ and on the parameter in the boundary conditions.     

Case study: problem formulation and solution for a real-world sports scheduling problem

This case study paper describes a problem faced every year by the Devon Cricket League in England. Every league match requires two officiating umpires. There are various preferences relating to the deployment of umpires that fall short of being definite constraints. The requirement was to produce a computer system that would allocate umpires in a satisfactory manner without the need for human interaction, since the users of the system will be unqualified amateurs. This necessitated the construction of a very complex objective function, using imprecise and ill-defined information. The biggest challenge was thus one of problem formulation; the solution technique was relatively straightforward. The system has been put into successful use and it is expected that its use will continue indefinitely. The work raises ethical issues regarding work done for customers who are inexperienced amateurs.     

On the on-line maintenance scheduling problem

A machine instantly serves requests but needs to undergo maintenance after serving a maximum of L requests. We want to maximize the number of requests served. In the on-line version, we prove that serving L requests before placing a maintenance is 0.5-competitive and is best possible for deterministic algorithms. We describe a 0.585-competitive randomized algorithm and show an upper bound of \(2L/(3L-1)\). We also analyze the empirical performance of various on-line algorithms on specific arrival distributions.     

Counting and enumeration complexity with application to multicriteria scheduling

In this paper we tackle an important point of combinatorial optimisation: that of complexity theory when dealing with the counting or enumeration of optimal solutions. Complexity theory has been initially designed for decision problems and evolved over the years, for instance, to tackle particular features in optimisation problems. It has also evolved, more or less recently, towards the complexity of counting and enumeration problems and several complexity classes, which we review in this paper, have emerged in the literature. This kind of problems makes sense, notably, in the case of multicriteria optimisation where the aim is often to enumerate the set of the so-called Pareto optima. In the second part of this paper we review the complexity of multicriteria scheduling problems in the light of the previous complexity results. This paper appeared in 4OR 3(1), 1–21, 2005.     

On Torricelli's geometrical solution to a problem of Fermat

Around 1640, Torricelli devised a geometrical solution to aproblem, allegedly first formulated in the early 1600s by Fermat:‘given three points in a plane, find a fourth point suchthat the sum of its distances to the three given points is assmall as possible’. We account for Torricelli's constructiontogether with a correctness proof which also establishes thevalidity of results obtained much later. We introduce furthermorea so-called complementary problem, arising when the given trianglehas one angle exceeding 120°, and for which an incorrectsolution is given in 1941 by Courant & Robbins. Some historicalnotes conclude the paper.     

On a resource-constrained scheduling problem with application to distributed systems reconfiguration

This paper is devoted to the study of a resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high availability real-time distributed systems. Informally, this problem consists, starting from an arbitrary initial distribution of processes on the processors of a distributed system, in finding the least disruptive sequence of operations (non-impacting process migrations or temporary process interruptions) at the end of which the system ends up in another predefined arbitrary state. The main constraint is that the capacity of the processors must not be exceeded during the reconfiguration. After a brief survey of the literature, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. We then present a branch-and-bound algorithm for the general case along with computational results demonstrating its practical relevance. The paper is concluded by a discussion on further research.     

On solution strategies to Saint-Venant problem

Different solution strategies to the relaxed Saint-Venant problem are presented and comparatively discussed from a mechanical and computational point of view. Three approaches are considered; namely, the displacement approach, the mixed approach, and the modified potential stress approach. The different solution strategies lead to the formulation of two-dimensional Neumann and Dirichlet boundary-value problems. Several solution strategies are discussed in general, namely, the series approach, the reformulation of the boundary-value problems for the Laplace's equations as integral boundary equations, and the finite-element approach. In particular, the signatures of the finite-element weak solutions—the computational costs, the convergence, the accuracy—are discussed considering elastic cylinders whose cross sections are represented by piece-wise smooth domains.     

Counting and enumeration complexity with application to multicriteria scheduling

In this paper we tackle an important point of combinatorial optimisation: that of complexity theory when dealing with the counting or enumeration of optimal solutions. Complexity theory has been initially designed for decision problems and evolved over the years, for instance, to tackle particular features in optimisation problems. It has also evolved, more or less recently, towards the complexity of counting and enumeration problems and several complexity classes, which we review in this paper, have emerged in the literature. This kind of problems makes sense, notably, in the case of multicriteria optimisation where the aim is often to enumerate the set of the so-called Pareto optima. In the second part of this paper we review the complexity of multicriteria scheduling problems in the light of the previous complexity results.Received: November 2004 / Received version: March 2005MSC classification: 90B40, 90C29, 68Q15     

Using solution properties within an enumerative search to solve a sports league scheduling problem

This paper presents an enumerative approach for a particular sports league scheduling problem known as “Prob026” in CSPLib. Despite its exponential-time complexity, this simple method can solve all instances involving a number T of teams up to 50 in a reasonable amount of time while the best known tabu search and constraint programming algorithms are limited to T?40 and the direct construction methods available only solve instances where or T/2 is odd. Furthermore, solutions were also found for some T values up to 70. The proposed approach relies on discovering, by observation, interesting properties from solutions of small problem instances and then using these properties in the final algorithm to constraint the search process.     

On a new notion of the solution to an ill-posed problem

A new understanding of the notion of the stable solution to ill-posed problems is proposed. The new notion is more realistic than the old one and better fits the practical computational needs. A method for constructing stable solutions in the new sense is proposed and justified. The basic point is: in the traditional definition of the stable solution to an ill-posed problem Au=f, where A is a linear or nonlinear operator in a Hilbert space H, it is assumed that the noisy data {f_δ,δ} are given, ‖f−f_δ‖≤δ, and a stable solution u_δ:=R_δf_δ is defined by the relation lim_δ→0‖R_δf_δ−y‖=0, where y solves the equation Au=f, i.e., Ay=f. In this definition y and f are unknown. Any f∈B(f_δ,δ) can be the exact data, where B(f_δ,δ):={f:‖f−f_δ‖≤δ}.The new notion of the stable solution excludes the unknown y and f from the definition of the solution. The solution is defined only in terms of the noisy data, noise level, and an a priori information about a compactum to which the solution belongs.