Integer
flows
in
binary
matroids
^{
[2,3]}:
Geelen
and
Guenin
^{
[5]}
proved
that
the
cut
condition
is
both
sufficient
and
necessary
for
the
existence
of
an
integer
multi-commodity
flow
for
instances
that
are
Eulerian
and
do
not
contain
a
special
obstruction.
As
a
consequence,
one
obtains
an
excluded

minor
characterization
for
weakly
bipartite
graphs,
a
2003
Fulkerson
prize
winner
result
by
Guenin
^{
[6]}.

However,
perhaps
more
importantly,
Geelen
and
Guenin’s
result
confirmed,
for
graphic
matroids,
thevery
deep
and
difficult
1977
Cycling
Conjecture
of
Seymour
^{
[11]}
on
the
existence
of
certain
integer
flows
in
binary
matroids.

During
my
undergraduate
studies,
Professor
Guenin
and
I
generalized
this
result
by
proving
Seymour’s
conjecture
for
even-cycle
matroids,
which
are
lifts
of
graphic
matroids
^{
[3]}.
Our
result
has
many
applications
to
packing
odd
st-joins
and
odd
circuit
covers,
as
well
as
graph
colorings
and
graph
homomorphisms.

We
also
considered
Seymour’s
conjecture
for
the
duals
of
even-cycle
matroids.
Surprisingly,
the
conjecture
in
this
case
generalizes
the
Four
Color
Theorem
^{
[2]}.
We
verified
Seymour’s
conjecture
for
such
matroids
having
the
additional
property
that
the
graphic
representation
either
has
an
even-face
embedding
on
simple
topological
surfaces,
or
contains
only
five
odd
edges
forming
a
pentagon
^{
[2]}.

As part of our future work, we plan on examining Seymour’s conjecture for the following two classes of matroids: lifts of cographic matroids known as even-cut matroids, as well as the duals of even-cycle matroids having additional simple properties regarding their graphic representations.

On
the
Mixing
Set
with
a
Knapsack
Constraint
^{
[1]}:
The
mixing
set
with
a
knapsack
constraint
arises
as
a
substructure
in
mixed-integer
programming
reformulations
of
chance-constrained
programs
with
stochastic
right-hand-sides
over
a
finite
discrete
distribution.
A
full
understanding
of
the
mixing
set
with
a
knapsack
constraint
is
very
important
as
it
forms
the
underlying
substructure
to
many
industrial
problems
such
as
probabilistic
lot/batch
sizing
^{
[4,
10]},
probabilistic
production
and
distribution
planning
^{
[8]}.
Recently,
Luedtke
et
al.
^{
[9]}
and
Kucukyavuz
^{
[7]}
studied
valid
inequalities
for
such
sets.
However,
most
of
their
results
were
focused
on
the
equal
probabilities
case
(equivalently
when
the
knapsack
reduces
to
a
cardinality
constraint),
with
only
minor
results
in
the
general
case.

During
my
undergraduate
studies,
Professor
Fukasawa
and
I
focused
on
the
general
probabilities
case
(general
knapsack
constraint).
We
devised
a
relaxation
scheme
for
the
polyhedron
containing
the
coefficients
of
all
valid
inequalities
^{
[1]}.
This
scheme
allowed
us
to
extend
the
previous
results
for
the
equal
probabilities
case
to
the
general
probabilities
case,
as
well
as
enabling
us
to
discover
more
structural
properties,
new
polynomial-time
heuristic
separation
algorithms,
compact
extended
formulations,
and
approximate
formulation
for
the
set.

Our next step is to consider more specific chance-constrained programs such as probabilisitic lotsizing problems with the hope of finding even more efficient separation algorithms.

**
References:**

^{
[1]}
A.
Abdi
and
R.
Fukasawa,
On
the
mixing
set
with
a
knapsack
constraint,
arXiv:
1207.1077
[math.OC],
to
be
submitted.

^{
[2]}
A.
Abdi
and
B.
Guenin,
Packing
odd
circuit
covers:
A
conjecture,
2013,
in
preparation.

^{
[3]}
A.
Abdi
and
B.
Guenin,
The
cycling
property
for
even-cycle
matroids,
2013,
in
preparation.

^{
[4]}
P.
Beraldi
and
A.
Ruszczynski,
A
branch
and
bound
method
for
stochastic
integer
programs
under
probabilistic
constraints,
Optim.
Methods
Softw.
(2002)
17,
359-382.

^{
[5]}
J.
Geelen
and
B.
Guenin,
Packing
odd
circuits
in
Eulerian
graphs,
J.
Combin.
Theory
Ser.
B
(2002)
86,
280-295.

^{
[6]}
B.
Guenin,
A
characterization
of
weakly
bipartite
graphs,
J.
Combin.
Theory
Ser.
B
83
(2001),
112-168.

^{
[7]}
S.
Kucukyavuz,
On
mixing
sets
arising
in
chance-constrained
programming,
Math.
Program.
132(1),
(2012),
31-56.

^{
[8]}
M.A.
Lejeune
and
A.
Ruszczynski,
An
efficient
trajectory
method
for
probabilistic
inventory-production-distribution
problems,
Oper.
Res.
(2007)
50(2),
378-394.

^{
[9]}
J.
Luedtke,
S.
Ahmed,
G.
Nemhauser,
An
integer
programming
approach
for
linear
programs
with
probabilistic
constraints,
Math.
Program.
122(2)
(2010),
247-272.

^{
[10]}
G.
Lulli
and
S.
Sen,
Branchand-price
algorithm
for
multistage
stochastic
integer
programming
with
application
to
stochastic
batch-sizing
problems,
Manage.
Sci.
(2004)
50(6),
786-796.

^{
[11]}
P.D.
Seymour,
The
matroids
with
the
max-flow
min-cut
property,
J.
Combin.
Theory
Ser.
B
(1977)
23,
189-222.