2
$\begingroup$

It is known that (quoted from CLRS, 3rd edition)

If $a$ and $b$ are any integers, not both zero, then $\text{gcd}(a, b)$ is the smallest positive element of the set $\{ax + by: x, y \in \mathbb{Z}\}$ of linear combinations of $a$ and $b$.

Generally, we can formulate the problem of computing $x = \text{gcd}(c_1, c_2, \ldots, c_n)$ as an integer programming ($P$), as done in JOTA1977:

\begin{align*} \max & \quad x, \\ \text{subject to } & \quad c_j/x = y_j, \qquad j = 1, 2, \ldots, n, \\ & \quad y_j \in \mathbb{Z}, \qquad j = 1, 2, \ldots, n. \end{align*}

Its dual ($D$) is given as:

\begin{align*} \min & \quad \sum_{j=1}^{n} c_j z_j, \\ \text{subject to } & \quad \sum_{j=1}^{n} c_j z_j > 0, \\ & \quad z_j \in \mathbb{Z}, \qquad j = 1, 2, \ldots, n. \end{align*}

Then JOTA1977 reads,

When the $c_j$'s are all integers and $c \neq 0$, it is noted by Greenberg (Ref. 3) that the greatest common divisor of the $c_j$'s is the minimum of $cz$, subject to $cz \ge 1$ and $z$ integer.

I have no access to Greenberg (Ref. 3).

I have computed the dual of the integer programming above and I got $yz \ge 1$ instead of $cz \ge 1$.

How to obtain the dual of the integer programming for $\text{gcd}$?


(Added 1: I compute the dual by the method of Lagrange Multipliers. (I use it in LP, but I am not sure whether this is valid for ILP.) Multiplying $c_j = x y_j$ by $z_i$, summing the $n$ equality constraints, and letting it be an upper bound for $x$: $x \le cz = yzx$.)

(Added 2: I realized that the integer programming above is not linear due to $c_j/x = y_j$.)

$\endgroup$
  • $\begingroup$ How did you compute the dual? $\endgroup$ – Misha Lavrov Apr 21 '19 at 6:42
  • $\begingroup$ @MishaLavrov By the method of Lagrange Multipliers. (I use it in LP, but I am not sure whether this is valid for ILP.) Multiplying $c_j = x y_j$ by $z_i$, summing the $n$ equality constraints, and letting it be an upper bound for $x$: $x \le cz = yzx$. $\endgroup$ – hengxin Apr 21 '19 at 7:18
  • $\begingroup$ I'm also having trouble getting Lagrange duality to work. Are you sure that "Greenberg (Ref. 3)" does use duality to prove this fact? $\endgroup$ – Misha Lavrov Apr 21 '19 at 15:37
  • 1
    $\begingroup$ About whether Lagrange multipliers are valid for IP: in general, the dual is the same for the IP and for its fractional relaxation (e.g. for an ILP and its LP relaxation), so unless your IP formulation is perfect there will be a duality gap. In particular, the relaxation of your IP is unbounded, so we don't expect things to work without fiddling. $\endgroup$ – Misha Lavrov Apr 21 '19 at 15:55
  • $\begingroup$ @MishaLavrov I have no access to Greenberg (Ref. 3), and I am not sure whether it uses Lagrange duality. However, in the abstract of JOTA1977, it is mentioned that "The primal-dual formulation (in this paper) is based on a number-theoretic, rather than a Lagrangian, duality property; consequently, it avoids the duality gap common to Lagrangian duals in integer programming." By the way, I have edited the post to include the dual program given in the JOTA1977 paper. $\endgroup$ – hengxin Apr 22 '19 at 1:30
0
$\begingroup$

Converting Misha Lavrov's help comment into an answer:

Looking over the Meyer and Fleisher paper (1) it doesn't claim that Greenberg uses duality at all, so I assume that they are just citing a description of the Euclidean algorithm, and (2) they prove strong duality right there in Theorem 2.1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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