In recent years, the home delivery market has rapidly been growing since customers can purchase a variety of products very easily via Internet. At the same time, however, customers tend to switch from a supplier to another seeking for better service for them. For this reason, it is necessary for suppliers to enclose their customers by means of various kinds of service and strategy. An appointed delivery date of a product ordered by a customer is one of important factors of supplier's services. From the suppliers' point of view, they hope to make the period from the order date to the delivery date as short as possible to increase their customers, but at the same time they prefer to make this period as long as possible since the risk becomes higher that they cannot deliver products to their consumer by the appointed date under the short period appointed date. This study proposes a stochastic model to determine an optimal appointed delivery date for a supplier. For small values of an appointed delivery date L, the probability that a customer purchases the product becomes larger, but the probability of tardiness increases. In contrast, the purchase probability as well as the penalty of tardiness decreases with L. From this point of view, this study formulates the expected profit for a supplier, which is to be maximized as an objective function. Clarified are the conditions under which an optimal appointed delivery date exists for the case where the purchase probability is expressed by a multinomial logit model. Numerical examples are also presented.

The paper is designated to the analysis of queueing systems, arising in the network theory and communications theory (called multiphase queueing systems, tandem queues or series of queueing systems). Also we note that multiphase queueing systems can be useful for modelling practical multi-stage service systems in a variety of disciplines, especially on manufacturing (assembly lines), computer networking (packet switch structures), and in telecommunications (e.g. cellular mobile networks), etc. This research presents heavy traffic limit theorems for the cumulative idle time in multiphase queues. In this work, functional limit theorems are proved for the values of important probability characteristics of the queueing system (a cumulative idle time of a customer).

Public inoculation centers are examples of facilities providing service to customers whose demand is elastic to travel and waiting time. That is, people will not travel too far, or stay in line for too long to obtain the service. The goal, when planning such services, is to maximize the demand they attract, by locating centers and staffing them so as to reduce customers' travel time and time spent in queue. In the case of inoculation centers, the goal is to maximize the people that travel to the centers and stay in line until inoculated. We propose a procedure for the allocation of multiple servers to centers, so that this goal is achieved. An integer programming model is formulated. Since demand is elastic, a supply-demand equilibrium equation must be explicitly included in the optimization model, which then becomes nonlinear. As there are no exact procedures to solve such problems, we propose a heuristic procedure, based on Heuristic Concentration, which finds a good solution to this problem. Numerical examples are presented.

In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach — the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O(nlogn)-time algorithm is given, where n is a number of restriction sites.

We describe an interior point algorithm for convex quadratic problem with astrict complementarity constraints. We show that under some assumptions theapproach requires a total of $O(\sqrt{n}L)$ number of iterations, where Lis the input size of the problem. The algorithm generates a sequence of problems, each of which isapproximately solved by Newton's method.

The multiparametric min max 0-1-Integer Programming (0-1-IP) problem relative to the objective function is a family of min max 0-1-IP problems which are related by having identical constraint matrix and right-hand-side vector. In this paper we present an algorithm to perform a completemultiparametric analysis relative to the objective function.

We consider the NP Hard problems of online Bin Covering and Packing whilerequiring that larger (or longer, in the one dimensional case)items be placed at the bottom of the bins, below smaller (orshorter) items — we call such a version, the LIBversion of problems. Bin sizes can be uniform or variable. We lookat computational studies for both the Best Fit and Harmonic Fitalgorithms for uniform sized bin covering. The Best Fit heuristic forthis version of the problem is introduced here. The approximation ratios obtained were well within the theoretical upperbounds. For variable sized bin covering, a more thorough analysis revealeddefinite trends in the maximum and average approximation ratios. Finally, we prove that for online LIB bin packing with uniform sizebins, no heuristic can guarantee an approximation ratio better than1.76 under the online model considered.

Nous présentons dans cet article un algorithme générique hybride permettant de combiner des méthodes complètes (programmation par contraintes) et incomplètes(recherche locale) pour la résolutionde problèmes de satisfaction de contraintes.Ce schéma algorithmique basé sur la gestion de populations, utilise destechniques de propagation de contraintes intégrant également des heuristiques de recherche locale. Les structures utiliséesautorisent une interaction homogène entre les différentes méthodes mises enœuvre et permettent également de bénéficier de leurs atoutsrespectifs. Nous proposons alors diverses stratégies de combinaisons dont nous mettons en avant l'intérêt sur quelques exemples par lebiais d'une implémentation.

