In this paper, we present an Uzawa-based heuristic that is adapted to certain type of stochastic optimal control problems. More precisely, we consider dynamical systems that can be divided into small-scale subsystems linked through a static almost sure coupling constraint at each time step. This type of problem is common in production/portfolio management where subsystems are, for instance, power units, and one has to supply a stochastic power demand at each time step. We outline the framework of our approach and present promising numerical results on a simplified power management problem.

This paper considers large shift scheduling problems with different shiftstart times and lengths, fractionable breaks and work stretch durationrestrictions. Two solution approaches are proposed to solve the problemsover a multiple-day planning horizon. The first approach is based on alocal branching strategy and the second one is based on a temporaldecomposition of the problem. Local branching is veryefficient in finding good feasible solutions when compared to a classicalbranch-and-bound procedure. However, the decomposition approach has theadvantage of yielding feasible solutions in short computing times, even for difficult instances.

Data envelopment analysis (DEA) has been widely used to measure the performance of theoperational units that convert multiple inputs into multiple outputs. In many real worldscenarios, there are systems that have a two-stage network process with shared inputs usedin both stages of productions. In this paper, the problem of evaluating the efficiency ofa set of specialized and interdependent components that make up a large DMU is considered.In these processes the first stage consists of two parallel components which are connectedserially with the process in the second stage. The paper develops a DEA approach formeasuring efficiency of decision processes which can be divided into two stages. Thisapplication of parallel-series production process involves shared resources and the paperdetermines an optimal split of shared resources among two components.

This paper addresses an ongoing experience in the design of an artificial agenttaking decisionsand combining them with the decisions taken by human agents.The context is a serious game research project,aimed at computer-based support for participatory management of protected areas(and more specifically national parks)in order to promote biodiversity conservation and social inclusion.Its objective isto help various stakeholders (e.g., environmentalist, tourism operator)to collectively understand conflict dynamicsandexplore negotiationstrategies for the management of parks.In this paper,after introducing the design of our serious game, named SimParc,we will describe the architecture of the decision making agent playing the role of the park manager.In the game, the park manager makes final decisions based on its own analysisand also on the votes of the stakeholders.It includes two modules:1) individual decision –based on a model of argumentation,which also provides a basis to justify and explain the decision;2) participatory decision –to take into account the preferences/votes from the stakeholders.

In this paper, a batch arrival general bulk service queueing system with interruptedvacation (secondary job) is considered. At a service completion epoch, if the server findsat least ‘a’ customers waiting for service say ξ, heserves a batch of min (ξ, b) customers, whereb ≥ a. On the other hand, if the queue length is atthe most ‘a-1’, the server leaves for a secondary job (vacation) ofrandom length. It is assumed that the secondary job is interrupted abruptly and the serverresumes for primary service, if the queue size reaches ‘a’, during thesecondary job period. On completion of the secondary job, the server remains in the system(dormant period) until the queue length reaches ‘a’. For the proposedmodel, the probability generating function of the steady state queue size distribution atan arbitrary time is obtained. Various performance measures are derived. A cost model forthe queueing system is also developed. To optimize the cost, a numerical illustration isprovided.

