References of "Boros, Endre"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailQuadratic reformulations of nonlinear binary optimization problems
Anthony, Martin; Boros, Endre; Crama, Yves ULiege et al

in Mathematical Programming (2017), 162

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these ... [more ▼]

Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables. In this paper we initiate a systematic study of these quadratization approaches. We provide tight lower and upper bounds on the number of auxiliary variables needed in the worst-case for general objective functions, for bounded-degree functions, and for a restricted class of quadratizations. Our upper bounds are constructive, thus yielding new quadratization procedures. Finally, we completely characterize all ``minimal'' quadratizations of negative monomials. [less ▲]

Detailed reference viewed: 137 (16 ULiège)
Full Text
Peer Reviewed
See detailQuadratization of symmetric pseudo-Boolean functions
Anthony, Martin; Boros, Endre; Crama, Yves ULiege et al

in Discrete Applied Mathematics (2016), 203

A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to ${\bbr}$. For a pseudo-Boolean function $f(x)$ on $\{0,1 ... [more ▼]

A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,\ldots,x_n)$ of $n$ binary variables; that is, a mapping from $\{0,1\}^n$ to ${\bbr}$. For a pseudo-Boolean function $f(x)$ on $\{0,1\}^n$, we say that $g(x,y)$ is a quadratization of $f$ if $g(x,y)$ is a Quadratic polynomial depending on $x$ and on $m$ auxiliary binary variables $y_1,y_2,\ldots,y_m$ such that $f(x)= \min \{ g(x,y) : y \in \{0,1\}^m \} $ for all $x \in \{0,1\}^n$. By means of quadratizations, minimization of $f$ is reduced to minimization (over its extended set of variables) of the quadratic function $g(x,y)$. This is of some practical interest because minimization of quadratic functions has been thoroughly studied for the last few decades, and much progress has been made in solving such problems exactly or heuristically. A related paper initiated a systematic study of the minimum number of auxiliary $y$-variables required in a quadratization of an arbitrary function $f$ (a natural question, since the complexity of minimizing the quadratic function $g(x,y)$ depends, among other factors, on the number of binary variables). In this paper, we determine more precisely the number of auxiliary variables required by quadratizations of \emph{symmetric} pseudo-Boolean functions $f(x)$, those functions whose value depends only on the Hamming weight of the input $x$ (the number of variables equal to 1). [less ▲]

Detailed reference viewed: 87 (13 ULiège)
See detailQuadratization of pseudo-Boolean functions
Crama, Yves ULiege; Anthony, Martin; Boros, Endre et al

Conference (2015, July)

Detailed reference viewed: 156 (1 ULiège)
Full Text
See detailThe Mathematics of Peter L. Hammer (1936-2006): Graphs, Optimization, and Boolean Models
Boros, Endre; Crama, Yves ULiege; De Werra, Dominique et al

in Boros, Endre; Crama, Yves; De Werra, Dominique (Eds.) et al The Mathematics of Peter L. Hammer (1936-2006): Graphs, Optimization, and Boolean Models (2011)

This volume of the Annals of Operations Research, contains a collection of papers published in memory of Peter L. Hammer. As we recall further down, Peter made substantial contributions to several areas ... [more ▼]

This volume of the Annals of Operations Research, contains a collection of papers published in memory of Peter L. Hammer. As we recall further down, Peter made substantial contributions to several areas of operations research and discretemathematics, including, in particular, mathematical programming (linear and quadratic 0–1 programming, pseudo-Boolean optimization, knapsack problems, etc.), combinatorial optimization (transportation problems, network flows, MAXSAT, simple plant location, etc.), graph theory (special classes of graphs, stability problems, and their applications), data mining and classification (Logical Analysis of Data), and, last but not least, Boolean theory (satisfiability, duality, Horn functions, threshold functions, and their applications). [less ▲]

