4 ms·
can't you just use the strong duality theorem to reframe an integral optimization problem as a system of integer inequalities? I thought you usually don't do th
by sterlind 3y ago
can't you just use the strong duality theorem to reframe an integral optimization problem as a system of integer inequalities? I thought you usually don't do that because the satisfaction problem is harder in practice.
- whatever1 3y agoNo unfortunately strong duality does not hold for integer problems. But your intuition is right, this is roughly how IP optimizers work. They relax the problem to a continuous one (aka convert the {0,1} to [0,1]), solve this super easy linear problem and try to find integral solutions close this linear optimum. If not, start branching on the integers and solve smaller and smaller linear problems until you prove optimality.