The Logical Credal Network or LCN is a recent probabilistic logic designed for effective aggregation and reasoning over multiple sources of imprecise knowledge. An LCN specifies a set of probability distributions over all interpretations of a set of logical formulas for which marginal and conditional probability bounds on their truth values are known. Inference in LCNs involves the exact solution of a non-convex non-linear program defined over an exponentially large number of non-negative real valued variables and, therefore, is limited to relatively small problems. In this paper, we present ARIEL -- a novel iterative message-passing scheme for approximate inference in LCNs. Inspired by classical belief propagation for graphical models, our method propagates messages that involve solving considerably smaller local non-linear programs. Experiments on several classes of LCNs demonstrate clearly that ARIEL yields high quality solutions compared with exact inference and scales to much larger problems than previously considered.

We introduce Logical Credal Networks (or LCNs for short) -- an expressive probabilistic logic that generalizes prior formalisms that combine logic and probability. Given imprecise information represented by probability bounds and conditional probability bounds on logic formulas, an LCN specifies a set of probability distributions over all its interpretations. Our approach allows propositional and first-order logic formulas with few restrictions, e.g., without requiring acyclicity. We also define a generalized Markov condition that allows us to identify implicit independence relations between atomic formulas. We evaluate our method on benchmark problems such as random networks, Mastermind games with uncertainty and credit card fraud detection. Our results show that the LCN outperforms existing approaches; its advantage lies in aggregating multiple sources of imprecise information.

We study the classical linear programing relaxation of the ‐median problem, together with the so‐called “odd directed cycle inequalities.” We characterize in terms of forbidden subgraphs, the oriented graphs for which this system of inequalities defines an integral polytope. This completes the study started in Baïou and Barahona (2016), where oriented graphs with no triangles were treated.

We study the maximum node-weighted induced bipartite subgraph problem in planar graphs with maximum degree three. We show that this is polynomially solvable. It was shown in Choi, Nakajima, and Rim [SIAM J. Discrete Math., 2 (1989), pp. 38--47] that it is NP-complete if the maximum degree is four. We extend these ideas to the problem of balancing signed graphs. We also consider maximum weighted induced acyclic subgraphs of planar directed graphs. If the maximum degree is three, it is easily shown that this is polynomially solvable. We show that for planar graphs with maximum degree four the same problem is NP-complete.

We study a prize-collecting version of the uncapacitated facility location problem and of the p-median problem. We say that the uncapacitated facility location polytope has the intersection property if adding the extra equation that fixes the number of opened facilities does not create any fractional extreme point. We characterize the graphs for which this polytope has the intersection property and give a complete description of the polytope for this class of graphs. This characterization yields a polynomial time cutting plane algorithm for these graphs. We also give a combinatorial polynomial time algorithm to solve the different variants of the p-median and facility location problems studied in this paper.

We study a system of linear inequalities associated with some facility location problems. We show that this system defines a polytope with integer extreme points if and only if the graph does not contain a certain type of odd cycles. We also derive odd cycle inequalities and give a separation algorithm.

Abstract Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. Frederickson and Solis‐Oba gave an algorithm for the case when the costs are linear. We give a different derivation of their algorithm, and we slightly extend it to deal with convex piecewise linear costs. We formulate the problem as a combinatorial linear program and show how to produce primal and dual solutions. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Given a graph with nonnegative capacities on its edges, it is well known that the capacity of a minimum T-cut is equal to the value of a maximum fractional packing of T-joins. The Padberg--Rao algorithm finds a minimum capacity T-cut, but it does not produce a T-join packing. We present a polynomial combinatorial algorithm for finding an optimal T-join packing.

Given a directed graph D that has a two-vertex cut, this paper describes a technique to derive a linear system that defines the acyclic subgraph polytope of D from systems related to the pieces. It also gives a technique to describe facets of this polytope by composition of facets for the pieces. The authors prove that, if the systems for the pieces are totally dual integral (TDI), then the system for D is also. The authors prove that the “cycle inequalities” form a TDI system for any orientation of $K_5$. These results are combined with Lucchesi–Younger theorem and a theorem of Wagner to prove that, for graphs with no $K_{3,3} $ minor, the cycle inequalities characterize the acyclic subgraph polytope and form a TDI system. This shows that, for this class of graphs, the cardinality of a minimum feedback set is equal to the maximum number of arc disjoint cycles. For planar graphs, this is a consequence of the Lucchesi–Younger theorem.

Let $P( G )$ be the balanced induced subgraph polytope of G. If G has a two-node cutset, then G decomposes into $G_1 $ and $G_2$. It is shown that $P( G )$ can be obtained as a projection of a polytope defined by a system of inequalities that decomposes into two pieces associated with $G_1 $ and $G_2$. The problem max $cx,x \in P( G )$ is decomposed in the same way. This is applied to series-parallel graphs to show that, in this case, $P( G )$ is a projection of a polytope defined by a system with $O( n )$ inequalities and $O( n )$ variables, where n is the number of nodes in G. Also for this class of graphs, an algorithm is given that finds a maximum weighted balanced induced subgraph in $O( n\log n )$ time. This approach is also used to obtain composition of facets of $P( G )$. Analogous results are presented for acyclic induced subgraphs.

A graph G with a two-node cutset decomposes into two pieces. A technique to describe the stable set polytope for G based on stable set polytopes associated with the pieces is studied. This gives a way to characterize this polytope for classes of graphs that can be recursively decomposed. This also gives a procedure to describe new facets of this polytope. A compact system for the stable set problem in series-parallel graphs is derived. This technique is also applied to characterize facet-defining inequalities for graphs with no $K_5 \backslash e$ minor. The stable set problem is polynomially solvable for this class of graphs. Compositions of h-perfect graphs are also studied.

The authors characterize the stable set polytope for graphs that do not have a 4-wheel as a minor. The authors prove that the nontrivial facets are either “edge” inequalities or can be obtained by composing “odd cycles” and “subdivisions of $K_4 $.” By adding some extra variables, it is shown that the stable set problem for these graphs can be formulated as a linear program of polynomial size.

In 1974 Weintraub [Management Sci., 21 (1974), pp. 87–97] published an algorithm for the minimum-cost circulation problems with convex cost function. In this note Weintraub’s algorithm is considered when applied to a minimum-cost circulation problem with linear objective function. It is shown that a minor variation of the algorithm runs in polynomial time. The resulting algorithm, although it is not strongly polynomial, does not rely on scaling. It is a generalization of the maximum flow algorithm due to Edmonds and Karp [J. Assoc. Comput. Mach., 19 (1972), pp. 248–264] that augments along the fattest augmenting path in the residual graph. The algorithm described here is slower than the fastest minimum-cost circulation algorithms known. The authors’ interest in the algorithm is partially historical, a scaling free “almost polynomial time” algorithm was published in 1974, and partially due to the different ideas involved.