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.