Machine Learning-based heuristics have recently shown impressive performance in solving a variety of hard combinatorial optimization problems (COPs). However they generally rely on a separate neural model, specialized and trained for each single problem. Any variation of a problem requires adjustment of its model and re-training from scratch. In this paper, we propose GOAL (for Generalist combinatorial Optimization Agent Learner), a generalist model capable of efficiently solving multiple COPs and which can be fine-tuned to solve new COPs. GOAL consists of a single backbone plus light-weight problem-specific adapters for input and output processing. The backbone is based on a new form of mixed-attention blocks which allows to handle problems defined on graphs with arbitrary combinations of node, edge and instance-level features. Additionally, problems which involve heterogeneous types of nodes or edges are handled through a novel multi-type transformer architecture, where the attention blocks are duplicated to attend the meaningful combinations of types while relying on the same shared parameters. We train GOAL on a set of routing, scheduling and classic graph problems and show that it is only slightly inferior to the specialized baselines while being the first multi-task model that solves a wide range of COPs. Finally we showcase the strong transfer learning capacity of GOAL by fine-tuning it on several new problems. Our code is available at https://github.com/naver/goal-co .

We consider a large-scale data center where a fleet of heterogeneous mobile robots and human workers collaborate to handle various installation and maintenance tasks. We focus on the underlying multi-agent task assignment problem which is crucial to optimize the overall system. We formalize the problem as a Markov Decision Process and propose an end-to-end learning approach to solve it. We demonstrate the effectiveness of our approach in simulation with realistic data and in the presence of uncertainty.

Despite the success of neural-based combinatorial optimization methods for end-to-end heuristic learning, out-of-distribution generalization remains a challenge. In this paper, we present a novel formulation of Combinatorial Optimization Problems (COPs) as Markov Decision Processes (MDPs) that effectively leverages common symmetries of COPs to improve out-of-distribution robustness. Starting from a direct MDP formulation of a constructive method, we introduce a generic way to reduce the state space, based on Bisimulation Quotienting (BQ) in MDPs. Then, for COPs with a recursive nature, we specialize the bisimulation and show how the reduced state exploits the symmetries of these problems and facilitates MDP solving. Our approach is principled and we prove that an optimal policy for the proposed BQ-MDP actually solves the associated COPs. We illustrate our approach on five classical problems: the Euclidean and Asymmetric Traveling Salesman, Capacitated Vehicle Routing, Orienteering and Knapsack Problems. Furthermore, for each problem, we introduce a simple attention-based policy network for the BQ-MDPs, which we train by imitation of (near) optimal solutions of small instances from a single distribution. We obtain new state-of-the-art results for the five COPs on both synthetic and realistic benchmarks. Notably, in contrast to most existing neural approaches, our learned policies show excellent generalization performance to much larger instances than seen during training, without any additional search procedure. Our code is available at: [link](https://github.com/naver/bq-nco).

Standard autoregressive seq2seq models are easily trained by max-likelihood, but tend to show poor results under small-data conditions.We introduce a class of seq2seq models, GAMs (Global Autoregressive Models), which combine an autoregressive component with a log-linear component, allowing the use of global a priori features to compensate for lack of data.We train these models in two steps.In the first step, we obtain an unnormalized GAM that maximizes the likelihood of the data, but is improper for fast inference or evaluation.In the second step, we use this GAM to train (by distillation) a second autoregressive model that approximates the normalized distribution associated with the GAM, and can be used for fast inference and evaluation.Our experiments focus on language modelling under synthetic conditions and show a strong perplexity reduction of using the second autoregressive model over the standard one.

A first step in the optimisation of the power consumption of a device infrastructure is to detect the power consumption signature of the involved devices. In this paper, we are especially interested in devices which spend most of their time waiting for a job to execute, as is often the case of shared devices in a networked infrastructure, like multi-function printing devices in an office or transaction processing terminals in a public service. We formulate the problem as an instance of power disaggregation in non intrusive load monitoring (NILM), with strong prior assumptions on the sources but with specific constraints: in particular, the aggregation is occlusive rather than additive.We use a specific variant of Hidden Semi Markov Models (HSMM) to build a generative model of the data, and adapt the Expectation-Maximisation (EM) algorithm to that model, in order to learn, from daily operation data, the physical characteristics of the device, separated from those linked to the job load or the device configurations. Finally, we show some experimental results on a multifunction printing device.

On-street parking, just as any publicly owned utility, is used inefficiently if access is free or priced very far from market rates. This paper introduces a novel demand management solution: using data from dedicated occupancy sensors an iteration scheme updates parking rates to better match demand. The new rates encourage parkers to avoid peak hours and peak locations and reduce congestion and underuse. The solution is deliberately simple so that it is easy to understand, easily seen to be fair and leads to parking policies that are easy to remember and act upon. We study the convergence properties of the iteration scheme and prove that it converges to a reasonable distribution for a very large class of models. The algorithm is in use to change parking rates in over 6000 spaces in downtown Los Angeles since June 2012 as part of the LA Express Park project. Initial results are encouraging with a reduction of congestion and underuse, while in more locations rates were decreased than increased.

We propose a supervised machine learning method to automate the classification of events within time series in a monitoring context. It is based on a generative stochastic model of the time series which combines a probabilistic autoregressive classifier to determine the class label of each event, and a hidden Markov model to capture the production of the events. Events can be described by arbitrary combinations of discrete and continuous features. While at training time (offline), it is assumed that the class labels of all the events are known, at inference time (online), when a prediction is to be made for an event, it is not assumed that the class labels of the preceding events are known. This makes prediction more complex due to the autoregressive nature of the model. Instead, we make and exploit a “delayed disclosure” assumption, namely that the class labels of all the events are eventually revealed, but the occurrence of an event and the revelation of its class are asynchronous. We report experimental results obtained by application of this approach to the monitoring of a fleet of distributed devices.

In modern business, educational, and other settings, it is common to provide a digital network that interconnects hardware devices for shared access by the users (e.g., in an office where printers are available for use by all the office workers). In such a context, so-called "soft" failures, where a device silently starts working in degraded mode, may easily go un-noticedfor a long time, resulting in potential productivity loss. It is therefore advantageous to enable system administrators to identify soft failures at an early stage. We propose here a probabilistic method using variational inference on a factorial hidden Markov model to automatically discover soft failures, based on the analysis of simple usage information which is normally logged by the network infrastructure. We propose to mine these logs in order to discover statistically significant deviations in the usage behavior of the overall infrastructure, and we identify such deviations with soft failures, or, in any case, situations of interest to an administrator.

CLF/Mekano is a distributed object infrastructure oriented towards the high-level coordination of coarse grain components. Unlike other infrastructures of the same class, such as CORBA or DCOM, coordination in CLF/Mekano is built-in at the lowest level, namely at the inter-component communication protocol level, and not as a side service (such as the event, transaction or negotiation services of Corba). Although the CLF protocol is "lightweight" (it relies on very few concepts and only 8 communication "verbs"), it makes the design and implementation of components more complex, but also more valuable if it can be reused. The Mekano library has been developed in order to deal with this complexity, targeting reusability. It provides ready-to-use generic classes of customizable components, as well as useful component parts which can be reassembled according to application specific needs. Of course, further layers of domain-specific libraries (so called business object libraries), can then be developed on top of Mekano, to provide ready-to-use components dedicated to specific business needs (in the line of Enterprise Java Beans).

Describes a coordination-based approach to the dynamic evolution of (software) workflow processes. Our interest is in widely distributed workflow processes, i.e. systems that allow each instance of a process model to be enacted in a distributed fashion, with different parts of the process being enacted on different nodes of the system. More specifically, we are interested in the problem of dynamic workflow process evolution in such a distributed context, where the propagation of changes to all the concerned nodes has to be performed in an orderly manner. We address the problem of dynamic workflow process evolution from a coordination system approach, considering the workflow system as a coordination system and the workflow evolution as a coordinated evolution of the coordination schemes. We illustrate the problem of workflow evolution in a software engineering context, and describe a method using the reflexive features of our underlying coordination system to support dynamic workflow process evolution in a distributed workflow system.

Summary form only given. The amount of information available from electronic sources on the World Wide Web and other on-line information repositories is highly heterogeneous and increasing dramatically. Tools are needed to extract relevant information from these repositories. The Constraint-Based Knowledge Brokers project (CBKB) at RXRC Grenoble realizes sophisticated facilities for efficient information retrieval, schema integration, and knowledge fusion. The current implementation of the CBKB research prototype involves three kinds of agents: a) users, who input queries and process answers (i.e., ranking, fusion) through a GUI; b) wrappers, capable of interrogating heterogeneous information sources, which can provide answers to elementary queries (essentially various public bibliographic catalogues available on the Web, as well as preprint archives and opera information repositories); c) brokers, which can manage complex queries (i.e., decompose a complex query, recompose the partial answers, synthesize a full answer) and which mediate between the GUI and the different wrappers. The core of the system is given by the brokers, which provide various important services such as intelligent caching, filtering and knowledge combination. Requests, intermediate information, and results are internally represented via feature constraints. Requests do not need to be fully defined; they may correspond to partial specifications of the requested information.

