3
$\begingroup$

For fun, I explored vertex enumeration algorithms for linear programs to find all feasible extreme points in a polytope. Naturally, I asked, "Do there exist algorithms that solve for all integer points within a polytope?", but I found only two sources that discuss this topic: this paper and this CS StackExchange question. Thus, there doesn't seem to be much research on this topic. Does there exist more papers or lectures on this topic?

Currently, I'm working on a Branch & Bound algorithm that only fathoms when it reaches infeasible solutions (in that it uniquely branches on integer solutions to find neighboring integer solutions), but I would like more resources that discuss existing algorithms that solve for all integer points such that while exploring and implementing other approaches, it can assist/improve the Branch & Cut approach I'm trying to implement.

$\endgroup$
8
  • $\begingroup$ You might want to look at the answers to this question: How to find all vertices of a polyhedron. $\endgroup$ Commented Apr 23, 2024 at 15:34
  • $\begingroup$ Is the middle branch really $n-1$ separate branches? Also, how do you enforce $\not=$? $\endgroup$ Commented Apr 24, 2024 at 23:23
  • $\begingroup$ it is n-1 branches, as you'd have check every adjacent integer that may have the same values, and you just linearize it like you would with Big-M via math.stackexchange.com/a/1517850/1105283 $\endgroup$ Commented Apr 24, 2024 at 23:40
  • $\begingroup$ thankfully in implementation, CPLEX already has a method of handling $\neq$ $\endgroup$ Commented Apr 24, 2024 at 23:41
  • $\begingroup$ I recommend explicitly expanding the tree plot to $n-1$ branches because what you have now means something else. $\endgroup$ Commented Apr 24, 2024 at 23:43

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.