We introduce a new barrier function to solve a class ofSemidefinite Optimization Problems (SOP) with bounded variables.That class is motivated by some (SOP) as the minimization of thesum of the first few eigenvalues of symmetric matrices and graphpartitioning problems. We study the primal-dual central pathdefined by the new barrier and we show that this path is analytic,bounded and that all cluster points are optimal solutions of theprimal-dual pair of problems. Then, using some ideas fromsemi-analytic geometry we prove its full convergence. Finally, weintroduce a new proximal point algorithm for that class ofproblems and prove its convergence.

In this paper we present a robust real-time optimization method for the online linear oilblending process. The blending process consists in determining the optimal mix ofcomponents so that the final product satisfies a set of specifications. We examinedifferent sources of uncertainty inherent to the blending process and show how to addressthis uncertainty applying the Robust Optimization techniques. The polytopal structure ofour problem permits a simplified robust approach. Our method is intended to avoidreblending and we measure its performance in terms of the blend quality giveaway andfeedstocks prices. The difference between the nominal and the robust optimal values (theprice of robustness) provides a benchmark for the cost of reblending which is difficult toestimate in practice. This new information can be used to adjust the level of conservatismin the model. We analyze the feasibility of a blend to be produced from a set offeedstocks when the heel of a previous blend is used in the composition of the new blend.Additional critical information for the control system is then produced.

In this paper, we propose an industrial symbiosis network equilibrium model by usingnonlinear complementarity theory. The industrial symbiosis network consists of industrialproducers, industrial consumers, industrial decomposers and demand markets, which imitatesnatural ecosystem by means of exchanging by-products and recycling useful materialsexacted from wastes. The industrial producers and industrial consumers are assumed to beconcerned with maximization of economic profits as well as minimization of emissions. Wedescribe the optimizing behavior, derive optimality conditions of the variousdecision-makers along with respective economic interpretations and establish the nonlinearcomplementarity model in accordance with the industrial symbiosis network equilibriumconditions. Based on the existence proof of the corresponding nonlinear complementaritymodel under reasonable assumptions, two groups of numerical examples are given toillustrate the rationality as well as the effectiveness of the model.

We propose a temporal decomposition approach for the one-machine schedulingproblem with ready times and due dates. A set of feasible schedules ischaracterized by means of constraint-based analysis rules. They permit thedetermination of the feasible locations of each task in a sequence, representedby rank intervals. A decomposition procedure based on comparisons of rankintervals is developed in order to group tasks to be sequenced in theneighbourhood of each other in a feasible solution. Computational results are reported so that the capability of our approach to prepare the problem for a solution computation, achieved either by a human operator or by an automatic solving procedure, can be evaluated.

The present study proposes a theoretical model to test sales velocity for new products introduced in small format retail stores. The model is designed to distinguish fast moving products within a relatively short period. Under the proposed model, the sales of a newly introduced product are monitored for a prespecified period T, e.g., one week, and if the number of items sold over T is equal to a prespecified integer k or more, the product is considered a fast moving product and is carried over to the following sales periods. A slow moving product could be quickly replaced with alternative merchandise in order to make best use of shelf space. The paper first presents definitions of fast and slow moving products, and then a proposed sales test policy based on the model is formulated, where the expected loss is to be minimized with respect to the integer k. Numerical examples based on actual data collected from a convenience store in Japan are also presented to illustrate the theoretical underpinnings of the proposed sales test model.

Dans cet article nous proposons une nouvelleméthode d'initialisation du problème de transportclassique. Cette méthode est basée sur le principe d'uneaffectation seulement si nécessaire. Elle donne de bonsrésultats etsouvent la solution optimale.

We consider a generalized proximal point method (GPPA) forsolving the nonlinear complementarity problem with monotone operators inRn . It differs from the classical proximal point method discussedby Rockafellar for the problem of finding zeroes of monotone operatorsin the use of generalized distances, called φ-divergences,instead of the Euclidean one. These distances play not only aregularization role but also a penalization one, forcing the sequencegenerated by the method to remain in the interior of the feasible set,so that the method behaves like an interior point one. Under appropriateassumptions on the φ-divergence and the monotone operator weprove that the sequence converges if and only if the problem hassolutions, in which case the limit is a solution. If the problem doesnot have solutions, then the sequence is unbounded. We extend previousresults for the proximal point method concerning convex optimizationproblems.

In this paper, open shop scheduling problems with limited machine availabilityare studied. Such a limited availability of machines may appear inmany real-life situations, e.g. as preventive maintenance activities.Three types of jobs are distinguished: non-preemptable,resumable and preemptable. An operation of a resumable job if not completedbefore a non-availability period of a machine may be suspended and continuedwithout additional cost when the machine becomes available.In the paper, results are given for the scheduling problems associated withthe three types of jobs.Forpreemptable jobs polynomial-time algorithms based on the two-phase methodare proposed.

We study networks with positive and negative customers (or Generalized networks of queues and signals) in a random environment. This environment may change the arrival rates, the routing probabilities, the service rates and also the effect of signals. We prove that the steady-state distribution has a product form. This property is obtained as a corollary of a much more general result on multidimensional Markov chains.

Long running software systems are known to experience an aging phenomenon called software aging, one in which the accumulation of errors during the execution of software leads to performance degradation and eventually results in failure. To counteract thisphenomenon a proactive fault management approach, called software rejuvenation, is particularly useful. It essentially involves gracefully terminating an application or a system and restarting it in a clean internal state. In this paper, we reconsider the non-homogeneousMarkovian models for a single-server type of software system with rejuvenation in Garg et al. (1998), and revisit them from the theoretical view point. More precisely, it is assumed in these models that software failures can occur with positive probability during idle periods in transaction systems, but we exclude this unreasonable situation in our refined models.