The deep symmetry of linear logic [18] makes it suitable for providing abstract models of computation, free from implementation details which are, by nature, oriented and non-symmetrical. I propose here one such model, in the area of logic programming, where the basic computational priciple is Computation = Proof search Proofs cinsidered here are those of the Gentzen style sequent calculus for linear logic. However, proofs in this system may be redundant, in that two proofs canbe syntactically different although identical up to some irrelevant reordering or simplification of the applications of the inferences rules. This leads to an untractable proof search where the search procedure is forced to make costly choices whch turn out to be irrelevant. To overcome this problem, a subclass of proofs, called the ‘focusing’ proofs, which is both complete (any derivable formla in linear logic has a focusing proof) and tractable (many irrelevant choices in the search are eliminated when aimed at focusing proofs) is identified. The main constraint underlying the specificatuon of focusing proofs has been to preserve the symmetry of linear logic, which is its most salient feature. In particular, dual connectives have dual properties with respect to focusing proofs Then, a progrmming language, called LinLog, consisting of a fragment of linear logic, in which focussing proofs have a more compact form, is presented. Linlog deals with formulae which have a syntax similar to the of the definite clauses and goals of Horn logic, but the crucial difference here is that it allows clauses with multiple atoms in the head, connected by the ‘par’ (multiplicative disjuction). It is then shown that the syntyactic restriction induced by LinLog is not performed at the cost of any expressive power: a mapping from full linear logic to LinLog, preserving focusing proofs, and analogous to the normalization to clausal form for classical logic, is presented.

Ve introduce an abstract form of interobject communication for object-oriented concurrent programming based on the proof theory of Linear Logic, a logic introduced to provide a theoretical basis for the study of concurrency.Such a form of communication, which we call forumbased communication, can be seen as a refinement of blackboard-based communication in terms of a more local notion of resource consumption.Forumbased communication is introduced as part of a new computational model for the object-oriented concurrent programming language LO, presented at last year OOPSLA/ECOOP (1990), which exploits the proof-theory of Linear Logic also to achieve a powerful form of knowledge-sharing.