In this paper we propose a primal-dual interior-point algorithm forconvex quadratic semidefinite optimization problem. The searchdirection of algorithm is defined in terms of a matrix function andthe iteration is generated by full-Newton step. Furthermore, wederive the iteration bound for the algorithm with small-updatemethod, namely, O( $\sqrt{n}$ log $\frac{n}{\varepsilon}$ ), which isbest-known bound so far.

This paper analyzes adiscrete-time multi-server queue in which service capacity of eachserver is a minimum of one and a maximum of b customers. Theinterarrival- and service-times are assumed to be independent andgeometrically distributed. The queue is analyzed under theassumptions of early arrival system and late arrival system withdelayed access. Besides, obtaining state probabilities atarbitrary and outside observer's observation epochs, someperformance measures and waiting-time distribution in the queuehave also been discussed. Finally, it is shown that in limitingcase the results obtained in thispaper tend to the continuous-time counterpart.

The minimum cost network flow problem, (MCNFP) constitutes a wide category of networkflow problems. Recently a new dual network exterior point simplex algorithm (DNEPSA) forthe MCNFP has been developed. This algorithm belongs to a special “exterior point simplextype” category. Similar to the classical dual network simplex algorithm (DNSA), thisalgorithm starts with a dual feasible tree-solution and after a number of iterations, itproduces a solution that is both primal and dual feasible, i.e. it isoptimal. However, contrary to the DNSA, the new algorithm does not always maintain a dualfeasible solution. Instead, it produces tree-solutions that can be infeasible for the dualproblem and at the same time infeasible for the primal problem. In this paper, we presentfor the first time, the mathematical proof of correctness of DNEPSA, a detailedcomparative computational study of DNEPSA and DNSA on sparse and dense random probleminstances, a statistical analysis of the experimental results, and finally some newresults on the empirical complexity of DNEPSA. The analysis proves the superiority ofDNEPSA compared to DNSA in terms of cpu time and iterations.

The computation of leastcore and prenucleolus is an efficient way ofallocating a common resource among n players. It has, however,the drawback being a linear programming problem with2n - 2 constraints. In this paper we showhow, in the case of convex production games, generate constraints by solving small sizelinear programming problems,with both continuous and integer variables. The approach is extended to games with symmetries (identical players), and to games with partially continuous coalitions. We also study thecomputation of prenucleolus, and display encouraging numerical results.

We describe the solution of a bound constrained convex quadratic problem with limited memory resources. The problem arises from physical simulations occurring within video games. The motivating problem is outlined, along with a simple interior point approach for its solution. Various linear algebra issues arising in the implementation are explored, including preconditioning, ordering and a number of ways of solving an equivalent augmented system. Alternative approaches are briefly surveyed, and some recommendations for solving these types of problems are given.

In the last decade, the authorities require the use of safe, comfortable vehicles to assure a door to door aspect with respect of environment in the urban context. In this paper, we propose an advanced approach of transport regulation where we integrate cybercars into a regulation process as an alternative in disruption cases. For that, we propose an ITS architecture including public transportation and cybercars into the same framework. We will show that collaboration between these two systems provides better results than managing them separably.

In this work we propose a ranking procedure. This procedure uses an ordinal information about the criterion weights and a non-cardinal or mixed information for the potential actions evaluation. The advantage of this procedure is that it uses the linear programming software packages to compute the intervals of relative proximities from where the rankings are obtained.

In this paper, a single server finite buffer Markovian queuing system is analyzed with the additional restriction that customers may balk as well as renege. Reneging considered in literature is usually of position independent type where the reneging rate is constant irrespective of the position of the customer in the system. However there are many real world situations where this assumption does not hold. This paper is an attempt to model balking with position dependent reneging. Explicit closed form expressions of a number of performance measures are presented. A typical problem is discussed to demonstrate the usefulness of results derived in the paper.

In applications such as airport operations, militarysimulations, and medical simulations, conductingsimulations in accurate and realistic settings that are represented byreal video imaging sequences becomes essential. This paper surveys recent work that enablesvisually realistic model constructions and the simulation of syntheticobjects which are inserted in video sequences, and illustrates how synthetic objects canconduct intelligent behavior within a visual augmented reality.

This paper derives a good approach to approximating the expected inventory level per unit time for the continuousreview (Q, r) perishable inventory system. Three existing approximation approaches are examined and compared with the proposed approach. Three stockout cases, including the full backorder, the partial backorder, and the full lost sales cases, which customers or material users generally use to respond to a stockout condition are considered.This study reveals the fact that the proposed approximationis simple yet good and suitable for incorporation into the (Q, r)perishable inventory model to determine the best ordering policy.The results from numerical examples and a sensitivity analysisindicate that severe underestimation or overestimation of the expected inventory level per unit time due to the use of an inappropriate approximation approach would result in great distortion in the determination of the best ordering policy.

This paper analyses an M/G/1 retrial queue with working vacation and constant retrial policy. As soon as the system becomes empty, the server begins a working vacation. The server works with different service rates rather than completely stopping service during a vacation. We construct the mathematical model and derive the steady-state queue distribution of number of customer in the retrial group. The effects of various performance measures are derived.

