Basic Notions Seminar
Fall 2018
All talks are from 12001300 in the Seminar room, unless otherwise specified.

Oct18

Can I get a witness (set)?Dan BatesUSNA, MathTime: 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.

Oct11

Completeness, Incompleteness, Consistency and Independence: Gödel's revolutionizing of logicDarren CreutzUSNA, MathematicsTime: 12:00 PM

Sep25

Polymatroids and ChunsCarolyn ChunUSNA, MathTime: 12:00 PM
View Abstract
Nearly 10 years after Deborah Chun's paper on excluded minors for deletioncontraction 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.

Sep13

A Decomposition Method for Solving Large Linear (And Integer) ProgramsRob CurryUSNA, MathTime: 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 nonbasic 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 nonbasic 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 branchandprice algorithm (BP) that deploys CG within a branchandbound 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.