0
$\begingroup$

Is there an example of an $m\times n$ integer matrix $A$ and an integer vector $b\in \mathbb {Z}^{m}$ such that the polyhedron $P := \{ x\in \mathbb {R}^{n} \mid A x \leq b\}$ is integer, while $A$ is not totally unimodular?

Note that a polyhedron is integer if all of its vertices are integral.

$\endgroup$
3
  • 1
    $\begingroup$ Please read: "To what extent are math questions allowed?", what is the perspective you desire that places this question within our scope? $\endgroup$
    – Rob
    Commented May 4, 2022 at 8:50
  • 3
    $\begingroup$ @Rob Integrality of polyhedra is of some importance in discrete optimization, which IMO is definitely a fit with this site. $\endgroup$
    – prubin
    Commented May 4, 2022 at 15:40
  • 1
    $\begingroup$ Cross-posted at math.stackexchange.com/questions/4442667/…. $\endgroup$
    – prubin
    Commented May 5, 2022 at 3:00

2 Answers 2

5
$\begingroup$

The answer is yes, and the proof is trivial. Recall that a TUM matrix has all coefficients in $\lbrace -1, 0, 1\rbrace.$ Start with any $P := \{ x\in \mathbb {R}^{n} \mid A x \leq b\}$ that is integer. If $A$ happens to be TUM, change $A$ to $2A$ and $b$ to $2b$. The polynomial is unchanged, but the new constraint matrix $2A$ cannot be TUM since it will contain components of $2$ and/or $-2$.

$\endgroup$
3
$\begingroup$

You might want to look at MRP(Material Requirements Planning)/Leontief matrices.

In an MRP/Leontief matrix/model:

Each constraint is an equality,

Every column has exactly one positive coefficient and it is a +1, (the output)

Each column has 0 or more negative coefficients, every one of which is integer, (inputs needed)

Each RHS coefficient is a nonnegative integer. (the demands)

Result: An LP whose complete constraint set is an MRP set has an optimal solution that is integer.

Further, if the objective coefficients are all integer, then there is an optimal solution with integral dual prices.

Ref: Jeroslow, R., K. Martin, R. Rardin, J. Wang(1992), "Gainfree Leontief substitution flow problems," Mathematical Programming, 57, pp. 375-414.;

$\endgroup$
1
  • $\begingroup$ would you please, where can we find the related MRP model in the mentioned reference? I have seen that here, but there is no abbreviation like MRP! AFAIK, the MRP system cannot be defined as a TUM based on the complex material's matrix. Would you more elaborate on? $\endgroup$
    – A.Omidi
    Commented May 7, 2022 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.