We propose a novel discriminative model for sequence labeling called Bregman conditional random fields (BCRF).Contrary to standard linear-chain conditional random fields, BCRF allows fast parallelizable inference algorithms based on iterative Bregman projections.We show how such models can be learned using Fenchel-Young losses, including extension for learning from partial labels.Experimentally, our approach delivers comparable results to CRF while being faster, and achieves better results in highly constrained settings compared to mean field, another parallelizable alternative.

In this paper, we characterize in several manners the class of contraction perfect graphs which are the perfect graphs that remain perfect after the contraction of any edge set. We define the utter graph u ( G ) which is the graph whose stable sets are in bijection with the co-2-plexes of G , and prove that u ( G ) is perfect if and only if G is contraction perfect. Moreover, we exhibit the strong link between co-2-plexes and induced matchings and discuss its consequences according to known results on these problems. This yields several classes of graphs for which the maximum weighted co-2-plex is solvable in polynomial time. Finally, we show how our results extend to a new class of graphs for which finding a maximum weighted induced matching can be done in polynomial time.

Traffic Engineering (TE) represents one of the most essential tools in modern telecommunication networks. The rapid growth of exchanged traffic has required tackling a known NP-hard problem called the Multi-Commodity Flow problem (MCF). Many studies in the literature have already considered different variants of this problem. In this paper, we propose a new way to use a double Dantzig-Wolfe decomposition formulation to improve the quality of the linear relaxation. We apply our method on the classical multi-commodity flow problem where the throughput acceptance is first maximized and then the routing cost is minimized. We provide a computational experiment and conduct an in-depth analysis of the algorithm based on realistic instances.

Lagrangian Relaxation stands among the most efficient approaches for solving Mixed Integer Linear Programs (MILPs) with difficult constraints. Given any duals for these constraints, called Lagrangian Multipliers (LMs), it returns a bound on the optimal value of the MILP, and Lagrangian methods seek the LMs giving the best such bound. But these methods generally rely on iterative algorithms resembling gradient descent to maximize the concave piecewise linear dual function: the computational burden grows quickly with the number of relaxed constraints. We introduce a deep learning approach that bypasses the descent, effectively amortizing per instance optimization. A probabilistic encoder based on a graph neural network computes, given a MILP instance and its Continuous Relaxation (CR) solution, high-dimensional representations of relaxed constraints, which are turned into LMs by a decoder. We train the encoder and the decoder jointly by directly optimizing the bound obtained from the predicted multipliers. Our method is applicable to any problem with a compact MILP formulation, and to any Lagrangian Relaxation providing a tighter bound than CR. Experiments on two widely known problems, Multi-Commodity Network Design and Generalized Assignment, show that our approach closes up to 85% of the gap between the continuous relaxation and the best Lagrangian bound, and provides a high-quality warm-start for descent-based Lagrangian methods.

In this paper, we propose two exact algorithms based on the computation of the Dijkstra tree to solve the multiple pairs shortest path problem. Traditionally, to solve this kind of problems, algorithms are based on distance matrices. For sparse graphs, the computation of these matrices is too costly. The two approaches that we propose allow tackling this issue by computing a small number of Dijkstra trees. We test our algorithms on telecommunication network instances and random instances, and we discuss the dependence of the obtained results on the structure of sources and destinations of commodities. We also propose an extension of the Bi-Dijkstra algorithm to consider several destinations together.

International audience

We present a new method for the joint task of tagging and non-projective dependency parsing.We demonstrate its usefulness with an application to discontinuous phrase-structure parsing where decoding lexicalized spines and syntactic derivations is performed jointly.The main contributions of this paper are (1) a reduction from joint tagging and non-projective dependency parsing to the Generalized Maximum Spanning Arborescence problem, and (2) a novel decoding algorithm for this problem through Lagrangian relaxation.We evaluate this model and obtain state-of-the-art results despite strong independence assumptions.

Caio Corro, Joseph Le Roux, Mathieu Lacroix, Antoine Rozenknop, Roberto Wolfler Calvo. Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2016.

Given an indirected graph G = (V;E), a Vertex k-Separator is a subset of the vertex set V such that, when the separator is removed from the graph, the remaining vertices can be partitioned into k subsets that are pairwise edge-disconnected. In this paper we focus on the Balanced Vertex k-Separator Problem, i.e., the problem of finding a minimum cardinality separator such that the sizes of the resulting disconnected subsets are balanced. We present a compact Integer Linear Programming formulation for the problem, and present a polyhedral study of the associated polytope. We also present an Exponential-Size formulation, for which we derive a column generation and a branching scheme. Preliminary computational results are reported comparing the performance of the two formulations on a set of benchmark instances.