5
$\begingroup$

I am given two formulations, that is, two integer programs

$ (IP1)\quad \min \{c^tx \mid Ax\geq a, x\in Z^n\} $

and

$ (IP2)\quad \min \{d^ty \mid By\geq b, y\in Z^m\} $

and I wish to check whether they describe the same problem. That is, I wish to know, whether the set of integer feasible points for both models is the same. This is, however, complicated by the fact that $x$ and $y$ variables may live in totally different spaces (think of the one-constraint binary program for 0-1 knapsack, and the equivalent longest-path flow formulation that mimics the dynamic program --- toootally different models, same problem).

I know that I need a transformation/projection between $(P1)$ and $(P2)$, and for the above knapsack example (and many others), I know how to do this. But I am interested in a generic answer.

I expect that, even when this can be settled in theory (which I assume to be very hard already), computationally doing the "proof" is totally intractable -- and I am ultimately interested in doing a computational check of the equivalence of the two models. Therefore, I can do with a "high probability" argument. What we currently do it to (a) have a reference formulation, (b) explicitly prescribe the transformation (a set of variables that has to be used by every formulation, maybe by explicitly modeling the projection), then (c) use specific instances, (d) put "random" objective functions, (e) solve to optimality, and (f) check whether the same (?) solution occurs -- well, there can be many optimal solutions... so, all this is not so trivial.

I cannot help it but I think of Benders here as well.

$\endgroup$
4
  • $\begingroup$ This transformation between the variables spaces $f(x) =y$, do you assume that you have given $f$ and want to verify it? $\endgroup$ Nov 30 '20 at 12:44
  • $\begingroup$ Since the formulations live in different spaces, you really cannot expect the set of feasible solutions to be the same. At best, you can ask whether there is a bijection between the feasible regions. To me, that might be too stringent for "equivalent" solutions. I would call two formulations "equivalent" if they produce (after transformation) the same optimal objective value and each produces a valid solution with the value (and if both are infeasible or unbounded when they should be). $\endgroup$
    – prubin
    Nov 30 '20 at 18:55
  • $\begingroup$ Paul, what you consinder "equivalent" is the same as my notion, since when I use "every" objective function, I effectively reconstruct all the feasible (extreme) solutions, and this is what I am interested in; when two formulations are not equivalent (for the same problem), then one is usually wrong :) $\endgroup$ Dec 1 '20 at 16:26
  • $\begingroup$ user3680510, I don't know such an $f$; but when it helps we can assume it given first, and generalize later $\endgroup$ Dec 1 '20 at 16:27
1
$\begingroup$

A further algorithmic way:

If $f$ is given you could try to solve for $i=1, \ldots, \text{number of constraints in } A$:

$r_i = \min \{(A_{i:}x): f(x) = y, By \geq b, y \in \mathbb{Z}^m \}$

If $r_i < a_i$ then you have found a counterexample, otherwise you can conclude at least for this instance, that they are equal. Might only be practical if the instance is small and $f$ is simple.

It is also possible to multiply $A_{i:} x \geq a_i$ such they only contain integral values, then one can write a pure feasibility problem $A_{i:} x \leq a_i -1$, which might produce stronger cuts.

$\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.