Publication
On the Power and Limitations of Branch and Cut
Related concepts (35)
Boolean satisfiability problem
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable.
Algebraic geometry
Algebraic geometry is a branch of mathematics which classically studies zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical problems about these sets of zeros. The fundamental objects of study in algebraic geometry are algebraic varieties, which are geometric manifestations of solutions of systems of polynomial equations.
Formal proof
In logic and mathematics, a formal proof or derivation is a finite sequence of sentences (called well-formed formulas in the case of a formal language), each of which is an axiom, an assumption, or follows from the preceding sentences in the sequence by a rule of inference. It differs from a natural language argument in that it is rigorous, unambiguous and mechanically verifiable. If the set of assumptions is empty, then the last sentence in a formal proof is called a theorem of the formal system.
Algebraic structure
In mathematics, an algebraic structure consists of a nonempty set A (called the underlying set, carrier set or domain), a collection of operations on A (typically binary operations such as addition and multiplication), and a finite set of identities, known as axioms, that these operations must satisfy. An algebraic structure may be based on other algebraic structures with operations and axioms involving several structures.
Proof assistant
In computer science and mathematical logic, a proof assistant or interactive theorem prover is a software tool to assist with the development of formal proofs by human-machine collaboration. This involves some sort of interactive proof editor, or other interface, with which a human can guide the search for proofs, the details of which are stored in, and some steps provided by, a computer. A recent effort within this field is making these tools use artificial intelligence to automate the formalization of ordinary mathematics.
Ample line bundle
In mathematics, a distinctive feature of algebraic geometry is that some line bundles on a projective variety can be considered "positive", while others are "negative" (or a mixture of the two). The most important notion of positivity is that of an ample line bundle, although there are several related classes of line bundles. Roughly speaking, positivity properties of a line bundle are related to having many global sections. Understanding the ample line bundles on a given variety X amounts to understanding the different ways of mapping X into projective space.
Canonical bundle
In mathematics, the canonical bundle of a non-singular algebraic variety of dimension over a field is the line bundle , which is the nth exterior power of the cotangent bundle on . Over the complex numbers, it is the determinant bundle of the holomorphic cotangent bundle . Equivalently, it is the line bundle of holomorphic n-forms on . This is the dualising object for Serre duality on . It may equally well be considered as an invertible sheaf.
Real algebraic geometry
In mathematics, real algebraic geometry is the sub-branch of algebraic geometry studying real algebraic sets, i.e. real-number solutions to algebraic equations with real-number coefficients, and mappings between them (in particular real polynomial mappings). Semialgebraic geometry is the study of semialgebraic sets, i.e. real-number solutions to algebraic inequalities with-real number coefficients, and mappings between them. The most natural mappings between semialgebraic sets are semialgebraic mappings, i.
Flat morphism
In mathematics, in particular in the theory of schemes in algebraic geometry, a flat morphism f from a scheme X to a scheme Y is a morphism such that the induced map on every stalk is a flat map of rings, i.e., is a flat map for all P in X. A map of rings is called flat if it is a homomorphism that makes B a flat A-module. A morphism of schemes is called faithfully flat if it is both surjective and flat. Two basic intuitions regarding flat morphisms are: flatness is a generic property; and the failure of flatness occurs on the jumping set of the morphism.
Divisor (algebraic geometry)
In algebraic geometry, divisors are a generalization of codimension-1 subvarieties of algebraic varieties. Two different generalizations are in common use, Cartier divisors and Weil divisors (named for Pierre Cartier and André Weil by David Mumford). Both are derived from the notion of divisibility in the integers and algebraic number fields. Globally, every codimension-1 subvariety of projective space is defined by the vanishing of one homogeneous polynomial; by contrast, a codimension-r subvariety need not be definable by only r equations when r is greater than 1.