Search

Heuristics are important techniques designed to find quickly good feasible solutions for hard integer programs. Most heuristics depend on a solution of the relaxed linear program. Another approach based on Lagrangian relaxation offers a number of advantages over linear programming, namely it is extremely fast for solving large problems. Wedelin heuristic is such a Lagrangian based heuristic, initially developed to solve airline crew scheduling problems. The performance of this method depends crucially on the choice of its numerous parameters. To adjust them and learn which ones have important influence on whether a solution is found and its quality, we propose to conduct a sensitivity analysis followed by an automatic tuning of the most influential parameters. We have implemented a C++ open-source solver called baryonyx which is a parallel version of a (generalized) Wedelin heuristic. We used the Morris method to find useful continuous parameters. Once found, we fixed other parameters and let a genetic optimization algorithm using derivatives adjust the useful ones in order to get the best solutions for a given time limit and training instance set. Our experimental results done mostly on crew and bus driver scheduling benchmarks tackled as set partitioning problems show the significant improvements obtained by tuning the parameters and the good performances of our approach compared to state-of-the-art exact and inexact integer programming solvers.

International audience; This work deals with the simulation of spatial complex systems resolved with cellular models. We compare two component-based modeling implementations, based on DSDE and Multicomponent formalisms, using a Virtual Laboratory Environment framework (VLE) that is based on the DSDE formalism.

Mixed fruit-vegetable cropping systems (MFVCS) are a promising way of ensuring environmentally sustainable agricultural production systems in response to the challenge of being able to fulfill local market requirements. Indeed, they combine productions and they also make a better use of biodiversity. These agroforestry systems are based on a complex set of interactions modifying the utilization of light, water and nutrients. Thus, designing such a system must optimize the use of these resources, by maximizing positive interactions (facilitation) and minimizing negative ones (competition). To attain these objectives, the system's design has to include the spatial and temporal dimensions of these interactions, taking into account the evolution of above- and belowground interactions over a time horizon. However, a considerable amount of research has been conducted, on the one hand, to prove the interest of agroforestry, and on the other hand to propose models supporting cropping plan and crop rotation decisions, but to our knowledge, no model supports the spatial and temporal allocation of both vegetable crops and trees in agroforestry systems. Therefore, we initially built a first MFVCS prototype using the Weighted Constraint Satisfaction framework but the resolution was limited to small scale systems. In this paper, we explore larger MFVCS models using a solver based on Integer Quadratic Programming. The limits of exact methods in solving the MFVCS problem are presented showing the need for approximation methods able to solve a large scale system with solutions of good quality in reasonable time, which could be used in interactive design with farmers and advisers.

International audience; The observation of a simulation is an important task of the modeling and simulation activity. However, this task is rarely explained in the underlying formalism or simulator. Observation consists to capture the state of the model during the simulation. Observation helps understand the behavior of the studied model and allows improving, analyzing or debugging it. In this paper, we focus on appending an observation mechanism in the Parallel Discrete Event System Specification (PDEVS) formalism with guarantee of the reproducible simulation with or without observation mechanism. This extension to PDEVS allows us to observe models at the end of the simulation or according to a time step. Thus, we define a formal specification of this extension and its abstract simulators algorithms. Finally, we present an implementation in the DEVS framework VLE.

International audience; The observation of a model is a necessary process in the context of modeling and simulation as it offers to modelers the results of their simulations. In this paper, we focus our works on the observation mechanism which is generally not explicit nor clearly specified. This is generally not an issue unless we want to use our model in experimental frames or to avoid the observation mechanism to interfere with the simulation. In this paper, we introduce an extension to the Parallel Discrete Event System Specification (PDEVS) formalism, to observe models in various ways, by event (at each state transition of a model), at the end of the simulation or by a time step.Thus, we define a formal specification of this extension and its abstract simulators algorithms. Finally, we present an implementation in the DEVS framework VLE.

Analysing and designing whole-farm systems can greatly be enhanced by using simulation platforms that support representation of management decision-making processes. Asmanager of a purposive system, a farmer reasons his actions on the basis of a deliberated context-dependent course ofactions setup to integrate biological, managerial and technical constraints specific to the farm and its environment.This paper presents a system-based model of such deliberative decision-making behavior based on the DEVS (Discrete Event System Specification) formalism. The modelingof farmer’s decision-making is addressed using the Belief-Desire-Intention (BDI) agent paradigm that provides a theoreticalframework to articulate respectively the informational, motivational and intentional drivers underlying decisionmaking in an open (dynamic) environment. The functioningof such a management process is illustrated through the example of scheduling and coordinating the technical activities involved in a corn production system.

Time is a crucial variable in planning and often requires special attention since it introduces a specific structure along with additional complexity, especially in the case of decision under uncertainty. In this paper, after reviewing and comparing MDP frameworks designed to deal with temporal problems, we focus on Generalized Semi-Markov Decision Processes (GSMDP) with observable time. We highlight the inherent structure and complexity of these problems and present the differences with classical reinforcement learning problems. Finally, we introduce a new simulation-based reinforcement learning method for solving GSMDP, bringing together results from simulation-based policy iteration, regression techniques and simulation theory. We illustrate our approach on a subway network control example.

Time is a crucial variable in planning and often requires special attention since it introduces a specific structure along with additional complexity, especially in the case of decision under uncertainty. In this paper, after reviewing and comparing MDP frameworks designed to deal with temporal problems, we focus on Generalized Semi-Markov Decision Processes (GSMDP) with observable time. We highlight the inherent structure and complexity of these problems and present the differences with classical reinforcement learning problems. Finally, we introduce a new simulation-based reinforcement learning method for solving GSMDP, bringing together results from simulation-based policy iteration, regression techniques and simulation theory. We illustrate our approach on a subway network control example.