<p>I would suspect not.  There are several main factors here:</p>
<ol>
<li><p>The overall algorithm is a &quot;Lenstra-type algorithm&quot; that essentially is a fancy generalized branching algorithm.  But finding the right branching directions is a lot of work, that may not be beneficial practically.  So this type of algorithm does not even exist as an implementation for linear integer programming.<br />
Practical codes typically do branching on variables directly since it does not make underlying LP's numerically too much more complicated.</p>
</li>
<li><p>The algorithm requries a separation type procedure called ellipsoid rounding.  This is a variant of an ellipsoid method, and as we know, pratically are slow because they are numerically unstable.</p>
</li>
<li><p>For implementing the ellipsiod rounding procedure for these sets, they solve a difficult polynomial optimizaition problem and cite Renegar's work for best complexity.  This is nice in theory, but I'm not sure that Renegar's approach is even implemented.  More often used is &quot;Cylindrical Algebraic Decomposition&quot;, which is implmented in Mathematica and Maple, but technically has a worse complxity with respect to the dimension.</p>
</li>
</ol>

CC BY-SA 4.0
2024-08-26T19:08:45.050Z
2024-08-26T19:08:45.050Z
Robert Hildebrand
<p>Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ over integer points in a convex set in $\Bbb R^k$. Has this ever been implemented in any package?</p>

<ds.algorithms><integer-programming><convex-optimization><software><implementation>
Has Khachiyan/Porkolob's convex integer optimization been implemented?
Turbo
# Has Khachiyan/Porkolob's convex integer optimization been implemented?

(Asked by: username_0 on 2018-02-06)

Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ over integer points in a convex set in $\Bbb R^k$. Has this ever been implemented in any package?

**Tags:** ds.algorithms, integer-programming, convex-optimization, software, implementation


---

## 1 answers

### Answer by username_1 on 2024-08-26. Score: 3 | Accepted answer

I would suspect not. There are several main factors here:

1. The overall algorithm is a "Lenstra-type algorithm" that essentially is a fancy generalized branching algorithm. But finding the right branching directions is a lot of work, that may not be beneficial practically. So this type of algorithm does not even exist as an implementation for linear integer programming.  
   Practical codes typically do branching on variables directly since it does not make underlying LP's numerically too much more complicated.
2. The algorithm requries a separation type procedure called ellipsoid rounding. This is a variant of an ellipsoid method, and as we know, pratically are slow because they are numerically unstable.
3. For implementing the ellipsiod rounding procedure for these sets, they solve a difficult polynomial optimizaition problem and cite Renegar's work for best complexity. This is nice in theory, but I'm not sure that Renegar's approach is even implemented. More often used is "Cylindrical Algebraic Decomposition", which is implmented in Mathematica and Maple, but technically has a worse complxity with respect to the dimension.


---

