Dual bounds of integer programming problems

Question

I often read in papers when branch-and-X algorithms are used to solve mixed integer programming problems, that the lower bound (in the minimization case) obtained from solving a linear programming relaxation at each branching node, is called a dual bound. Consequently, the gap between the best (smallest) linear programming lower bound of an active branching node and the best known integer feasible solution, is then called the duality gap. But can we consider the bound from the LPs a dual bound and the gap a duality gap? I would at least consider the gap to be an optimality gap and maybe say that the bound is a linear programming bound as there is no duality going on. Or am I wrong?

Answer 1

The notions of dual bound and primal bound originate a bit more generally, I think. We typically call an (iterative optimization) algorithm primal when it maintains a feasible solution in every iteration. The Ford-Fulkerson algorithm for solving maximum flow is an example where we have a feasible flow in every iteration, or the simplex method, where we have a feasible LP solution all the time. A complementary concept is a dual algorithm that maintains a certificate of optimality in each iteration; the dual simplex algorithm is an example: we have an optimal solution after each pivot, but the solution does not necessarily satisfy the constraints; in fact, it becomes feasible (if there is a feasible solution) only in the very last iteration. For LPs and other problems you may know that (primal) optimality is the same as dual feasibility.

In brief: primal refers to feasibility, dual refers to optimality.

Now, returning to your question: the primal bound always refers to the value of a solution that satisfies all the constraints, in particular the integrality constraints. According to the above, a dual bound refers to the value of the current "optimality proof." This is one, out of several, viewpoints, I guess. So, finally, I agree that you can call the dual bound an LP bound when it comes from solving an LP relaxation. And even when I use dual bound I would not speak of duality gap, but of optimality gap as you do.

I hope someone has more substance to add to this.

Answer 2

As you said branch-and-X algorithm, AFAIK, the main method of solving MIPs is the branch-and-cut method, since it is used in all modern MIP solvers. The branch-and-cut method is a combination of the branch-and-bound and cutting-plane algorithms.

It should be noted that the dual simplex method is the main LP method to solve MIPs which, it repeats the work of the primal simplex method applied to the dual LP.

The basic structure of the branch-and-bound method is the search tree. Each of the MIPs in the child nodes is obtained from the parent MIP by adding one or more new constraints that are usually upper or lower bounds for integer variables.

As @Marco Lübbecke said, In the LP-based branch-and-bound method, the upper bound at any node is the optimal objective value of the relaxation LP at this node. The lower bound is the largest value of the objective function attained on the already found feasible solutions of the original MIP and then, The B&B gap is the difference between these terms.