12
$\begingroup$

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?

$\endgroup$
17
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Also, calling bounds primal and dual allows you to be independent of the optimization sense (minimization and maximization). When you deal with generic methods, it is not convenient to use "lower bound" and "upper bound" because the sense of objective function is not known. $\endgroup$ – Ruslan Sadykov Dec 17 '19 at 7:55
  • 1
    $\begingroup$ So, in some sense, a bound becomes "dual" if it is approximating the optimal value from the optimistic side, and "primal" if it approximates it from the pessimistic side? Or is this too simplified? $\endgroup$ – Djames Dec 17 '19 at 8:39
  • 1
    $\begingroup$ yes, @djames, that sounds right. primal proves that we already have a solution and it cannot get worse; dual proves that there is no better than... $\endgroup$ – Marco Lübbecke Dec 17 '19 at 8:56
  • $\begingroup$ @Marco Lübbecke, thanks for your detailed explanation. $\endgroup$ – A.Omidi Dec 17 '19 at 10:08
-3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I downvoted this answer as I don’t think it tries to answer the question. $\endgroup$ – Sune Dec 17 '19 at 15:22
  • $\begingroup$ Unnecessary downvote. $\endgroup$ – Alexandre Frias Dec 17 '19 at 19:14

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.