A method to infer X-trees (valued trees having X as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2n-3 distance values between the n elements of X, if they fulfill some explicit conditions. This construction is based on the mapping between X-tree and a weighted generalized 2-tree spanning X.

An algebraic and combinatorial approach to the study ofthe Quadratic Assignment Problem produced theoretical results that canbe applied to (meta) heuristics to give them information about theproblem structure, allowing the construction of algorithms. In thispaper those results were applied to inform a Simulated Annealing-typeheuristic (which we called RedInv-SA). Some results from tests withknown literature instances are presented.

The partial inverse minimum cut problem is to minimally modify the capacities of a digraph such that there exists a minimum cut with respect to the new capacities that contains all arcs of a prespecified set. Orlin showed that the problem is strongly NP-hard if the amount of modification is measured by the weighted L 1-norm. We prove that the problem remains hard for the unweighted case and show that theNP-hardness proof of Yang [RAIRO-Oper. Res.35 (2001) 117–126] for this problem with additionalbound constraints is notcorrect.

The minimum cost multiple-source unsplittable flow problem isstudied in this paper. A simple necessary condition to get asolution is proposed. It deals with capacities and demands and canbe seen as a generalization of the well-known semi-metriccondition for continuous multicommdity flows. A cutting planealgorithm is derived using a superadditive approach. Theinequalities considered here are valid for single knapsackconstraints. They are based on nondecreasing superadditivefunctions and can be used to strengthen the relaxation of anyinteger program with knapsack constraints. Some numericalexperiments confirm the efficiency of the inequalities introducedin the paper.

We present a transformation for stochastic matrices and analyze theeffects of using it in stochastic comparison with the strong stochastic(st) order. We show that unless the given stochastic matrix is row diagonallydominant, the transformed matrix provides better st bounds on the steady state probability distribution.

Simple Temporal Networks (STN) allow conjunctions of minimum and maximum distance constraints between pairs of temporal positions to be represented. This paper introduces an extension of STN called Time–dependent STN (TSTN), which covers temporal constraints for which the minimum and maximum distances required between two temporal positions x and y are not necessarily constant but may depend on the assignments of x and y. Such constraints are useful to model problems in which the duration of an activity may depend on its starting time, or problems in which the transition time required between two activities may depend on the time at which the transition is triggered. Properties of the new framework are analyzed, and standard STN solving techniques are extended to TSTN. The contributions are applied to the management of temporal constraints for so-called agile Earth observation satellites.

In this paper we consider the problem of scheduling, on a two-machine flowshop, a set ofunit-time operations subject to time delays with respect to the makespan. This problem isknown to be \hbox{${\cal NP}$}𝒩𝒫-hard in the strong sense. We propose an algorithm basedon a branch and bound enumeration scheme. This algorithm includes the implementation ofnew lower and upper bound procedures, and dominance rules. A computer simulation tomeasure the performance of the algorithm is provided for a wide range of testproblems.

We present a Branch-and-Cut algorithm where the volume algorithm is applied instead of the traditionally used dual simplex algorithm to the linear programming relaxations in the root node of the search tree. This means that we use fast approximate solutions to these linear programs instead of exact but slower solutions. We present computational results with the Steiner tree and Max-Cut problems. We show evidence that one can solve these problems much faster with the volume algorithm based Branch-and-Cut code than with a dual simplex based one. We discuss when the volume based approach might be more efficient than the simplex based approach.

We present a review of the main “global optimization" methods. The paper comprises one introduction and two parts. In the introduction, we recall some generalities about non linear constraint-less optimization and we list some classifications which have been proposed for the global optimization methods. We then describe, in the first part, various “classical" global optimization methods, most of which available long before the appearance of Simulated Annealing (a key event in this field). There exists plenty of papers and books dealing with these methods, and studying in particular their convergence properties. The second part of the paper is devoted to more recent or atypical methods, mostly issued from combinatorial optimization. The three main methods are “metaheuristics": Simulated Annealing (and derived techniques), Tabu Search and Genetic Algorithms; we also describe three other less known methods. For these methods, theoretical studies of convergence are less abundant in the literature, and the use of convergence results is by far more limited in practice. However, the fitting of some of these techniques to continuous variables problems gave very promising results; that question is not discussed in detail in the paper, but useful references allowing to deepen the subject are given.

Application tools for the crop allocation problem (CAP) are required for agricultural advisors to design more efficient farming systems. Despite the extensive treatment of this issue by agronomists in the past, few methods tackle the crop allocation problem considering both the spatial and the temporal aspects of the CAP. In this paper, we precisely propose an original formulation addressing the crop allocation planning problem while taking farmers’ management choices into account. These choices are naturally represented by hard and soft constraints in the Weighted CSP formalism. We illustrate our proposition by solving a medium–size virtual farm using either a WCSP solver (toulbar2) or an ILP solver (NumberJack/SCIP). This preliminary work foreshadows the development of a decision–aid tool for supporting farmers in their crop allocation strategies.

In this paper, a graph partitioning problem that arises in the design ofSONET/SDH networks is defined and formalized. Approximation algorithms withperformance guarantees are presented. To solve this problem efficiently inpractice, fast greedy algorithms and a tabu-search method are proposed andanalyzed by means of an experimental study.

We consider a Markov decision process for an MX/M/1 queue that iscontrolled by batches of negative customers. More specifically, we deriveconditions that imply threshold-type optimal policies, under either thetotal discounted cost criterion or the average cost criterion. Theperformance analysis of the model when it operates under a giventhreshold-type policy is also studied. We prove a stability condition and acomplete stochastic comparison characterization for models operating underdifferent thresholds. Exact and asymptotic results concerning thecomputation of the stationary distribution of the model are also derived.

The purpose of this paper is to demonstrate that, for globally minimize one dimensional nonconvex problems withboth twice differentiable function and constraint, we can propose an efficientalgorithm based on Branch and Bound techniques. The method is firstdisplayed in the simple case with an interval constraint. The extension is displayedafterwards to the general case with an additional nonconvex twicedifferentiable constraint. A quadratic bounding function which is betterthan the well known linear underestimator is proposed while w-subdivision is added to support the branching procedure. Computational results on several andvarious types of functions show the efficiency of our algorithms and theirsuperiority with respect to the existing methods.

We give a new formulation for the problem of task scheduling intounrelated processors under precedence constraints. This formulation has a polynomial number of variables and does not require that theprocessing times be integer valued.

The problem of minimizing the maximum edge congestion in a multicastcommunication network generalizes the well-known NP-hard multicommodityflow problem. We give the presently best theoretical approximation results aswell as efficient implementations. In particular we show that for a networkwith m edges and k multicast requests, anr(1 + ε)(rOPT + exp(1)lnm)-approximation can be computed inO(kmε-2 lnklnm) time, where β bounds the time forcomputing an r-approximate minimum Steiner tree. Moreover, we present a newfast heuristic that outperforms the primal-dual approaches with respect toboth running time and objective value.