Detailed reference viewed: 42 (3 ULiège)
Full Text
Peer Reviewed
See detailThe Mathematics of Peter L. Hammer (1936-2006): Graphs, Optimization, and Boolean Models
Boros, Endre; Crama, Yves ULiege; de Werra, Dominique et al

in Annals of Operations Research (2011), 188

This volume contains a collection of papers published in memory of Peter L. Hammer (1936-2006). Peter Hammer made substantial contributions to several areas of operations research and discrete mathematics ... [more ▼]

This volume contains a collection of papers published in memory of Peter L. Hammer (1936-2006). Peter Hammer made substantial contributions to several areas of operations research and discrete mathematics, including, in particular, mathematical programming (linear and quadratic 0--1 programming, pseudo-Boolean optimization, knapsack problems, etc.), combinatorial optimization (transportation problems, network flows, MAXSAT, simple plant location, etc.), graph theory (special classes of graphs, stability problems, and their applications), data mining and classification (Logical Analysis of Data), and, last but not least, Boolean theory (satisfiability, duality, Horn functions, threshold functions, and their applications). The volume contains 23 contributed papers along these lines. [less ▲]

Detailed reference viewed: 64 (9 ULiège)
Full Text
Peer Reviewed
See detailLogical Analysis of Data: Classification with justification
Boros, Endre; Crama, Yves ULiege; Hammer, Peter L. et al

in Annals of Operations Research (2011), 188

Learning from examples is a frequently arising challenge, with a large number of algorithms proposed in the classification, data mining and machine learning literature. The evaluation of the quality of ... [more ▼]

Learning from examples is a frequently arising challenge, with a large number of algorithms proposed in the classification, data mining and machine learning literature. The evaluation of the quality of such algorithms is frequently carried out ex post, on an experimental basis: their performance is measured either by cross validation on benchmark data sets, or by clinical trials. Few of these approaches evaluate the learning process ex ante, on its own merits. In this paper, we dis- cuss a property of rule-based classifiers which we call "justifiability", and which focuses on the type of information extracted from the given training set in order to classify new observations. We investigate some interesting mathematical properties of justifiable classifiers. In partic- ular, we establish the existence of justifiable classifiers, and we show that several well-known learning approaches, such as decision trees or nearest neighbor based methods, automatically provide justifiable clas- sifiers. We also identify maximal subsets of observations which must be classified in the same way by every justifiable classifier. Finally, we illustrate by a numerical example that using classifiers based on "most justifiable" rules does not seem to lead to over fitting, even though it involves an element of optimization. [less ▲]

Detailed reference viewed: 82 (5 ULiège)
Full Text
Peer Reviewed
See detailGeršgorin variations III: On a theme of Brualdi and Varga
Boros, Endre; Brualdi, Richard; Crama, Yves ULiege et al

in Journal of Linear Algebra and its Applications (2008), 428

Brualdi brought to Geršgorin Theory the concept that the digraph G(A) of a matrix A is important in studying whether A is singular. He proved, for example, that if, for every directed cycle of G(A), the ... [more ▼]

Brualdi brought to Geršgorin Theory the concept that the digraph G(A) of a matrix A is important in studying whether A is singular. He proved, for example, that if, for every directed cycle of G(A), the product of the diagonal entries exceeds the product of the row sums of the moduli of the off-diagonal entries, then the matrix is nonsingular. We will show how, in polynomial time, that condition can be tested and (if satisfied) produce a diagonal matrix D, with positive diagonal entries, such that AD (where A is any nonnnegative matrix satisfying the conditions) is strictly diagonally dominant (and so, A is nonsingular). The same D works for all matrices satisfying the conditions. Varga raised the question of whether Brualdi’s conditions are sharp. Improving Varga’s results, we show, if G is scwaltcy (strongly connected with at least two cycles), and if the Brualdi conditions do not hold, how to construct (again in polynomial time) a complex matrix whose moduli satisfy the given specifications, but is singular. [less ▲]