The line balancing problem consits in assigning tasks to stations in orderto respect precedence constraints and cycle time constraints. In thispaper, the cycle time is fixed and the objective is to minimize the numberof stations. We propose to use metaheuristics based on simulated annealingby exploiting the link between the line balancing problem and the binpacking problem. The principle of the method lies in the combinationbetween a metaheuristic and a bin packing heuristic. Two representationsof a solution and two neighboring systems are proposed and the methods arecompared with results from the literature. They are better or similar totabu search based algorithm.


In this paper we consider the problem of scheduling precedence task graphs inparallel processing where there can be disturbances in computation andcommunication times. Such a phenomenon often occurs in practice, due to ourinability to exactly predict the time because of system intrusion like cache miss and packet transmission time in mediums like ethernet etc. We propose a method based on the addition of some extra edges to protect the initial scheduling from performing badly due to such changes and provide an upper bound on theperformance guarantee for the scheduling algorithms. Moreover, this construction guarantees a result at least as goodas the result obtained for the initial static scheduling.We also show that this construction is a minimal set in context of partially on-line scheduling.

Proximal Point Methods (PPM) can be traced to the pioneer works of Moreau [16], Martinet [14,15] and Rockafellar [19, 20] who used as regularization function the square of the Euclideannorm. In this work, we study PPM in the context of optimization and we derive a class of suchmethods which contains Rockafellar's result. We also present a less stringent criterion to theacceptance of an approximate solution to the subproblems that arise in the inner loops of PPM.Moreover, we introduce a new family of augmented Lagrangian methods for convex constrainedoptimization, that generalizes the PE+ class presented in [2].

We show in this paper that timed Petri nets, with one resource shared by all the transitions, are directly connected tothe modelling of integer linear programs (ILP). To an ILP can be automatically associated an equivalent Petri net. Theoptimal reachability delay is an optimal solution of the ILP. We show next that a net can model any ILP. I order to dothis, we give a new sufficient reachability condition for the marking equation, which also holds for general Petri netswithout timed transitions.

Information quality is crucial to any information fusion system as combining unreliable or partially credible pieces of information may lead to erroneous results. In this paper, Dempster-Shafer theory of evidence is being used as a framework for representing and combining uncertain pieces of information. We propose a method of dynamic estimation of evidence discounting rates based on the credibility of pieces of information. The credibility of a piece of information Cre(I n ) is evaluated through a measure of consensus (corroboration degree) between a set of belief functions, and this measure serves as a basis for quantifying the credibility of the source (sensor or fusion node) itself, Cre(S k ), used then as a discounting factor for all further belief functions provided by S k . The process is dynamic in the sense that the credibility of the source is revisited in the light of new incoming piece of information. The method proposed relies on a hybrid fusion topology in which the sensors are grouped according to the feature they measure (similar and dissimilar sensors), allowing to select different kinds of measure for estimating the corroboration degrees. Through simulations, we compare (a) the hybrid-combination using the source credibility and the robust combination rule (RCR-L) accounting automatically for sensors's credibility; (b) the hybrid-combination, with different membership degrees and corroboration degrees used to estimate the sources credibility. We show that the new hybrid topology together with the credibility-based evidence discounting estimation algorithm provide a faster identification of the observed object.

We consider a G-network with Poisson flow of positive customers.Each positive customer entering the network is characterized bya set of stochastic parameters: customer route, the length of customer route,customer volume and his service length at each route stage aswell. The following node types are considered:Negative customers arriving at each node also form a Poisson flow.A negative customer entering a node with k customers in service, withprobability 1/k chooses one of served positivecustomer as a “target”. Then, if the node is of a type 0the negative customer immediately “kills” (displaces from the network)the target customer, and if the node is of types 1–3the negative customer with given probability depending on parameters of thetarget customer route kills this customer and with complementary probability hequits the network with no service.A product form for the stationary probabilities of underlyingMarkov process is obtained.

The solution of a variety of classes of globaloptimisation problemsis required in theimplementation of a framework for sensitivity analysis in multicriteria decision analysis. These problems have linear constraints, some of which have a particularstructure, anda variety of objective functions, which may be smooth or non-smooth. Thecontext in which theyarise implies a need for a single, robust solution method.The literature contains few experimental results relevant to such aneed.We report on our experience with the implementation of threestochastic algorithms for global optimisation: the multi-level singlelinkage algorithm,the topographical algorithm and the simulated annealing algorithm.Issues relating to their implementation and use to solve practicalproblems are discussed. Computational results suggest that, for the class of problems considered, simulated annealing performs well.

We study an uncapacitated facility location model where customers are served byfacilities of level one, then each level one facility that is opened must be assigned toan opened facility of level two. We identify a polynomially solvable case, and study somevalid inequalities and facets of the associated polytope.

We address the problem of simultaneous localization and mapping (SLAM) by combining visual loop-closure detection with metrical information given by a robot odometry. The proposed algorithm extends a purely appearance-based loop-closure detection method based on bags of visual words [A. Angeli, D. Filliat, S. Doncieux and J.-A. Meyer, IEEE Transactions On Robotics, Special Issue on Visual SLAM 24 (2008) 1027–1037], which is able to detect when the robot has returned back to a previously visited place. An efficient optimization algorithm is used to integrate odometry information and to generate a consistent topo-metrical map much more usable for global localization and path planning. The resulting algorithm which only requires a monocular camera and robot odometry data, is real-time, incremental (i.e. it does not require any a priori information on the environment), and can be easily embedded on medium platforms.