Search

This article addresses the formulation for implementing a single source, single-destination shortest path algorithm on a quantum annealing computer. Three distinct approaches are presented. In all the three cases, the shortest path problem is formulated as a quadratic unconstrained binary optimization problem amenable to quantum annealing. The first implementation builds on existing quantum annealing solutions to the traveling salesman problem, and requires the anticipated maximum number of vertices on the solution path $|P|$ to be provided as an input. For a graph with $|V|$ vertices, $|E|$ edges, and no self-loops, it encodes the problem instance using $|V||P|$ qubits. The second implementation adapts the linear programming formulation of the shortest path problem, and encodes the problem instance using $|E|$ qubits for directed graphs or $2|E|$ qubits for undirected graphs. The third implementation, designed exclusively for undirected graphs, encodes the problem in $|E| + |V|$ qubits. Scaling factors for penalty terms, complexity of coupling matrix construction, and numerical estimates of the annealing time required to find the shortest path are made explicit in the article.

Linear programming is used to solve optimization problems. Thus, finding a shortest path in a grid is a good target to apply linear programming. In this paper, specific bipartite grids, the square and the body-centered cubic grids are studied. The former is represented as a “diagonal square grid” having points with pairs of either even or pairs of odd coordinates (highlighting the bipartite feature). Therefore, a straightforward generalization of the representation describes the body-centered cubic grid in 3D. We use chamfer paths and chamfer distances in these grids; therefore, weights for the steps between the closest neighbors and steps between the closest same type points are fixed, and depending on the weights, various paths could be the shortest one. The vectors of the various neighbors form a basis if they are independent, and their number is the same as the dimension of the space studied. Depending on the relation of the weights, various bases could give the optimal solution and various steps are used in the shortest paths. This operational research approach determines the optimal paths as basic feasible solutions of a linear programming problem. A directed graph is given containing the feasible bases as nodes and arcs with conditions on the used weights such that the simplex method may step from one feasible basis to another one. Thus, the optimal bases can be determined, and they are summarized in two theorems. If the optimal solution is not integer, then the Gomory cut is applied and the integer optimal solution is reached after only one Gomory iteration. Chamfer distances are frequently used in image processing and analysis as well as graphics-related subjects. The body-centered cubic grid, which is well-known in solid state physics, material science, and crystallography, has various applications in imaging and graphics since less samples are needed to represent the signal in the same quality than on the cubic grid. Moreover, the body-centered cubic grid has also a topological advantage over the cubic grid, namely, the neighbor Voronoi cells always share a full face.

The shortest path problem is formulated as an $l_1$-regularized regression problem, known as lasso. Based on this formulation, a connection is established between Dijkstra's shortest path algorithm and the least angle regression (LARS) for the lasso problem. Specifically, the solution path of the lasso problem, obtained by varying the regularization parameter from infinity to zero (the regularization path), corresponds to shortest path trees that appear in the bi-directional Dijkstra algorithm. Although Dijkstra's algorithm and the LARS formulation provide exact solutions, they become impractical when the size of the graph is exceedingly large. To overcome this issue, the alternating direction method of multipliers (ADMM) is proposed to solve the lasso formulation. The resulting algorithm produces good and fast approximations of the shortest path by sacrificing exactness that may not be absolutely essential in many applications. Numerical experiments are provided to illustrate the performance of the proposed approach., 17 pages

In the transport system, it is necessary to optimize routes to ensure that the distance, the amount of fuel used, and travel times are minimized. A classical problem in network optimization is the shortest path problem (SPP), which is used widely in many optimization problems. However, the uncertainty that exists regarding real network problems makes it difficult to determine the exact arc lengths. In this study, we analyzed the problem of route optimization when delivering urban road network products while using fuzzy logic to include factors which are difficult to consider in classical models (e.g., traffic). Our approach consisted of two phases. In the first phase, we calculated a fuzzy coefficient to consider the uncertainty, and in the second phase, we used fuzzy linear programming to compute the optimal route. This approach was applied to a real network problem (a portion of the distribution area of a delivery company in the city of Tuxtla Gutierrez, Chiapas, Mexico) by comparing the travel times between the proposed model and a classical model. The proposed model was shown to predict travel time better than the classical model in this study, reducing the mean absolute percentage error (MAPE) by 25.60%.