Nous modélisons ici plusieurs problèmes de Transport et de Gestion de Flux à l'aide d'un flot entier et d'un multiflot fractionnaire couplés par une contrainte de capacité. Pour le problème ainsi obtenu, nous proposons différents schémas de résolution par relaxation et décomposition, qui induisent la recherche d'un flot auxiliaire dont la partie entière supérieure doit minimiser un certain coût, et qui requièrent la mise en œuvre d'un processus d'agrégation. Nous en déduisons diverses heuristiques que nous testons.


Nous nous intéressons dans ce travail au problème d'approximation d'une matrice donnée par une matrice bistochastique. Des instances de ce problème peuvent apparaître dans différents domaines : en recherche opérationnelle dans un problème d'agrégation de préférence, en calcul de variations et optimisation de forme entre autres. Nous en proposons dans cet article une étude directe via le théorème de projection et une résolution numérique inspirée par la méthode de projections alternées de Boyle-Dykstra.

We consider the Airspace Sectorization Problem (ASP) in which airspacehas to be partitioned into a given number of sectors, each of whichbeing assigned to a team of air traffic controllers. The objective isto minimize the coordination workload between adjacent sectors whilebalancing the total workload of controllers. Many specificconstraints, including both geometrical and aircraft relatedconstraints are taken into account. The problem is solved in aconstraint programming framework. Experimental results show that ourapproach can be used on real life problems.

The existence of solutions to a scalar Minty variational inequality of differential type is usually related to monotonicity property of the primitive function. On the other hand, solutions of the variational inequality are global minimizers for the primitive function.The present paper generalizes these results to vector variational inequalitiesputting the Increasing Along Rays (IAR) property into the center of the discussion. To achieve that infinite elements in the image space Y are introduced.Under quasiconvexity assumptions we show that solutions of generalized variational inequality and of the primitive optimization problem are equivalent.Finally, we discuss the possibility to generalize the scheme of this paper to get further applications in vector optimization.

Le système AutoGraphiX (AGX1 et AGX2) permet,parmi d'autres fonctions, la génération automatique de conjectures enthéorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afind'illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjecturesobtenues par ce système et de la forme $\underline{b}_{n} \, \le \, g\,\oplus \,i \, \le \, \overline{b}_{n}$ où g désigne la maille (ou longueur du plus petit cycle) du graphe G=(V, E), i un autre invariant choisi parmi le nombre de stabilité, le rayon, le diamètre, le degré minimum, moyen ou maximum, $\underline{b}_{n} $ et $ \overline{b}_{n} $ des fonctions de l'ordre n = |V| de G les meilleures possibles, enfin $ \oplus $ correspond à une des opérations +,-,×,/. 48 telles conjectures sont obtenues: les plus simples sont démontréesautomatiquement et les autres à la main. De plus 12 autres conjecturesouvertes et non encore étudiées sont soumises aux lecteurs.

This paper introduces a new method to prune the domains of the variablesin constrained optimization problems where the objective function is defined by a sumy = ∑xi , and where the integer variables x i are subject to difference constraintsof the form xj - xi ≤ c. An important application area where such problems occur is deterministic scheduling with the mean flow time as optimality criteria.This new constraint is also more general than a sum constraint defined on a set of ordered variables. Classical approaches perform a local consistency filtering after each reduction ofthe bound of y. The drawback of these approaches comes from the fact that the constraints are handled independently.We introduce here a global constraint that enables to tackle simultaneously the whole constraint system, and thus, yields a more effective pruningof the domains of the x i when the bounds of y are reduced.An efficient algorithm,derived from Dijkstra's shortest path algorithm, is introduced to achieve interval consistency on this global constraint.

The decision repair algorithm (Jussien and Lhomme, Artificial Intelligence139 (2002) 21–45),which has been designed to solve constraint satisfaction problems (CSP), canbe seen, either (i) as an extension of the classical depth first treesearch algorithm with the introduction of a free choice of the variable towhich to backtrack in case of inconsistency, or (ii) as a localsearch algorithm in the space of the partial consistent variableassignments. or (iii) as a hybridisation between local searchand constraint propagation. Experiments reported in Pralet and Verfailllie (2004) show that some heuristics for the choice of thevariable to which to backtrack behave well on consistent instances andthat other heuristics behave well on inconsistent ones. They show alsothat, despite its a priori incompleteness, decision repair,equipped with some specific heuristics, can solve within a limited timealmost all the consistent and inconsistent randomly generatedinstances over the whole constrainedness spectrum. In this paper, wediscuss the heuristics that could be used by decisionrepair to solve consistent instances, on the one hand, andinconsistent ones, on the other hand. Moreover, we establish thatsome specific heuristics make decision repair complete.