Skip to main content Skip to footer site map
Mathematics Department

Basic Notions Seminar

Fall 2018

All talks are from 1200-1300 in the Seminar room, unless otherwise specified.

  • Oct
    18
  • Can I get a witness (set)?
    Dan Bates
    USNA, Math
    Time: 12:00 PM

    View Abstract

    When trying to describe the solutions of a polynomial system, we have to choose a data type for each "piece" of the solution set. For example, a solution set might consist of a surface, two lines, and five points. Some might choose to describe each of these components by providing a list of polynomials that specifically pick out the component. In the world of numerical algebraic geometry, the goal is to produce a "witness set" for each component. The primary goal for this talk is to introduce this type of problem (polynomial system) and this type of solution (witness set) through examples, though we will likely also get into some of the geometric tools around these ideas.
  • Oct
    11
  • Completeness, Incompleteness, Consistency and Independence: Gödel's revolutionizing of logic
    Darren Creutz
    USNA, Mathematics
    Time: 12:00 PM
  • Sep
    25
  • Polymatroids and Chuns
    Carolyn Chun
    USNA, Math
    Time: 12:00 PM

    View Abstract

    Nearly 10 years after Deborah Chun's paper on excluded minors for deletion-contraction polymatroids appeared, I am working with Joseph Bonin and Steven Noble on some excluded minor characterizations of certain classes of polymatroids related to D. Chun's work. In this talk, I define a polymatroid and present some of D. Chun's results. I will also give some motivating background and relate this subject to ongoing work in matroid theory. Note: A polymatroid is NOT a kind of matroid.
  • Sep
    13
  • A Decomposition Method for Solving Large Linear (And Integer) Programs
    Rob Curry
    USNA, Math
    Time: 12:00 PM

    View Abstract

    When linear programs (LPs) become too large to explicitly consider all variables, conventional LP solution techniques may not be computationally viable. In many such cases, though, a majority of variables will be non-basic and assume a value of zero for an optimal LP solution. To take advantage of this observation, decomposition methods may be deployed to consider only a subset of all possible variables. In this talk, I describe the details of one such method, column generation (CG). I detail how CG involves the implicit pricing of non-basic variables to generate new column variables, and I show how CG can prove the optimality of a current solution. Furthermore, I will also discuss the branch-and-price algorithm (BP) that deploys CG within a branch-and-bound tree to solve integer linear programs having a large number of variables. I describe the strengths, weaknesses, and challenges involved with deploying CG and BP algorithms. Finally, I outline a few classes of problems for which CG and BP might be useful.
go to Top