Linear Programming Relaxation - Branch and Bound For Exact Solutions

Branch and Bound For Exact Solutions

As well as its uses in approximation, linear programming plays an important role in branch and bound algorithms for computing the true optimum solution to hard optimization problems.

If some variables in the optimal solution have fractional values, we may start a branch and bound type process, in which we recursively solve subproblems in which some of the fractional variables have their values fixed to either zero or one. In each step of an algorithm of this type, we consider a subproblem of the original 0-1 integer program in which some of the variables have values assigned to them, either 0 or 1, and the remaining variables are still free to take on either value. In subproblem i, let Vi denote the set of remaining variables. The process begins by considering a subproblem in which no variable values have been assigned, and in which V0 is the whole set of variables of the original problem. Then, for each subproblem i, it performs the following steps.

  1. Compute the optimal solution to the linear programming relaxation of the current subproblem. That is, for each variable xj in Vi, we replace the constraint that xj be 0 or 1 by the relaxed constraint that it be in the interval ; however, variables that have already been assigned values are not relaxed.
  2. If the current subproblem's relaxed solution is worse than the best integer solution found so far, backtrack from this branch of the recursive search.
  3. If the relaxed solution has all variables set to 0 or 1, test it against the best integer solution found so far and keep whichever of the two solutions is best.
  4. Otherwise, let xj be any variable that is set to a fractional value in the relaxed solution. Form two subproblems, one in which xj is set to 0 and the other in which xj is set to 1; in both subproblems, the existing assignments of values to some of the variables are still used, so the set of remaining variables becomes Vi \ {xj}. Recursively search both subproblems.

Although it is difficult to prove theoretical bounds on the performance of algorithms of this type, they can be very effective in practice.

Read more about this topic:  Linear Programming Relaxation

Famous quotes containing the words branch, bound, exact and/or solutions:

    “In communist society, where nobody has one exclusive sphere of activity but each can become accomplished in any branch he wishes, society regulates the general production and thus makes it possible for me to do one thing today and another tomorrow, to hunt in the morning, fish in the afternoon, rear cattle in the evening, criticize after dinner, just as I have a mind, without ever becoming hunter, fisherman, shepherd or critic.”
    —Karl Marx (1818–1883)

    “The essence of the modern state is that the universal be bound up with the complete freedom of its particular members and with private well-being, that thus the interests of family and civil society must concentrate themselves on the state.... It is only when both these moments subsist in their strength that the state can be regarded as articulated and genuinely organized.”
    —Georg Wilhelm Friedrich Hegel (1770–1831)

    “The primary function of myth is to validate an existing social order. Myth enshrines conservative social values, raising tradition on a pedestal. It expresses and confirms, rather than explains or questions, the sources of cultural attitudes and values.... Because myth anchors the present in the past it is a sociological charter for a future society which is an exact replica of the present one.”
    —Ann Oakley (b. 1944)

    “Those great ideas which come to you in your sleep just before you awake in morning, those solutions to the world’s problems which, in the light of day, turn out to be duds of the puniest order, couldn’t they be put to some use, after all?”
    —Robert Benchley (1889–1945)