Nowadays, the Internet of Things enabled Underwater Wireless Sensor Network (IoT-UWSN) is suffering from serious performance restrictions, i.e., high End to End (E2E) delay, low energy efficiency, low data reliability, etc. The necessity of efficient, reliable, collision and interference-free communication has become a challenging task for the researchers. However, the minimum Energy Consumption (EC) and low E2E delay increase the performance of the IoT-UWSN. Therefore, in the current work, two proactive routing protocols are presented, namely: Bellman&ndash, Ford Shortest Path-based Routing (BF-SPR-Three) and Energy-efficient Path-based Void hole and Interference-free Routing (EP-VIR-Three). Then we formalized the aforementioned problems to accomplish the reliable data transmission in Underwater Wireless Sensor Network (UWSN). The main objectives of this paper include minimum EC, interference-free transmission, void hole avoidance and high Packet Delivery Ratio (PDR). Furthermore, the algorithms for the proposed routing protocols are presented. Feasible regions using linear programming are also computed for optimal EC and to enhance the network lifespan. Comparative analysis is also performed with state-of-the-art proactive routing protocols. In the end, extensive simulations have been performed to authenticate the performance of the proposed routing protocols. Results and discussion disclose that the proposed routing protocols outperformed the counterparts significantly.

We present two results on slime mold computations. In wet-lab experiments (Nature'00) by Nakagaki et al. the slime mold Physarum polycephalum demonstrated its ability to solve shortest path problems. Biologists proposed a mathematical model, a system of differential equations, for the slime's adaption process (J. Theoretical Biology'07). It was shown that the process convergences to the shortest path (J. Theoretical Biology'12) for all graphs. We show that the dynamics actually converges for a much wider class of problems, namely undirected linear programs with a non-negative cost vector. Combinatorial optimization researchers took the dynamics describing slime behavior as an inspiration for an optimization method and showed that its discretization can $\varepsilon$-approximately solve linear programs with positive cost vector (ITCS'16). Their analysis requires a feasible starting point, a step size depending linearly on $\varepsilon$, and a number of steps with quartic dependence on $\mathrm{opt}/(\varepsilon\Phi)$, where $\Phi$ is the difference between the smallest cost of a non-optimal basic feasible solution and the optimal cost ($\mathrm{opt}$). We give a refined analysis showing that the dynamics initialized with any strongly dominating point converges to the set of optimal solutions. Moreover, we strengthen the convergence rate bounds and prove that the step size is independent of $\varepsilon$, and the number of steps depends logarithmically on $1/\varepsilon$ and quadratically on $\mathrm{opt}/\Phi$.

The paper deals with nonlinear multicommodity flow problems with convex costs. A decomposition method is proposed to solve them. The approach applies a potential reduction algorithm to solve the master problem approximately and a column generation technique to define a sequence of primal linear programming problems. Each subproblem consists of finding a minimum cost flow between an origin and a destination node in an uncapacited network. It is thus formulated as a shortest path problem and solved with Dijkstra's d-heap algorithm. An implementation is described that takes full advantage of the supersparsity of the network in the linear algebra operations. Computational results show the efficiency of this approach on well-known nondifferentiable problems and also large scale randomly generated problems (up to 1000 arcs and 5000 commodities).

In this thesis, we are concerned with multiobjective combinatorial optimization (MOCO) problems. We attempt to fill the gap between theory and practice, which comes from the lack of a deep complexity theory for MOCO problems. In a first part, we consider a complexity notion for multiobjective optimization problems which derives from output-sensitive complexity. The primary goal of such a complexity notion is to classify problems into easy and hard problems. We show that the multiobjective minimum cut problem as well as the multiobjective linear programming problem are easy problems in this complexity theory. We also show that finding extreme points of nondominated sets is an easy problem under certain assumptions. On the side of hard problems, there are obvious ones like the multiobjective traveling salesperson problem. Moreover, we show that the well-known multiobjective shortest path problem is a hard problem. This is also the case for the multiobjective matching and integer min-cost flow problem. We also identify a class of problems for which the biobjective unconstraint combinatorial optimization problem is a barrier for efficient solvability. In a second part, we are again concerned with the gap between theory and practice. This time, we approach the multiobjective shortest path (MOSP) problem from the practical side. For the application in the planning of power transmission lines, we need to have implementations which can cope with large graphs and a larger number of objectives. The results from the first part suggest that exact methods might be incapable of achieving this goal which we also prove empirically. This is why we decide to study the literature on approximation algorithms for the MOSP problem. We conclude that they do not scale well with the number of objectives in general and that there are no practical implementations available. Hence, we develop a novel approximation algorithm in the second part which leans to the exact approaches which are well tested in practice. In an extensive computational study, we show that our implementation of this algorithm performs well even on a larger number of objectives. We compare our implementation to implementations of the other existing approximation algorithms and conclude that our implementation is superior on instances with more than three objectives., Diese Dissertation ist mit der Komplexität von mehrkriteriellen kombinatorischen Optimierungsproblemen (MOCO) befasst. Hierbei wollen wir die Lücke schließen, die sich aus dem Fehlen einer umfassenden Komplexitätstheorie dieser Probleme ergibt. In einem ersten Teil beschreiben wir einen Komplexitätsbegriff für mehrkriterielle Optimierungsprobleme, der sich von ausgabesensitiver Komplexität ableitet. Das Ziel eines Komplexitätsbegriffes ist die Klassifikation von Problemen in einfache und schwierige Probleme. Wir zeigen, dass die Probleme einen Pareto-optimalen Schnitt in einem Graphen zu bestimmen, sowie mehrkriterielle lineare Optimierung einfache Probleme nach dieser Komplexitätstheorie sind. Auch das Problem Extrempunkte von Pareto-Fronten zu bestimmen ist unter bestimmten Bedingungen ein einfaches Problem. Auf der Seite der schwierigen Probleme können wir über die offensichtlichen Probleme wie das mehrkriterielle Handlungsreisendenproblem hinaus auch zeigen, dass das bekannte mehrkriterielle Kürzeste-Wege-Problem ein schwieriges Problem darstellt. Dies gilt ebenso auch für das mehrkriterielle Zuordnungsproblem in allgemeinen Graphen und das mehrkriterielle Flussproblem mit ganzzahligen Flussvariablen. Wir finden in dieser Arbeit außerdem eine Klasse von Problemen, deren effiziente Lösbarkeit von der effizienten Lösbarkeit des bikriteriellen unrestringierten kombinatorischen Optimierungsproblems abhängt. In einem zweiten Teil beschäftigen wir uns wieder mit der Lücke zwischen Theorie und Praxis. Diesmal nähern wir uns dem mehrkriteriellen Kürzeste-Wege-Problem von der praktischen Seite. Für eine Anwendung in der Stromtrassenoptimierung ist es nötig einen Algorithmus zu finden, der sowohl mit großen Graphen, als auch mit mehreren Zielfunktionen umgehen kann. Aus dem ersten Teil können wir ableiten, dass exakte Methoden dort an ihre Grenzen stoßen, was wir auch empirisch belegen. Wir studieren daher Approximationsalgorithmen aus der Literatur und stellen fest, dass sie in der Anzahl der Zielfunktionen nur schlecht skalieren und auch noch nicht praxiserprobt sind. Daher entwickeln wir im zweiten Teil einen neuen Approximationsalgorithmus, der sich stark an die Errungenschaften der praktischen Algorithmen orientiert. Wir zeigen in einem groß angelegten Experiment, dass unsere Implementierung des Algorithmus auch noch auf einer größeren Anzahl von Zielfunktionen praxistauglich ist. Der Vergleich mit unseren Implementierungen der existierenden Approximationsalgorithmen zeigt zudem, dass unsere Implementierung den anderen auf Instanzen mit mehr als drei Zielfunktionen überlegen ist.

Software defined networking (SDN) provides a framework to dynamically adjust and re-program the data plane with the use of flow rules. The realization of highly adaptive SDNs with the ability to respond to changing demands or recover after a network failure in a short period of time, hinges on efficient updates of flow rules. We model the time to deploy a set of flow rules by the update time at the bottleneck switch, and formulate the problem of selecting paths to minimize the deployment time under feasibility constraints as a mixed integer linear program (MILP). To reduce the computation time of determining flow rules, we propose efficient heuristics designed to approximate the minimum-deployment-time solution by relaxing the MILP or selecting the paths sequentially. Through extensive simulations we show that our algorithms outperform current, shortest path-based solutions by reducing the total network configuration time up to 55% while having similar packet loss, in the considered scenarios. We also demonstrate that in a networked environment with a certain fraction of failed links, our algorithms are able to reduce the average time to reestablish disrupted flows by 40%.

The shortest path finding algorithm is used in many problems on graphs and networks. This article will introduce the algorithm to find the shortest path between two vertices on the extended graph. Next, the algorithm finds the shortest path between the pairs of vertices on the extended graph with multiple weights is developed. Then, the shortest path finding algorithms is used to find the maximum flow on the multicommodity multicost extended network is developed in the article[12].

In this paper, we give a new framework for the stochastic shortest path problem in finite state and action spaces. Our framework generalizes both the frameworks proposed by Bertsekas and Tsitsiklis (1991) and by Bertsekas and Yu (2016). We prove that the problem is well-defined and (weakly) polynomial when (i) there is a way to reach the target state from any initial state and (ii) there is no transition cycle of negative costs (a generalization of negative cost cycles). These assumptions generalize the standard assumptions for the deterministic shortest path problem and our framework encapsulates the latter problem (in contrast with prior works). In this new setting, we can show that (a) one can restrict to deterministic and stationary policies, (b) the problem is still (weakly) polynomial through linear programming, (c) Value Iteration and Policy Iteration converge, and (d) we can extend Dijkstra’s algorithm.

We apply a flow-based location model, called Multipath Refueling Location Model (MPRLM), to develop an electric vehicle (EV) public charging infrastructure network for enabling long-haul inter-city EV trips. The model considers multiple deviation paths between every origin-destination (O-D) pairs and relaxes the commonly adopted assumption that travelers only take a shortest path between O-D pairs. This model is a mixed-integer linear program, which is intrinsically difficult to solve. With greedy-adding based heuristics, the MPRLM is applied to optimally deploy EV fast charging stations along major highway corridors in South Carolina. Compared to engineering methods, the optimization model reduces the capital cost of establishing a fast charging network by two thirds. We also explore the interplay between the spatial distributions of cities, vehicle range, and routing deviation tolerance as well as their impacts on the locational strategies.

International audience; This work focuses simultaneously on both the scaffolding and gap filling phases of de nouveau genome assembly. Given a set of contigs and their relationships--overlaps and/or remoteness in terms of distances between them--we propose an optimization-based approach for finding the genome sequence as a longest sequence that is consistent with the given contig and linkage information. Specifically, we define a graph, which we call a contig graph, that encodes information about contigs and overlaps and mate-pair distances between them, and reduce the scaffolding problem to the problem of finding a longest simple path in that graph such that as many as possible mate-pairs distances are satisfied. Since both conditions cannot generally be simultaneously satisfied, our objective function is a linear combination of the path length and penalties for distance mismatches.​​Unlike the shortest path problem with non-negative weights, for which efficient polynomial-time algorithms exist, the longest weighted path problem is NP-hard. We solve this problem by reformulating it as a mixed integer linear program (MILP) and develop a method that exactly solves the resulting program on genomes of up to 165 contigs and up to 6682 binary variables. An advantage of our approach is that the modeling of scaffolding as a longest path problem allows one to solve simultaneously several subtasks specific for this problem like: contig orientation and ordering, repeats, gap filling, and scaffold extension, which in other approaches are targeted as separate problems. We are not aware of previous approaches on scaffolding based on the longest path problem reduction. A drawback of the typically used strategy of constructing a set of disjoint paths, rather than a single path, is that it would require additional steps of gap filling and scaffold extension, involving additional work. Moreover, it would make impossible to find a provably optimal final solution, since, even if each separate problem is implemented optimally, their combination may not be optimal.We tested this model on a set of chloroplast and bacteria genome data and showed that it allows to assemble the complete genome as a single scaffold. Compared to the publicly available scaffolding tools that we have tested, our solution produces assemblies of significantly higher quality.; Ce travail porte particulièrement sur les étapes de scaffolding et de gap-filling lors de l’assemblage de novo d’un génome. Etant donné un ensemble de contigs et leurs relations (chevauchement et/ou éloignement), nous proposons une approche basée sur l’optimisation, quiconsiste à trouver le plus long assemblage possible consistant avec les distances attendues. Nous résolvons ce problème en le formulant sous la forme d’une programme mixte en nombres entiers (MILP). Notre méthode permet de résoudre exactement des instances comptant jusqu’à 6682 variables binaires pour 165 contigs.L’un des avantages de notre modélisation est qu’elle permet de résoudre simultanément différentes sous taches spécifiques à l’assemblage complet d’un génome : déterminer l’orientation de chaque contig, ordonnancer les répétitions, compléter les scaffolds et les étendre en un assemblage unique etc. . . Ce qui constitue d’ordinaire un ensemble de problèmes à traiter séquentiellement. (Nécessitant alors des solutions spécifiques pour chacun d’entre eux). A notre connaissance, aucune autre approche ne propose de réduire le problème de l’assemblage génomique à celui de la recherche du plus long chemin.

This work is dealing with train timetabling problem. In the first chapter, one can find an introduction to network flows which is needed for understanding deeper concepts later on. Namely, basic graph theory definitions are stated as well as core problems like the minimum cost flow and shortest path problem. Furthermore, two equivalent representations of network flows are described, including some useful properties connected to each of them. At the end of the chapter, linear programming and simplex method are introduced into some detail. In the second chapter more complex theory is introduced. At the beginning, multi-commodity flow problem is stated and few solutions approaches are briefly described. Once we settled for one of them, the rest of the chapter is dealing with Lagrangian relaxation and column generation techniques. Since column generation is the main result needed for solving our problem, some finer results, like determining lower and upper bounds, are stated. In the last, third chapter, one can find a model for representing train timetabling problem for a single line network. That model was introduced by Valentina Cacchiani in her Ph.D. thesis. In this work, periodicity of timetable is assumed because it makes computations way quicker, as well as it has some other benefits. At the end, one can find an algorithm based on column generation technique for solving introduced model. That algorithm is based on 6 steps, and after reading this work, one should be able to fully understand each of them. Ovaj rad bavi se problemom rasporeda vožnje u željezničkom prometu. U prvom poglavlju nalazi se uvod u mrežne tokove koji je potreban za razumijevanje naprednijih koncepata. Konkretno, iskazane su osnovne definicije teorije grafova kao i neki temeljni problemi poput problema najjeftinijeg toka i problema najkraćeg puta. Nadalje, opisana su dva ekvivalenta prikaza mrežnih tokova, uključujući neka korisna svojstva za svaki od njih. Na kraju poglavlja, linearno programiranje i simpleks metoda, objašnjeni su na razini razumijevanja. U drugom poglavlju nalazi se naprednija teorija koja se nadovezuje na prvo poglavlje. Na početku poglavlja prikazan je problem više dobara, kao i nekoliko pristupa rješavanju navedenog problema. Nakon što smo se odlučili za jedan od pristupa, ostatak poglavlja bavi se Lagrangeovom relaksacijom i metodom generacije stupaca. Kako je upravo metoda generacije stupaca najvažniji rezultat za rješavanje našega problema, napredniji rezultati vezani uz određivanje donjih i gornjih granica su detaljno objasnjeni. U posljednjem, trećem poglavlju, nalazi se model za prikazivanje problema rasporeda vožnje za mreže s jednom tračnicom. Navedeni model prvi puta je predstavljen u doktorskom radu Valentine Cacchiani. U ovom radu također pretpostavljamo periodičnost rasporeda vožnje kako bismo, između ostalih, ostvarili prednost poput bržeg vremena računanja. Na kraju rada nalazi se algoritam, temeljen na metodi generacije stupaca, za rješavanje predstavljenog modela. Navedeni algoritam sastoji se od 6 koraka, od kojih je svaki detaljno opisan u ovome radu.

Authors are in long term developing e-learning supports for some parts of Operation Research course. The original purpose was to prepare e-learning supports for students of FBE Mendelu, mainly for part-time form students, who have subscribed Economic mathematical methods course (EMM). Considering decreasing number of lessons on part-time form of study (16 hours in a semester, in comparison to 56 hours in full-time form of study), was for part-time form students even more difficult to fulfill exam requirements. As a help for students there was stage by stage prepared several of programs, they allow self-contained practicing of some linear programming methods. Programs did allow to users step-by-step verify their solution, i.e. whether their calculation are in accordance with algorithm described in lectures. Advantage for the students consists in fact, that each mistake (numerical or algorithmic) they were able to uncover, what contributes to increase of self-study effectiveness and from that resulting higher study motivation. Resulting from existing experience, authors decided to request for a new FRVS grant for academic year 2012, focused on e-learning support of selected graph theory problems. Within this project there was developed a tool allowing to make and according to the user needs interactively modify created graphs. On this graph it is possible individually, step by step (in compliance with on lectures presented algorithm) to practice solving of selected graph theory and network analysis problems (e.g. minimal spanning tree, shortest path in a graph, testing for cycles in a graph, critical path method etc.). Project is realized as modular and was realized in Delphi developing tool. Described algorithms are saved in dynamic linked libraries. There for it is very easy to add here new (newly programmed) algorithms. Project results (i.e. project experience obtained from e-learning supports) will be available for all FBE Mendelu members interested in this problematic.

Mixed integer optimal compensation deals with optimization problems with integer- and real-valued control variables to compensate disturbances in dynamic systems. The mixed integer nature of controls could lead to intractability in problems of large dimensions. To address this challenge, we introduce a decomposition method which turns the original n-dimensional optimization problem into n independent scalar problems of lot sizing form. Each of these problems can be viewed as a two-player zero-sum game, which introduces some element of conservatism. Each scalar problem is then reformulated as a shortest path one and solved through linear programming over a receding horizon, a step that mirrors a standard procedure in mixed integer programming. We apply the decomposition method to a mean-field coupled multi-agent system problem, where each agent seeks to compensate a combination of an exogenous signal and the local state average. We discuss a large population mean-field type of approximation and extend our study to opinion dynamics in social networks as a special case of interest.

We present a Markovian decision process (MDP) framework for multihop wireless sensor networks (MHWSNs) to bound the network performance of both energy constrained (EC) networks and energy harvesting (EH) networks, both with and without relay cooperation. The model provides the fundamental performance limit that a MHWSN can theoretically achieve, under the general constraints from medium access control, routing, and energy harvesting. We observe that the analyses for EC and EH networks fall into two branches of MDP theory, which are finite-horizon process and infinite-horizon process, respectively. The performance metrics for EC and EH networks are different. For EC networks, an appropriate metric is the network lifetime; for EH networks, an appropriate metric is, for example, the network throughput. To efficiently solve the models with high dimension, for the EC networks, we propose a novel computational algorithm by taking advantage of the stochastic shortest path structure of the problem; for the EH networks, we propose a dual linear programming based algorithm by considering the sparsity of the transition matrix. Under the unified MDP framework, numerical results demonstrate the advantages of cooperation for the optimal performance, in both EC and EH networks.

Software-defined networks have been proposed as a viable solution to decrease the power consumption of the networking component in data center networks. Still the question remains on which scheduling algorithms are most suited to achieve this goal. We propose 4 different linear programming approaches that schedule requested traffic flows on SDN switches according to different objectives. Depending on pre-defined software quality requirements such as delay and performance, a single variation or a combination of variations can be selected to optimize the power saving and the performance metrics. Our simulation results demonstrate that all our algorithm variations outperform the shortest path scheduling algorithm, our baseline on power savings, less or more strongly depending on the power model chosen. We show that in FatTree networks, where switches can save up to 60% of power in sleeping mode, we can achieve 15% minimum improvement assuming a one-to-one traffic scenario. Two of our algorithm variations privilege performance over power saving and still provide around 45% of the maximum achievable savings.

To solve the persistently multiple object tracking in cluttered environments, this paper presents a novel tracking association approach based on the shortest path faster algorithm. First, the multiple object tracking is formulated as an integer programming problem of the flow network. Then we relax the integer programming to a standard linear programming problem. Therefore, the global optimum can be quickly obtained using the shortest path faster algorithm. The proposed method avoids the difficulties of integer programming, and it has a lower worst-case complexity than competing methods but better robustness and tracking accuracy in complex environments. Simulation results show that the proposed algorithm takes less time than other state-of-the-art methods and can operate in real time.

International audience; Usual periodic scheduling problems deal with precedence constraints having non-negative latencies. This seems a natural way for modelling scheduling problems, since task delays are generally non-negative quantities. However, in some cases, we need to consider edges latencies that do not only model task latencies, but model other precedence constraints. For instance in register optimisation problems devoted to optimising compilation, a generic machine or processor model can allow considering access delays into/from registers. Edge latencies may be then non-positive leading to a difficult scheduling problem in presence of resources constraints. This research result is related to the problem of periodic scheduling with storage requirement optimisation; its aims is to solve the practical problem of register optimisation in optimising compilation. We show that pre-conditioning a data dependence graph (DDG) to satisfy register constraints before periodic scheduling under resources constraints may create circuits with non-positive distances, resulted from the acceptance of non-positive edge latencies. As a compiler construction strategy, it is forbidden to allow the creation of circuits with non-positive distances during the compilation flow, because such DDG circuits do not guarantee the existence of a valid instruction schedule under resource constraints. We study two solutions to avoid the creation of these problematic circuits. A first solution is reactive, it tolerates the creation of non-positive circuit in a first step, and if detected in a further check step, makes a backtrack to eliminate them. A second solution is proactive, it prevents the creation of non-positive circuits in the DDG during the register optimisation process. It is based on shortest path equations which define a necessary and sufficient condition to free any DDG from these problematic circuits. Then we deduce a linear program accordingly. We have implemented our solutions and we present successful experimental results.

International audience; In optimization, it is common to deal with uncertain and inaccurate factors which make it difficult to assign a single value to each parameter in the model. It may be more suitable to assign a set of values to each uncertain parameter. A scenario is defined as a realization of the uncertain parameters. In this context, a robust solution has to be as good as possible on a majority of scenarios and never be too bad. Such characterization admits numerous possible interpretations and therefore gives rise to various approaches of robustness. These approaches differ from each other depending on models used to represent uncertain factors, on methodology used to measure robustness, and finally on analysis and design of solution methods. In this paper, we focus on the application of a recent criterion for the shortest path problem with uncertain arc lengths. We first present two usual uncertainty models: the interval model and the discrete scenario set model. For each model, we then apply a criterion, called bw-robustness (originally proposed by B. Roy) which defines a new measure of robustness. According to each uncertainty model, we propose a formulation in terms of large scale integer linear program. Furthermore, we analyze the theoretical complexity of the resulting problems. Our computational experiments perform on a set of large scale graphs. By observing the results, we can conclude that the approved solvers, e.g. Cplex, are able to solve the mathematical models proposed which are promising for robustness analysis. In the end, we show that our formulations can be applied to the general linear program in which the objective function includes uncertain coefficients.

A methodology for safety verification of continuous and hybrid systems using barrier certificates has been proposed recently. Conditions that must be satisfied by a barrier certificate can be formulated as a convex program, and the feasibility of the program implies system safety in the sense that there is no trajectory starting from a given set of initial states that reaches a given unsafe region. The dual of this problem, i.e., the reachability problem, concerns proving the existence of a trajectory starting from the initial set that reaches another given set. Using insights from the linear programming duality appearing in the discrete shortest path problem, we show in this paper that reachability of continuous systems can also be verified through convex programming. Several convex programs for verifying safety and reachability, as well as other temporal properties such as eventuality, avoidance, and their combinations, are formulated. Some examples are provided to illustrate the application of the proposed methods. Finally, we exploit the convexity of our methods to derive a converse theorem for safety verification using barrier certificates.