In this paper, a new schedule generation scheme forresource-constrained project scheduling problems is proposed. Given aproject scheduling problem and a priority rule, a schedule generationscheme determines a single feasible solution by inserting one by oneeach activity, according to their priority, inside a partialschedule. The paper proposes a generation scheme that differs from theclassic ones in the fact that it allows to consider the activities inany order, whether their predecessors have already been scheduled ornot. Moreover, activity insertion is performed so that delaying somealready scheduled activities is allowed. The paper shows that thisstrategy remains polynomial and often gives better results than moreclassic ones. Moreover, it is also interesting in the fact that somepriority rules, which are quite poor when used with classic schedulegeneration schemes, become very competitive with the proposed schedulegeneration scheme.

In this work, we study an optimal control problem dealing with differential inclusion.Without requiring Lipschitz condition of the set valued map, it isvery hard to look for a solution of the control problem. Our aim isto find estimations of the minimal value, (α), of the costfunction of the control problem. For this, we construct anintermediary dual problem leading to a weak duality result, andthen, thanks to additional assumptions of monotonicity of proximalsubdifferential, we give a more precise estimation of (α). Onthe other hand, when the set valued map fulfills the Lipshitzcondition, we prove that the lower semicontinuous (l.s.c.) proximalsupersolutions of the Hamilton-Jacobi-Bellman (HJB) equationcombined with the estimation of (α), lead to a sufficientcondition of optimality for a suspected trajectory. Furthermore, weestablish a strong duality between this optimal control problem anda dual problem involving upper hull of l.s.c. proximalsupersolutions of the HJB equation (respectively with contingentsupersolutions). Finally this strong duality gives rise to necessaryand sufficient conditions of optimality.

A simple idea used in many combinatorial algorithms is the idea ofpivoting. Originally, it comes from the method proposed by Gauss in the19th century for solving systems of linear equations. This method had been extended in1947 by Dantzig for the famous simplex algorithm used for solving linear programs. Fromsince, a pivoting algorithm is a method exploring subsets of a ground set and going fromone subset σ to a new one σ′ by deleting anelement inside σ and adding an element outside σ:σ′ = σ\ { v}  ∪  {u},with v ∈ σ and u ∉ σ.This simple principle combined with other ideas appears to be quite powerful for manyproblems. This present paper is a survey on algorithms in operations research and discretemathematics using pivots. We give also examples where this principle allows not only tocompute but also to prove some theorems in a constructive way. A formalisation isdescribed, mainly based on ideas by Michael J. Todd.

Determining amino acid sequences of protein molecules is one of the most important issues in molecular biology. These sequences determine protein structure and functionality. Unfortunately, direct biochemical methods for reading amino acid sequences can be used for reading short sequences only. This is the reason, which makes peptide assembly algorithms an important complement of these methods. In this paper, a genetic algorithm solving the problem of short amino acid sequence assembly is presented. The algorithm has been tested in computational experiment and compared with an existing tabu search method for the same problem. The results clearly show that the genetic algorithm outperformed the tabu search approach.

This paper aims at describing the way Flow machinery may be used in order to deal with Resource Constrained Project Scheduling Problems (RCPSP). In order to do it, it first introduces the Timed Flow Polyhedron related to a RCPSP instance. Next it states several structural results related to connectivity and to cut management. It keeps on with a description of the way this framework gives rise to a generic Insertion operator, which enables programmers to design greedy and local search algorithms. It ends with numerical experiments.

In this paper we introduce some improvements on an approach that we described elsewherefor solving a modification of the well-known extended rapid transit network designproblem. Firstly, we propose an integer programming model for selecting the stations to beconstructed and the links between them, in such a way that a connected rapid transitnetwork is obtained. Secondly, we consider a linear 0-1 programming model for determininga route of minimum length in the rapid transit network between certain pairs of locations,and present a greedy heuristic procedure which attempts to minimize an estimation of thetotal number of transfers that should be made by the users to arrive at theirdestinations. We also report several computational experiments that show that thisprocedure can significantly reduce the estimated total number of transfers required forthe solutions obtained using our previous approach.

We consider two parallel M/M/1 queues. The server at one of the queuesis subject to intermittent breakdowns. By the theory of dynamic programming, we determine a threshold optimal policy which consists to transfer, when it is necessary, the customers that arrive at the first queue towards the second queue in order to minimize an instantaneous costdepending of the two queue lengths.

A risk measure in a portfolio selection problem is linear programming (LP) solvable, ifit has a linear formulation when the asset returns are represented by discrete randomvariables, i.e., they are defined by their realizations under specifiedscenarios. The efficient frontier corresponding to an LP solvable model is a piecewiselinear curve. In this paper we describe a method which realizes and produces a tangencyportfolio as a by-product during the procedure of tracing out of the efficient frontier ofrisky assets in an LP solvable model, when our portfolio contains some risky assets and ariskless asset, using nonsmooth optimization methods. We show that the test of finding thetangency portfolio can be limited only for two portfolios. Also, we describe that how thismethod can be employed to trace out the efficient frontier corresponding to a portfolioselection problem in the presence of a riskless asset.

In this article we study the realistic network topology of Synchronous Digital Hierarchy(SDH) networks. We describe how providers fulfill customer connectivity requirements. Weshow that SDH Network design reduces to the Non-Disjoint m-Ring-Star Problem (NDRSP). Wefirst show that there is no two-index integer formulation for this problem. We thenpresent a natural 3-index formulation for the NDRSP together with some classes of validinequalities that are used as cutting planes in a Branch-and-Cut approach. We propose apolyhedral study of a polytope associated with this formulation. Finally, we present ourBranch-and-Cut algorithm and give some experimental results on both random and realinstances.