We introduce the problem of selecting patient-donor pairs in a kidney exchange program to undergo a crossmatch test, and we model this selection problem as a two-stage stochastic integer programming problem. The optimal solutions of this new formulation yield a larger expected number of realized transplants than previous approaches based on internal recourse or subset recourse. We settle the computational complexity of the selection problem by showing that it remains NP-hard even for maximum cycle length equal to two. Furthermore, we investigate to what extent different algorithmic approaches, including one based on Benders decomposition, are able to solve instances of the model. We empirically investigate the computational efficiency of this approach by solving randomly generated instances and study the corresponding running times as a function of maximum cycle length, and of the presence of nondirected donors. Summary of Contribution: This paper deals with an important and very complex issue linked to the optimization of transplant matchings in kidney exchange programs, namely, the inherent uncertainty in the assessment of compatibility between donors and recipients of transplants. Although this issue has previously received some attention in the optimization literature, most attempts to date have focused on applying recourse to solutions selected within restricted spaces. The present paper explicitly formulates the maximization of the expected number of transplants as a two-stage stochastic integer programming problem. The formulation turns out to be computationally difficulty, both from a theoretical and from a numerical perspective. Different algorithmic approaches are proposed and tested experimentally for its solution. The quality of the kidney exchanges produced by these algorithms compares favorably with that of earlier models.

Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete.

Motivated by a fundamental clustering problem arising in several areas (production management, marketing, numerical analysis, etc.), we investigate the facial structure of the polytope whose extreme points are all 0–1 block diagonal matrices. For this polytope, general properties of facet-defining inequalities are investigated and specific families of facets are identified. Various techniques for lifting or combining facet-defining inequalities into new ones are also presented. Throughout the paper, a block diagonal matrix is regarded as the adjacency matrix of a disjoint union of complete bipartite graphs. The presentation and the derivation of the results heavily rely on this graph-theoretic interpretation. © 1997 John Wiley & Sons, Inc. Networks 30: 263–282, 1997

This paper associates a linear programming problem (LP) to any conjunctive normal form $\phi $, and shows that the optimum value $Z(\phi )$ of this LP measures the complexity of the corresponding ${\textit{SAT}}$ (Boolean satisfiability) problem. More precisely, there is an algorithm for ${\textit{SAT}}$ that runs in polynomial time on the class of satisfiability problems satisfying $Z(\phi ) \leqslant 1 + \tfrac{{c\log n}}{n}$ for a fixed constant c, where c is the number of variables. In contrast, for any fixed $\beta < 1$, $SAT$ is still NP complete when restricted to the class of CNFs for which $Z(\phi ) \leqslant 1 + ({1 / {n^\beta }})$.

In this paper a new lower bound for unconstrained quadratic 0 – 1 minimization is investigated. It is shown that this bound can be computed by solving a linear programming problem of polynomial size in the number of variables; and it is shown that the polyhedron ${\text{S}}^{[3]} $, defined by the constraints of this LP formulation is precisely the first Chvátal closure of the polyhedron associated with standard linearization procedures. By rewriting the quadratic minimization problem as a balancing problem in a weighted signed graph, it can be seen that the polyhedron defined by the odd cycle inequalities is equivalent, in a certain sense, with ${\text{S}}^{[3]} $. As a corollary, a compact linear programming formulation is presented for the maximum cut problem for the case of weakly bipartite graphs.

The authors study the complexity and propose an algorithm for the problem of determining, given p vectors of {-1,1}(n), all linear combinations of them which are also in {-1,1}(n). Computational results are reported. This problem corresponds to the detection of spurious states in neural networks.