Detailed reference viewed: 35 (4 ULiège)
Full Text
See detailPeter Ladislaw Hammer (1936-2006)
Boros, Endre; Crama, Yves ULiege; Simeone, Bruno

in 4OR : Quarterly Journal of the Belgian, French and Italian Operations Research Societies (2007), 5(1), 1-4

Detailed reference viewed: 67 (8 ULiège)
Peer Reviewed
See detailBoolean normal forms, shellability and reliability computations
Boros, Endre; Crama, Yves ULiege; Ekin, Oya et al

in SIAM Journal on Discrete Mathematics (2000), 13

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 16 (1 ULiège)
Full Text
Peer Reviewed
See detailA complexity index for satisfiability problems
Boros, Endre; Crama, Yves ULiege; Hammer, Peter L. et al

in SIAM Journal on Computing (1994), 23

This paper associates a linear programming problem (LP) to any conjunctive normal form p, and shows that the optimum value Z(p) of this LP measures the complexity of the corresponding SAT (Boolean ... [more ▼]

This paper associates a linear programming problem (LP) to any conjunctive normal form p, and shows that the optimum value Z(p) of this LP measures the complexity of the corresponding SAT (Boolean satisfiability) problem. More precisely, there is an algorithm for SAT that runs in polynomial time on the class of satisfiability problems satisfying Z(p) \leq 1 + \frac{c \log n}{n} for a fixed constant c, where n 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(p) \leq 1 + (1/n^\beta ). [less ▲]

Detailed reference viewed: 17 (0 ULiège)
Full Text
Peer Reviewed
See detailChvátal cuts and odd cycle inequalities in quadratic 0-1 optimization
Boros, Endre; Crama, Yves ULiege; Hammer, Peter L.

in SIAM Journal on Discrete Mathematics (1992), 5

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 ... [more ▼]

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 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 S[3]. As a corollary, a compact linear programming formulation is presented for the maximum cut problem for the case of weakly bipartite graphs. [less ▲]

Detailed reference viewed: 14 (0 ULiège)
Full Text
Peer Reviewed
See detailUpper-bounds for quadratic 0-1 maximization
Boros, Endre; Crama, Yves ULiege; Hammer, Peter L.

in Operations Research Letters (1990), 9

In this paper, three different approaches are generalised to obtain upper bounds for the maximum of a quadratic pseudo-Boolean function f over [0,1]^n. The original approaches (complementation ... [more ▼]

In this paper, three different approaches are generalised to obtain upper bounds for the maximum of a quadratic pseudo-Boolean function f over [0,1]^n. The original approaches (complementation, majorization and linearization) were introduced by Hammer, Hansen and Simeone. The generalization in this paper yields three upper bounds, Ck, Mk and Lk for each integer k ⩾ 2, where Cn = Ln = Mn is the maximum of f, and C2 = L2 = M2 is the roof duality bound studied by Hammer, Hansen and Simeone. It is proved that Ck = Mk = Lk for all values of k. [less ▲]

Detailed reference viewed: 18 (0 ULiège)
Full Text
Peer Reviewed
See detailPolynomial-time inference of all valid implications for Horn and related formulae
Boros, Endre; Crama, Yves ULiege; Hammer, Peter L.

in Annals of Mathematics & Artificial Intelligence (1990), 1

This paper investigates the complexity of a general inference problem: given a propositional formula in conjunctive normal form, find all prime implications of the formula. Here, a prime implication means ... [more ▼]

This paper investigates the complexity of a general inference problem: given a propositional formula in conjunctive normal form, find all prime implications of the formula. Here, a prime implication means a minimal clause whose validity is implied by the validity of the formula. We show that, under some reasonable assumptions, this problem can be solved in time polynomially bounded in the size of the input and in the number of prime implications. In the case of Horn formulae, the result specializes to yield an algorithm whose complexity grows only linearly with the number of prime implications. The result also applies to a class of formulae generalizing both Horn and quadratic formulae. [less ▲]

Detailed reference viewed: 23 (0 ULiège)