Lattice based extended formulations for integer linear equality systems

Mathematics – Optimization and Control

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-524961

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.