In this paper we present a new approach to solve the Minimum Independent Dominating Setproblem in general graphs which is one of the hardest optimization problem. We propose amethod using a clique partition of the graph, partition that can be obtained greedily. Weprovide conditions under which our method has a better complexity than the complexity ofthe previously known algorithms. Based on our theoretical method, we design in the secondpart of this paper an efficient algorithm by including cuts in the search process. We thenexperiment it and show that it is able to solve almost all instances up to 50 vertices inreasonable time and some instances up to several hundreds of vertices. To go further andto treat larger graphs, we analyze a greedy heuristic. We show that it often gives good(sometimes optimal) results in large instances up to 60   000 vertices in less than 20 s.That sort of heuristic is a good approach to get an initial solution for our exact method.We also describe and analyze some of its worst cases.

Usual periodic scheduling problems deal with precedence constraints having non-negativelatencies. This seems a natural way for modelling scheduling problems, since task delaysare generally non-negative quantities. However, in some cases, we need to consider edgeslatencies that do not only model task latencies, but model other precedence constraints.For instance in register optimisation problems devoted to optimising compilation, ageneric machine or processor model can allow considering access delays into/fromregisters. Edge latencies may be then non-positive leading to a difficult schedulingproblem in presence of resources constraints. This research result is related to theproblem of periodic scheduling with storage requirement optimisation; its aims is to solvethe practical problem of register optimisation in optimising compilation. We show thatpre-conditioning a data dependence graph (DDG) to satisfy register constraints beforeperiodic scheduling under resources constraints may create circuits with non-positivedistances, resulted from the acceptance of non-positive edge latencies. As a compilerconstruction strategy, it is forbidden to allow the creation of circuits with non-positivedistances during the compilation flow, because such DDG circuits do not guarantee theexistence of a valid instruction schedule under resource constraints. We study twosolutions to avoid the creation of these problematic circuits. A first solution isreactive, it tolerates the creation of non-positive circuit in a first step, and ifdetected in a further check step, makes a backtrack to eliminate them. A second solutionis proactive, it prevents the creation of non-positive circuits in the DDG during theregister optimisation process. It is based on shortest path equations which define anecessary and sufficient condition to free any DDG from these problematic circuits. Thenwe deduce a linear program accordingly. We have implemented our solutions and we presentsuccessful experimental results.

We consider multistage bidding models where two types of risky assets (shares) are tradedbetween two agents that have different information on the liquidation prices of tradedassets. These prices are random integer variables that are determined by the initialchance move according to a probability distribution p over thetwo-dimensional integer lattice that is known to both players. Player 1 is informed on theprices of both types of shares, but Player 2 is not. The bids may take any integer values.The model of n-stage bidding is reduced to a zero-sum repeated game withlack of information on one side. We show that, if liquidation prices of shares have finitevariances, then the sequence of values of n-step games is bounded. This makes itreasonable to consider the bidding of unlimited duration that is reduced to the infinitegame G∞(p). We give the solutions for thesegames. Optimal strategies of Player 1 generate random walks of transaction prices. Butunlike the case of one-type assets, the symmetry of these random walks is broken at thefinal stages of the game.

In the performance measurement using tools such as data envelopment analysis (DEA), datawithout explicit inputs has attracted considerable attention among researchers. In suchstudies the problem of production planning in the next production season is an importantand interesting subject. Because of the uncertain nature of the future, decision makersneed to provide robust procedures in order to examine alternative courses of action andtheir implications. The purpose of this paper is to develop an approach to productionplanning problem in production processes without explicit inputs that typically appears incentralized decision making environment. Application of the proposed approach isillustrated empirically using a real case.

In this paper, we show that the direct semidefinite programming (SDP) bound for thenonconvex quadratic optimization problem over ℓ1 unit ball(QPL1) is equivalent to the optimal d.c. (difference between convex) bound for thestandard quadratic programming reformulation of QPL1. Then we disprove a conjecture aboutthe tightness of the direct SDP bound. Finally, as an extension of QPL1, we study therelaxation problem of the sparse principal component analysis, denoted by QPL2L1. We showthat the existing direct SDP bound for QPL2L1 is equivalent to the doubly nonnegativerelaxation for variable-splitting reformulation of QPL2L1.

In matricial analysis, the theorem of Eckart and Young provides a best approximation ofan arbitrary matrix by a matrix of rank at most r. In variationalanalysis or optimization, the Moreau envelopes are appropriate ways of approximating orregularizing the rank function. We prove here that we can go forwards and backwardsbetween the two procedures, thereby showing that they carry essentially the sameinformation.

One-fund theorem states that an efficient portfolio in a Mean-Variance (M-V) portfolioselection problem for a set of some risky assets and a riskless asset can be representedby a combination of a unique risky fund (tangency portfolio) and the riskless asset. Inthis paper, we introduce a method for which the tangency portfolio can be produced as acorner portfolio. So, the tangency portfolio can be computed easily and fast by anyalgorithm designed for tracing out the M-V efficient frontier via computing the cornerportfolios. Moreover, we show that how this method can be used for tracing out the M-Vefficient frontier when problem contains a riskless asset in which the borrowing is notallowed.

To model the dynamics of discrete deterministic systems, we extend the Petri netsframework by a priority relation between conflicting transitions, which is encoded byorienting the edges of a transition conflict graph. The aim of this paper is to gain someinsight into the structure of this conflict graph and to characterize a class of suitableorientations by an analysis in the context of hypergraph theory.