Mathematics – Optimization and Control
Scientific paper
2007-02-28
Mathematics
Optimization and Control
uses packages amsmath and amssymb
Scientific paper
We study different extended formulations for the set $X = \{x\in\mathbb{Z}^n \mid Ax = Ax^0\}$ in order to tackle the feasibility problem for the set $X_+=X \cap \mathbb{Z}^n_+$. Here the goal is not to find an improved polyhedral relaxation of conv$(X_+)$, but rather to reformulate in such a way that the new variables introduced provide good branching directions, and in certain circumstances permit one to deduce rapidly that the instance is infeasible. For the case that $A$ has one row $a$ we analyze the reformulations in more detail. In particular, we determine the integer width of the extended formulations in the direction of the last coordinate, and derive a lower bound on the Frobenius number of $a$. We also suggest how a decomposition of the vector $a$ can be obtained that will provide a useful extended formulation. Our theoretical results are accompanied by a small computational study.
Aardal Karen
Wolsey Laurence A.
No associations
LandOfFree
Lattice based extended formulations for integer linear equality systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lattice based extended formulations for integer linear equality systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lattice based extended formulations for integer linear equality systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-524961