Accepted for Publication in Computers and Operations Research (2010)

Faster Integer-Feasibility in Mixed-Integer Linear Programs by
Branching to Force Change
Jennifer Pryor (jpryor@sce.carleton.ca)
John W. Chinneck (chinneck@sce.carleton.ca)
Systems and Computer Engineering
Carleton University
Ottawa, Ontario K1S 5B6
CanadaOctober 22, 2010

Abstract
Branching in mixed-integer (or integer) linear programming requires choosing both thebranching variable and the branching direction. This paper develops a number of new methods
for making those two decisions either independently or together with the goal of reaching thefirst integer-feasible solution quickly. These new methods are based on estimating theprobability of satisfying a constraint at the child node given a variable/direction pair. The
surprising result is that the first integer-feasible solution is usually found much more quickly
when the variable/direction pair with the smallest probability of satisfying the constraint ischosen.
This is because this selection forces change in many candidate variables
simultaneously, leading to an integer-feasible solution sooner. Extensive empirical results are
given.

1. Introduction
Mixed-integer linear programs (MILP) are composed of a linear objective function and linear
constraints over a set of variables, some or all of which are restricted to take on integer or
binary values ("integer" is assumed to include "binary" as a special case hereafter). The mostpopular solution approach is branch and bound, supplemented with cuts and various otherheuristics such as local searching (see e.g. Johnson et al. (2000)). Nodes in the resulting searchtree are variations on the original model with tightened bounds on the integer variables and/or
added cut constraints. The bounding formula applied at a node in the search tree consists ofthe solution of a linear programming (LP) relaxation of the modified version of the originalmodel represented by the node. The LP relaxation is a linear programming solution of the nodemodel that simply ignores the integer restrictions on the variables.
A branch and bound node that is chosen for further expansion has an LP relaxation solution inwhich at least one of the integer variables does not have an integer value; such integer
variables are candidates for branching. A candidate variable is chosen for branching and twochild nodes are created: branching up adjusts the bound on the branching variable to be no less1

than the current value rounded up, while branching down adjusts the bound on the branchingvariable to be no more than the current value rounded down. If there are k candidate variables,
then there are 2k ways to proceed from the current node to the next node in the usual depthfirst exploration of the search tree. The heuristic used for choosing which of the 2k potential
child nodes to explore next can have a major impact on the speed of the MILP solution.
There are two main ways to branch, i.e. to choose the child node to explore next. The mostcommon approach is to first choose the candidate variable, and then choose the branchingdirection (i.e. decide whether to branch up or down). A great deal of research exists onheuristics for choosing the candidate variable, but there is surprisingly little research on thebest way to choose the branching direction once the candidate variable has been selected. The
second approach is to choose the branching variable and the branching direction
simultaneously. There is relatively little research on techniques in this category.
This paper addresses the question of the best branching heuristic (i.e. the heuristic that mostoften reaches the first feasible solution fastest), given the node that is to be expanded.
Exploring this question sheds some light on the characteristics of MILP models that affect how
well various branching techniques work. Influential characteristics include the presence orabsence of equality constraints, the inclusion of "multiple choice" constraints, and the fractionof inequality constraints that are violated by adjusting the branching variable in the up vs. down
directions. The analysis uncovers some important general principles in branching.
The metric of interest in this paper is speed in reaching the first integer-feasible solution. Thisis important for several reasons. First, several classes of MILP problems do not have an
objective function and require only a feasible solution. Second, in very large MILPs it is wise toreach an incumbent solution early so that at least one integer-feasible solution is in handshould the time limit be reached, and because an incumbent is then available for pruning thedeveloping tree, thereby reducing the overall solution time. Third, if the node selection
heuristic is effective, then reaching an integer-feasible descendent of the chosen node quickly
should lead to an optimum solution more quickly.
There are a variety of branching heuristics, though most are oriented towards fast optimality as
opposed to fast integer-feasibility; see e.g. Achterberg et al. [2005] for an overview andassessment. Many algorithms first choose the branching variable and then the branchingdirection, using separate algorithms for each decision. Given the branching variable, the mostcommon direction selection heuristics are: branch up always, branch down always, or branch tothe closest integer. Branching to the farthest integer is also sometimes used. A number ofcommercial solvers include a parameter that allows the user to make any of these choices,along with the choice to let the solver decide the branching direction using its own heuristic.
Previous research provides no definite conclusions about which branching direction heuristic isbest. Meyer et al. [2003] studied branching direction selection in the context of optimizing theplacement of radioactive seeds for cancer treatment. They compared the branch up, branchdown, and closest integer direction selection heuristics in combination with different node2

selection, variable selection and scaling techniques, as well as with variations on the MILP
model itself. They conclude that the branching direction heuristic has a significant impact on
solution times, but could not identify an overall best heuristic: each method performed betteror worse depending on the scaling method used. For example, branching down worked wellwith aggressive scaling, and branching up worked best with standard scaling.
Jariwala [1995] studied branch and bound solutions to the dynamic layout problem, comparing
the usual three branching direction selection heuristics: branch up, branch down, and closest
integer. He concludes that fixing the branching variable direction selection to either branch up
or branch down is more effective than using the closest integer heuristic for this problem.
Bernatzki et al. [1998] looked at branching direction selection heuristics in a MILP model for
optimizing scrap combination for steel production. They test branching up and branching downon the binary variables, and concluded that branching down performs best for this model.
Driebeek [1966] developed a well-known branching heuristic that selects both the branchingvariable and the branching direction. Tomlin [1971] extended Driebeek’s idea by considering
the integrality of variables. The resulting Driebeek and Tomlin method is a penalty method that
estimates the potential degradation of the objective function value due to selecting a candidate
variable, as estimated by performing a dual simplex pivot, which generates a lower bound on
the bound improvement possible if a given candidate variable is selected as the branchingvariable [Linderoth and Ralphs 2004]. Degradation bounds are calculated separately forbranching up and for branching down. The largest degradation bound is used to choose thebranching variable, and once chosen, the smaller of the bounds for that variable is used tochoose the branching direction. This method is designed to reach optimality quickly, rather
than integer feasibility. It is the default heuristic for branching variable and direction selectionin the GLPK MILP solver [Makhorin 2008] that is used in the experiments reported in this paper.
There are a variety of specialized algorithms for reaching integer-feasibility quickly in MILPs thatare not solely branching heuristics. The pivot-and-shift algorithm (Balas and Martin 1986) has afirst phase that seeks integer feasibility using a variety of special techniques including rounding,specialized pivots and small neighbourhood searches. The OCTANE heuristic (Balas et al. 2001)
for binary integer programs uses the intersection of the improving direction with the extended
facets of the solution hyper-octagon to identify good binary solutions to try. The feasibility
pump (Fischetti et al. 2005) alternates linear programming solutions with rounding. This paper
concentrates on branching-related methods.
The general folklore is that branching in the up direction is usually best. This is definitely true inthe case of so-called "multiple choice" constraints, which are composed entirely of binary
variables and have the form x1 + x2 + x3 + ... xn {≤,=} 1. For these constraints, branching up on
the branching variable (i.e. setting it to 1) forces all other variables in the constraint to zero,hence all variables take on integer values simultaneously. On the other hand, branching downon the branching variable (i.e. setting it to 0) allows the other variables to take on non-integer
values, hence fewer, if any, are forced to integer values. Branching up on a variable in a
multiple choice constraint is decidedly preferable for reaching integer-feasibility quickly.
3

While not guaranteed, each branch in a branch and bound solution will more often than notforce the branching variable to an integer value. To reach an integer feasible solution more
quickly it is desirable to force as many additional candidate variables as possible to integer
values at each branch. How to do this is straightforward in the case of multiple choice
constraints, but not so obvious for other classes of constraints. However because every
candidate variable must be forced to an integer value to reach an integer-feasible solution it isobviously a poor idea to branch in such a way that few candidate variables are affected. The
generalization of this idea is that branching should force as many candidate variables as
possible to change their values, whether or not it can be guaranteed that they will change tointeger values: some may be forced to integer values, thereby speeding the solution.
This brings us to the central theme of this paper, namely branching to force change in thecandidate variable values. This is extremely effective in the case of multiple choice constraints,
where branching up forces all candidate variables in the constraint to integer values
simultaneously. This principle has not been previously articulated as a central motivation in
branching heuristics. Most branching variable selection heuristics concentrate on forcingchange in the value of the objective function. The single exception is the active constraints
branching variable selection method of Patel and Chinneck [2007], which concentrates onchoosing the branching variable that has the greatest impact on the active constraints in thecurrent LP-relaxation solution. Patel and Chinneck’s Method A chooses the candidate variable
that appears in the largest number of active constraints. In so doing it is also choosing thecandidate variable that affects the values of the largest number of other candidate variables via
their involvement in the active constraints. This is a very effective heuristic, outperforming
state of the art commercial MILP solvers in reaching the first integer-feasible solution quickly.
We will return throughout the paper to this theme of choosing the branching variable andbranching direction so as to force change in the values of numerous candidate variables.

2. Experimental Setup
The conclusions in this paper are based on extensive computational experimentation. The
experimental conditions are described below.
The open-source GLPK MILP solver version 4.28 [Makhorin 2008] was modified extensively totest a variety of existing and novel branching heuristics. All parameters were set at their default
values with the following exceptions: Stopping conditions. Solutions ran for a maximum of two hours, or stopped earlier
upon finding the first integer-feasible solution.
 Node selection. Depth-first, except where noted.
 Branching variable selection and branching direction selection. As required for theexperiment at hand.
Hardware consisted of four computers running Windows XP: a Pentium 4 CPU at 3.40GHz with
1 GB of RAM, an Intel Core 2 CPU at 3.40GHz with 3GB of RAM (with solutions running as single
4threads), a Pentium 4 CPU at 3.20GHz with 3GB of RAM, and a Pentium 4 CPU at 2.4 GHz with 1
GB of RAM. Multiple machines were needed to handle the computational load, which
extended over numerous weeks. Given the different machine specifications, the major metricfor speed is the total number of simplex iterations required for the MILP solution. This tracks
clock time closely when node selection, variable selection, and branching direction selection
heuristics are simple and do not require major computation.
A second metric is the number of models solved to integer-feasibility within the two-hour time
limit by a particular method. This could be affected by the slightly different machine speeds.
To minimize this effect, each model in a given comparison was normally solved on the samemachine using the different methods being compared; exceptions are noted. In a number oftest cases the same models were run using the same method on the fastest machine and again
on a slower machine: there was no difference in the number of completed models, so this is
likely a minor effect.
To provide a comparison to a known reference point across all experiments, all performance
profiles include the data for GLPK with all parameters at default settings. The main default
parameter settings of interest are branching variable and direction selection via the Driebeek
and Tomlin heuristic [Tomlin 1971], and node selection via best value of the bounding function.
Note that the GLPK default method was always run on the fastest machine, so the relative
number of model completions was as large as possible, making for a conservative comparison.
Performance profiles [Dolan and Moré 2002] are used to summarize the results throughout the
paper. These provide a graphical summary of the fraction of models (vertical axis) for which thesolution simplex iterations for a given competing method is within some ratio of the number ofsimplex iterations used by the best competing method (horizontal axis). This is a much moremeaningful generalization of the simple statistic giving the fraction of models for which a given
method is the fastest. Performance profiles also provide information about the robustness of acompeting algorithm, which is shown by the maximum height achieved on the vertical axis,
reflecting the fraction of the models solved by the method within the time limit. We plot theratio to the fewest simplex iterations only as far as 10, though there may be higher values in thedata set.
Four well-known MILP problem sets comprising a total of 142 models were used: 56 models
from MIPLIB2003 [Achterberg et al. 2006] (the momentum3, msc98-ip, rd-rplusc-21, and stp3d
models were omitted because they were not solved by any method within the time limit), 11
models from MIPLIB3.0 [Bixby et al. 1998], 7 models from MIPLIB 2.0 [Bixby et al. 1992], and 68
models from Coral [Linderoth 2009]. These include a variety of real-world problems and are
representative of a good general cross-section of MILPs [Achterberg et al. 2006]. At various
points in the paper the models are divided into an "equality-containing" subset that consists of
47 models that include at least one equality constraint involving an integer variable, and an"equality-free" subset that consists of 95 models that include no equality constraints thatinvolve integer variables. The complete set of models used in the experiments is shown in
Table 1.
5

10teams
a1c1s1
aflow30aaflow40b
air04
air05
arki001
atlanta-ip
bell3abell3b
bell4
bell5
bm23
cap6000
dano3mip
danoint
disktomds
fast0507
fiber
fixnet6

gesa2
gesa2-oglass4
gt2
harp2
liu
lseu
manna81markshare1
markshare2
mas74
mas76
misc07mkc
mod008mod011
modglob
momentum1
momentum2
mzzv11
mzzv42zneos-1056905
neos-1122047
neos-1171448
neos-1171692
neos-1171737
neos-1200887
neos-1211578
neos-1228986
neos13neos-1311124
neos-1337489
neos-1346382
neos-1420205
neos-1426635
neos-1426662
neos-1427181
neos-1427261
neos-1429185
neos-1429461
neos-1430701

neos-1436709
neos-1436713
neos-1439395
neos-1440447
neos-1440457
neos-1440460
neos-1442119
neos-1442657
neos-1467067
neos-1480121
neos-1516309
neos-1599274
neos-1616732
neos-495307
neos5
neos-544324
neos-547911
neos-565672
neos-702280
neos-785899

neos-785912
neos-785914
neos-787933
neos-841664
neos-856059
neos-872648
neos-873061
neos-885086
neos-885524
neos-886822
neos-932721
neos-932816
neos-933638
neos-933966
neos-934278
neos-934441
neos-948346
neos-953928
neos-954925
neos-956971

neos-957143
neos-957323
net12
noswotnsrand-ipx
nw04
opt1217
p0033
p0040
p0201
p0282
p0291
p0548
p2756
pk1
pp08a
pp08aCUTS
protfold
qiu
ramos3roll3000
routsentoyset1chseymour
seymour.disj-10
sp97arsp97icsp98arsp98icsp98irstein15
stein27
stein45swath
t1717
timtab1
timtab2
tr12-30
vpm2

Table 1: Models Used in Experiments. Equality-Free Models Shown in Italics.

3. Evaluation of Simple Branching Direction Selection Heuristics
Given the branching variable, there are only two choices available for the branching direction:
the up branch or the down branch. The three most common heuristics for making this choice
are (i) branch up always, (ii) branch down always, or (iii) branch to closest integer (i.e. branchdown if the fractional part of the branching variable has a value less than 0.5 and branch up
otherwise). One might reasonably guess that branching up always would be no better or worse
than branching down always, on the assumption that the composition of the model is more orless uniformly distributed in terms of coefficient signs and magnitudes and types of constraints.
On the other hand, the folklore in the community is that branching up always is the superior
choice. We tested the three basic branching direction heuristics over our complete set of test
models, with results as shown in the performance profile in Figure 1.

6

Up vs. Down vs. Closest Integer: All Models
1
0.9

Fraction of Models

0.8
0.7
0.6
0.5
0.4
0.3

GLPK Default
Up
Down
Closest Integer

0.2
0.1
0
1

2

3

4

5

6

7

8

9

10

Ratio to Fewest Simplex Iterations
Figure 1: Simple Branching Direction Heuristics Over All Models

As Figure 1 shows, branching up always is indeed usually better, and is in fact quite dominant.
Branching down always is the worst heuristic by a significant margin. While these results arefor default GLPK with the simple substitution of the specified branching direction selection
heuristic, the results are similar for a variety of other node and branching variable selection
combinations that we tested.
The relative performance of the branching direction selection heuristics is also similar for theequality-free subset of models, but is quite different for the equality-containing subset, asshown in Figure 2. For the equality-containing subset, note that all methods are significantly
less robust, with the three best methods tied in solving 74.5% of the models (vs. 85.9% for theup always method over all models). Second, when there is at least one equality constraint in
the model then branching up always does not always dominate. Both GLPK default andbranching to the closest integer have a larger fraction of solutions that are within a ratio of 2 ofthe smallest number of simplex iterations. This is so despite the fact that 33 of the 51 models(64.7%) in the equality-containing set include multiple choice constraints, for which it is known
that branching up is the preferred option.

7

Up vs. Down vs. Closest Integer: At Least One Equality
1
0.9

Fraction of Models

0.8
0.7
0.6
0.5
0.4
0.3

GLPK Default
Up
Down
Closest Integer

0.2
0.1
0
1

2

3

4

5

6

7

8

9

10

Ratio to Fewest Simplex Iterations
Figure 2: Simple Branching Direction Heuristics: Subset of Models Containing at Least One Equality Constraint

The presence or absence of equality constraints is a MIP characteristic that affects theperformance of branching methods. As noted earlier, multiple choice constraints are aparticularly influential form of equality constraint.
We will return in Section 8 to the question of why branching up is generally the better choice.

4. Probability-Based Branching Methods
Pesant and Quimper [2008] describe a method for counting solutions in knapsack constraints ofthe form l ≤ cx ≤ u where l and u are integer values representing the lower and upper bounds
respectively, c is a row vector of integers, and x is a column vector of integer variables. A countcan be established for variables whose values have not yet been fixed. For example, consider
the simple constraint x1 + 5x2 ≤ 10 (in general, g(x) ≤ b). We can count the number of solutions
that satisfy the constraint when x2 is fixed at each of its possible values, and calculate the"solution density" as shown in Table 2.
Value of x2
x2=0
x2=1
x2=2
Total solutions

Allowable range for x1[0,10][0,5][0]

Solution count
11
6
1
18

Solution density
11/18 = 0.61
6/18 = 0.33
1/18 = 0.06

Table 2: Solution Density for x1 + 5x2 ≤ 10.

This information can then be used in assigning values to the unfixed variables. For example,
you could choose to fix a variable at the value that has the maximum solution density in order8to provide the largest likelihood that you will be able to assign values to other unfixed variables
in a way that will satisfy the constraint. This reasoning would lead you to set x2=0 in thisexample because this value has the largest solution density.
More generally, the solution counting approach can be applied to examine the possible valuesof g(x) when the n variables (x1, x2, …, xn) each have the range [li, ui], coefficient ci in theconstraint, and are assumed to be uniformly distributed in their ranges [Pesant and Quimper2008]. This linear combination of uniformly distributed random variables results in an
approximately Gaussian normal distribution for g(x), whose mean and variance are:l  ui,2(1)(ui  li  1) 2  1
,
12

(2)

  i 1 ci in

 2  i 1 ci2nConsider the constraint g(x) = 3x1 + 2x2 + 5x3 ≤ 12 in which all variables are integer with range[0, 5]. Ignoring the integrality of the variables, this yields an approximately Gaussian normal
distribution for g(x) shown in Figure 3 which has a mean of 25 and variance of 110.83. Since werequire g(x) ≤ 12, the cumulative probability (shaded in Figure 3), gives an estimate of thelikelihood of satisfying the constraint if the variable values are uniformly distributed in theirranges.

Figure 3: Gaussian distribution for 3x1 + 2x2 + 5x3 ≤ 12

The cumulative probability for a Gaussian normal distribution can be analytically estimated by
the method of Abramowitz and Stegun [1965]. For this example, the cumulative probability ofthe shaded portion of Figure 3 is 0.1084. Thus the probability of satisfying the constraint is
10.84% under the assumption of uniform distribution of the variable values.
9We extend these ideas to develop a number of new branching methods for general mixedinteger linear programs. Let us first consider the case in which the branching variable has
already been selected and only the choice of whether to branch up or down remains. Where
the branching variable xi has the range [li, ui] and current value then the adjusted ranges inthe two child nodes are [li,] for the down branch and [, ui] for the up branch. Thismeans that the normal distributions derived for the up and down branches will be different andthe resulting probability of satisfying the constraint will be different for each branch. For thesame constraint as in Figure 3, branching on x1 = 1.5 yields a down branch with range [0,1] forx1 and an up branch with range [2,5] for x1. The two resulting Gaussian distributions for g(x) are
shown in Figure 4 and Figure 5.

Figure 4: Gaussian distribution for the down branch

Figure 5: Gaussian distribution for the up branch

The cumulative probability of satisfying the constraint is 0.2262 for the down branch and0.0511 for the up branch. These probabilities can then be used to help decide the branchingdirection. For example, one may choose a policy of always branching in the direction thatprovides the greatest probability of satisfying the constraint, or one may choose the opposite
policy. We examine this choice in detail in Section 6.
10

The examples thus far have dealt with inequalities of ≤ form. Inequalities of ≥ are easily dealt
with by calculating their satisfaction probability as 1 minus the cumulative probability of g(x) ≤b.
Dealing with equality constraints is more challenging. Given the assumption of uniform
distribution of the values of the variables within their ranges, the probability of exactly
satisfying an equality constraint is vanishingly small when real-valued variables are also
included in the constraint. For this reason, we instead develop a new measure that reflects how
centered the value of b is within the probability density function for g(x). The more centered b
is within the density function, the more likely it is that values can be found for the variables ing(x) that result in g(x)=b. "Centeredness" is measured by taking the ratio of the cumulative
probability for g(x)≤b to the cumulative probability for g(x)≥b. Specifically, the centeredness
measure is:(3)

The maximum value for the equality centeredness measure is 1, which occurs when P(g(x)≤b) =P(g(x)≥b), i.e. when b is exactly centered in the probability density function for g(x). The
minimum value of the equality centeredness measure is 0, which is achieved when b is at oneof the ends of the probability density function for g(x), i.e. is the least centered. Intermediate
values between 0 and 1 indicate the degree of centeredness between least and most. This
metric thus conveniently measures the degree of centeredness on the same 0 to 1 scale as thesatisfaction probabilities associated with inequalities.
Both the 0 to 1 range and the meaning of the equality centeredness measure conveniently alignwith the probability measures used for inequalities. A higher value of the equality
centeredness measure indicates a higher likelihood of satisfying the equality constraint in thesame way that a higher cumulative probability indicates a higher likelihood of satisfying an
inequality constraint. For this reason we will apply the centeredness measure for equalities inthe same way that we apply the cumulative satisfaction probability in developing branching
methods.
A number of branching methods can be developed using the probability and centeredness
measures. Though the methods are given names related to probability, the equality
centeredness measure is used for equality constraints. Given the branching variable, four suchmethods are:
 Lowest Cumulative Probability (LCP): Suppose that the branching variable appears in kconstraints. For each of the k constraints, calculate the probability of satisfying theconstraint (or the centredness measure if the constraint is an equality) in the up and thedown directions. Select the direction associated with the smallest of the 2k values.
 Highest Cumulative Probability (HCP): Same as LCP except choose the direction
associated with the largest of the 2k values.
11





Lowest Cumulative Probability Votes (LCPV): For each constraint that the branchingvariable appears in, calculate the relevant measure for the up and down directions.
Assign a vote to the branching direction that has the lower value. Choose the branchingdirection that has the most votes over all constraints.
Highest Cumulative Probability Votes (HCPV): For each constraint that the branchingvariable appears in, calculate the relevant measure for the up and down directions.
Assign a vote to the branching direction that has the higher value. Choose thebranching direction that has the most votes over all constraints.

Similar methods for choosing the branching variable and the branching direction
simultaneously can also be developed Two such methods are:
 Variable and Direction Selection using Lowest Cumulative Probability (VDS-LCP): forevery candidate variable, calculate the relevant measure for branching up and branching
down in every constraint in which it appears and choose the candidate variable andbranching direction that gives the lowest value of the measure in any constraint.
 Variable and Direction Selection using Highest Cumulative Probability (VDS-HCP): forevery candidate variable, calculate the relevant measure for branching up and branching
down in every constraint in which it appears and choose the candidate variable andbranching direction that gives the highest value of the measure in any constraint.
Numerous variations on these probability-measure-based methods are possible including
branching in the opposite of the directions returned by any of the methods listed above, using
values from the probability density function instead of the cumulative probability function,
multiplying the probabilities, etc. See Pryor [2009] for a listing and evaluation of these otherpossibilities.

5. Branching Based on Constraint Violation and Satisfaction
Given the current LP relaxation solution, we can examine the effect on each active constraint ofbranching up or down on a candidate variable while all other variables are fixed at their current
values. For inequality constraints this is simple: branching in one direction will violate an active
inequality while branching in the other direction will continue to satisfy the constraint, and infact will render the inequality inactive. Actual calculation of the new value of g(x) for eachactive constraint is not needed since the sign of the coefficient of the candidate variable andthe type of inequality contain all of the needed information, as summarized in Table 3:12

Coefficient Sign Constraint Sense Branching Direction
+
≤
up
+
≤
down
+
≥
up
+
≥
down
–
≤
up
–
≤
down
–
≥
up
–
≥
down

Resultviolatedsatisfiedsatisfiedviolatedsatisfiedviolated
violatedsatisfied

Table 3: Violating or Satisfying Active Inequality Constraints.

In the case of equality constraints, any unilateral change in the value of a variable will violate
the constraint. However branching in the up or down direction will change the range of the
branching variable, and thus there will be different probabilities for g(x)≤b and g(x)≥b in eachdirection. We label the four resulting probabilities as follows: If branching down: DB=P(g(x)≤b) and DA=P(g(x)≥b).
 If branching up: UB=P(g(x)≤b) and UA=P(g(x)≥b).
DA and DB are used in Equation 3 if we branch down, and UA and UB are used in Equation 3 if
we branch up.
It is more efficient to use the four values DB, DA, UB, and UA directly to discover the more andless centered branching directions instead of calculating the value of Equation 3 once for eachbranching direction. The more violating direction, i.e. the direction that leads to the smallest
value of Equation 3, is associated with min(DB, DA, UB, UA). The less violating direction, i.e. thedirection that leads to the largest value of Equation 3, is associated with max[min(DB, DA),
min(UB, UA)]. In the algorithms that follow below, the "satisfying" direction for an equality
constraint is associated with the less violating direction and the "violating" direction for an
equality constraint is associated with the more violating direction.
These definitions can be used to construct branching methods given the branching variable:
 Most Satisfied Votes (MSV): for each active constraint containing the branching variable,
register a vote in favour of the satisfying direction. Choose the direction with thelargest number of votes.
 Most Violated Votes (MVV): for each active constraint containing the branching variable,
register a vote in favour of the violating direction. Choose the direction with the largest
number of votes.

6. Branching to Force Change in the Candidate Variables
For our purposes, the measure of the quality of a branching method is how quickly the branch
and bound method reaches integer feasibility. It follows that a good branching heuristic willcause as many as possible of the current candidate variables to take on integer values in theselected child node. In some special cases, such as multiple choice constraints, it is obvious
how to do this: branching up forces all of the binary variables to integer values simultaneously.
13

In more general constraints it is difficult to know in advance which branch will result in integer
values for the largest number of candidate variables. It is reasonable to assume, however, thatbranching in a way that forces change in the candidate variables is more likely to produce
integer values than branching in a way that causes few candidate variables to change theirvalues. In the latter case the candidate variables will simply maintain their current non-integer
values whereas in the former case they may be forced to an integer value.
There are some existing indications that branching to force change results in fasterachievement of integer feasibility. This was demonstrated by the active constraint branchingvariable selection methods of Patel and Chinneck [2007] which branch on the candidate
variable that has the largest impact on the active constraints by some measure. Choosing thebranching variable in this way propagates changes to a large number of additional candidate
variables. These methods are highly effective in reaching integer feasibility quickly.
The concept that branching to force change in the candidate variable values will speed theachievement of the first integer feasible solution is now empirically testable given the newbranching methods developed in Sections 4 and 5. For inequalities, branching in the directionthat is most likely to satisfy the constraint will usually have less impact on the other variables in
the constraint. Branching in the direction that is least likely to satisfy the constraint will havethe opposite effect. For equalities, branching in the more centered direction should have less
impact on the other candidate variables while branching in the less centered direction shouldhave the most impact.
We test this concept by examining the various new branching methods in pairs. One method ineach pair works towards forcing change in the candidate variables by choosing the directionthat is least likely to satisfy the constraints, and the other method in the pair works towards
satisfying the constraints so that fewer candidate variables are forced to change their values.

14

LCP/LCPV vs. HCP/HCPV: All Models
1
0.9

Fraction of Models

0.8
0.7
0.6
0.5
GLPK Default
LCP
HCP
LCPV
HCPV

0.4
0.3
0.2
0.1
0
1

2

3

4

5

6

7

8

9

10

Ratio to Fewest Simplex Iterations
Figure 6: LCP/LPV vs. HCP/HCPV Over All Models

Figure 6 shows the results over all of the models in the test set when using the LCP, LCPV, HCP
and HCPV methods to choose the branching direction, where the branching variable is chosen
by the default GLPK method in all cases. Figure 6 shows that the two methods that work
towards forcing change by choosing the direction having the smallest likelihood of satisfying theactive constraints (LCP and LCPV) both give better results than their opposites (HCP and HCPV).
The results are also slightly better than those for default GLPK.
The effect is much stronger when the probability-based methods select both the branchingvariable and the branching direction, as shown in Figure 7 for the VDS-LCP method, which
forces change, vs. the VDS-HCP method, which does not. Both of these methods outperformdefault GLPK, but VDS-LCP dominates in terms of fewer simplex iterations required, as well as
robustness in that it is able to reach a feasible solution within the time limit for 4 more models
than VDS-HCP and 6 more models than default GLPK.

15

VDS-LCP vs. VDS-HCP: All Models
1
0.9

Fraction of Models

0.8
0.7
0.6
0.5
0.4
0.3

GLPK default

0.2

VDS-LCP

0.1

VDS-HCP

0
1

2

3

4

5

6

7

8

9

10

Ratio to Fewest Simplex Iterations
Figure 7: VDS-LPC vs. VDS-HCP Branching Over All Models

The pattern in Figure 7 is similar when the subset of equality-free models is examined, but
including equality constraints has a significant impact, as shown in Figure 8. Now VDS-LCP
dominates by a considerable margin, whereas VDS-HCP is only about as good as default GLPK.
VDS-LCP also reaches a feasible solution for 7 more models than default GLPK and 8 more than
VDS-HCP. Moving in the less-centered direction for the equality constraints has a significant
impact.

16

VDS-LCP vs. VDS-HCP: At Least One Equality
1
0.9

Fraction of Models

0.8
0.7
0.6
0.5
0.4
0.3

GLPK Default
VDS-LCPVDS-HCP

0.2
0.1
0
1

2

3

4

5

6

7

8

9

10

Ratio Fewest Simplex Iterations
Figure 8: VDS-LCP vs. VDS-HCP When Equality Constraints are Present

Figure 9 shows the effect of branching based on an assessment of the number of active
constraints violated or satisfied by a unilateral adjustment in the branching variable. The
branching variable is selected by the default GLPK method, but the branching direction is
selected by the MVV (most violated votes) or MSV (most satisfied votes) method. MVV
direction selection far outperforms MSV direction selection, and outperforms default GLPK.
These results also support the notion that branching to force change leads to integer feasibility
sooner.

17

MVV vs. MSV: All Models
1
0.9

Fraction of Models

0.8
0.7
0.6
0.5
0.4
0.3
GLPK Default
MSV
MVV

0.2
0.1
0
1

2

3

4

5

6

7

8

9

10

Ratio to Fewest Simplex Iterations
Figure 9: MVV vs. MSV Over All Models

When there are only inequalities in the model, MVV direction selection is strongly dominant
when using the variable selected by GLPK, as shown in Figure 10. It is also more robust, solving
10 more models than MSV, and one more model than default GLPK within the time limit.

18

MVV vs. MSV: Inequalities Only
1
0.9

Fraction of Models

0.8
0.7
0.6
0.5
0.4
0.3

GLPK Default

0.2

MSV

0.1

MVV

0
1

2

3

4

5

6

7

8

9

10

Ratio to Fewest Simplex Iterations
Figure 10: MVV vs. MSV in All-Inequality Models

However the picture is more mixed when the model contains equality constraints, as shown in
Figure 11. In this case, MVV direction selection using the branching variable selected by GLPK
uses the fewest simplex iterations on most models, but runs into difficulties on a few models.

MVV vs. MSV: At Least One Equality
1
0.9

Fraction of Models

0.8
0.7
0.6
0.5
0.4
GLPK Default

0.3
0.2

MSV

0.1

MVV

0
1

2

3

4

5

6

7

8

9

10

Ratio to Fewest Simplex Iterations
Figure 11: MVV vs. MSV When Equalities are Included

19

The active-constraints methods of Patel and Chinneck [2007] choose the candidate variable
that has the most impact on the active constraints, in keeping with the goal of forcing the mostchange in the candidate variables. One of the simplest and most effective of these methods is
Method A, which simply chooses the candidate variable that appears in the largest number ofactive constraints at the LP relaxation solution in the parent node. The effect of substituting
Method A for branching variable selection in place of the GLPK default method for branchingvariable selection is examined in Table 4. The best value in each pair of results is shown inboldface. All four machines were used to generate these results, so the fraction solved results
are not strictly comparable; the trends are clear nonetheless.
variable selection –direction selection
GLPK Default
GLPK-UPA-UP
GLPK-LCP
A-LCP
GLPK-LCPVA-LCPV
GLPK-MVV
A-MVV

fraction fewest
simplex iterations
0.16200.28870.36620.18310.30280.1901
0.23940.20420.3028

fraction solved
0.82390.85920.89440.83100.85920.79580.85210.83100.8521

Table 4: Effect of Branching Variable Selection Method

As shown in Table 4, replacing the GLPK default branching variable selection method by
Method A is always beneficial, whether the direction selection heuristic is always-up (UP), LCP,LCPV or MVV. When the 4 pairs of methods shown in the table are compared, the fraction of
the models for which the method is best (in terms of simplex iterations) always increases, andthe total fraction of models that are solved to integer feasibility within the time limit always
increases when Method A replaces the GLPK default branching variable selection procedure.
The overall best method among those compared in Table 4 is Method A for variable selection
coupled with always branching in the up direction. This is the combination of methods
suggested by Patel and Chinneck [2007] and is the best of the branching methods in theliterature for seeking MIP feasibility.
The dominant conclusion from these experiments is clear: branching to force change in as many
candidate variables as possible is a superior tactic for reaching integer feasibility quickly. Thisfinding is consistent across a number of different branching methods that assess the probabilityof reaching an LP-feasible solution for the constraints under consideration, as well as acrossmethods based on assessing whether a unilateral change in the branching variable will violate
or satisfy the active constraints.
The single exception to this conclusion that we have identified thus far is the case of setcovering problems, whose constraints are all the form x1 + x2 + … + xn ≥ 1. Branching to force
20

change suggests that branching down will provide superior results in terms of reaching afeasible solution quickly, however, this is not the case. This is not a surprise since a feasible(but poor) solution is readily available: simply set all variables equal to one. Given this, itfollows readily that branching up will provide better results; we confirmed this experimentally.

7. A-UP vs. VDS-LCP
Choosing the branching variable via Method A coupled with always branching up (A-UP)
represents the current state of the art in branching methods for seeking integer feasibility in
MILPs. In A-UP, the branching variable selection is disconnected from the branching direction
selection, unlike method VDS-LCP, which makes both decisions simultaneously. These two
approaches are compared in Figure 12, which shows that the two different methods produce
remarkably similar results, in fact an analysis of variance shows no significant difference
between the results. VDS-LCP is slightly slower on some models, but is able to solve 3 moremodels to feasibility than A-UP (it solves 91.5% of the models vs. 89.4% for A-UP). This showsthat a probability-based branching method that operates to force change is equivalent to thestate of the art branching method in seeking integer feasibility (which is itself based on theprinciple of branching to force change).

A-UP vs. VDS-LCP: All Models
1
0.9

Fraction of Models

0.8
0.7
0.6
0.5
0.4
0.3

GLPK Default

0.2

A-UP

0.1

VDS-LCP

0
1

2

3

4

5

6

7

8

9

10

Ratio to Fewest Simplex Iterations
Figure 12: A-UP vs. VDS-LCP

VDS-LCP actually outperforms A-UP on the subset of 47 equality-containing models, having 4
more fastest solutions and reaching integer feasibility within the time limit on 2 more models.
This raises the possibility of hybrid methods based on using VDS-LCP when there are equality
constraints in the model and A-UP otherwise; this is left for future research.
21

8. Branching Up Revisited
We now revisit the question of why branching up always is such a good heuristic, as shown in
Section 3. As will be seen, this is mainly due to the characteristics of the set of test MILPs.
Recall that branching up is always the best policy in a multiple choice constraint because thisforces all variables in the constraint to integrality simultaneously. As it happens, 104 of themodels in our test set contain at least one multiple choice constraint, versus just 38 without
multiple choice constraints. With almost three times as many models having multiple choice
constraints as not, it would be expected a priori that always branching up is a good policy. We
can examine this in detail by looking at how well the branching techniques work when themodel does or does not contain multiple choice constraints.
Figure 13 provides a performance profile for simplex iterations for the 104 models that include
at least one multiple choice constraint. Method A branching up provides the best performance,
followed by VDS-LCP, as expected.

At Least One Multiple Choice Constraint
1
0.9

Fraction of Models

0.8
0.7
0.6
GLPK Default

0.5

A-UP

0.4

VDS-LCP

0.3

A-LCP

0.2

A-LCPV

0.1

A-MVV

0
1

2

3

4
5
6
7
8
Ratio to Fewest Simplex Iterations

9

10

Figure 13: Models Having at Least One Multiple Choice Constraint

However, when there are no multiple choice constraints, the conclusion is a little different, asshown in Figure 14. Branching up exclusively is no longer the best policy: it is dominated byboth MVV and LCPV, both of which originate in the notion of branching to force change in thecandidate variable values.

22

No Multiple Choice Constraints

1
0.9

Fraction of Models

0.8
0.7
0.6
0.5

GLPK Default

0.4

A-UP

0.3

VDS-LCP
A-LCP

0.2

A-LCPV

0.1

A-MVV

0
1

2

3

4
5
6
7
Ratio to Fewest Simplex Iterations

8

9

10

Figure 14: Models Without Multiple Choice Constraints

It is interesting to analyze the behavior of the LCP heuristic on multiple choice constraints. LCP
always branches up on multiple choice inequality constraints. This is because all the variables
have the same set of possible values and the same coefficients, and hence the values calculated
in Eqns. 1 and 2 are always the same for a given number of candidate variables. Consider Table
5, which shows the cumulative probabilities of satisfying an inequality multiple choice
constraint when branching up or down. LCP, which chooses the lower cumulative probability,
will always choose to branch up, as shown in boldface.
# Variables Cumulative Probability Up Cumulative Probability Down
20.158655254
0.841344746
30.078649604
0.5
40.041632258
0.281851431
50.022750132
0.158655254
60.012673659
0.089856247
Table 5: Cumulative Probabilities for the Branching Direction in an Inequality Multiple Choice Constraint

The situation is a little different when the multiple choice constraint is an equality because now
Eqn. 3 is used, which measures the ratios of the cumulative probabilities. LCP chooses the
direction whose ratio is farthest from 1.0. As shown in Table 6, LCP will always choose tobranch up, except when there are two candidate variables, in which case there is no preference
for branching up or down, as shown in boldface. This is exactly as expected since in an equality
multiple choice constraint with two binary variables (x1 + x2 = 1), choosing to branch down will
force the other candidate variable to a value of 1, i.e. both variables will have integer values.
Hence when there are two candidate variables in an equality multiple choice constraint, bothcandidate variables are forced to integrality no matter which branching direction is chosen.
23

# Variables Equality Ratio Up Equality Ratio Down
20.188573417
0.188573417
30.085363401
1
40.043440797
0.392469529
50.023279749
0.188573417
60.012836343
0.098727533
Table 6: Cumulative Probability Ratios for the Branching Direction in an Equality Multiple Choice Constraint

9. Conclusions
This paper makes several useful contributions: The discovery of the principle that branching to force change in the candidate variables
results in faster achievement of integer feasibility in a MILP.
 The extension of probability-based branching methods for general mixed-integer
programming, most notably by the development of new methods for handling equality
constraints by assessing the "centeredness" of the constant value in the probability
distributions that result from branching up vs. branching down. As it turns out, theprobability-based branching methods are particularly effective on models having
equality constraints.
 The development of a number of useful new branching methods based on probability
methods and the principle of branching to force change. One of these methods (VDSLCP) chooses both the branching variable and the branching direction, and is as good as
the existing state-of-the art branching method (A-UP) which treats these two decisions
separately.
It is worth noting that the methods are unaffected by scaling. The MVV and MSV methods forinequality constraints use only the signs of the coefficients and not their magnitudes. All othermethods are based on probability calculations (including MVV and MSV for equality constraints)
which use only the lower and upper bounds on the variables and the coefficient values(Equations 1 and 2). Scaling will not affect the probability calculations and hence will not affectthe heuristics.
There is wide scope for future research to explore the full potential of these ideas: Hybrid methods. There is evidence that the presence or absence of equality constraints
and the presence or absence of multiple choice constraints impact the effectiveness ofthe branching methods. By observing which methods do best under which combinationof conditions, hybrid methods can be developed which apply the best method under thecurrent conditions. The decision as to which branching method to use can be madeonce at the beginning of the solution process after assessing the relevant factors, or canbe made at each node of the search tree.
 A number of combinations of the elements of the new methods were not assessed. For
example a new method for simultaneous variable and direction selection based on the
MVV method could be developed. This would assess the violation votes in the up and24

down directions for all candidate constraints and choose the variable and direction
having the most votes.
Dealing with ties for the selection of the branching variable and direction. When thesedecisions are made separately there are frequently numerous ties. For example Method
A for the selection of the branching variable simply counts the number of active
constraints that each candidate variable appears in, and ties are frequent. Using asecond method to break this tie may improve the results.

References
Abramowitz, M., and Stegun, I.A., eds. (1965), Handbook of Mathematical Functions, National
Bureau of Standards, Applied Mathematics Series, pp. 932.
Achterberg, T., Koch, T., and Martin, A. (2005), "Branching Rules Revisited", Operations
Research Letters 33:42-54.
Achterberg, T., Koch, T., and Martin, A. (2006), “MIPLIB 2003”, Operations Research Letters34:1-12.
Balas E., Ceria S., Dawande M., Margot F., Pataki G. (2001) "OCTANE: a New Heuristic for Pure
0-1 Programs", Operations Research 49:207-225.
Balas E., Martin C. (1986) "Pivot and Shift – a Heuristic for Mixed Integer Programming", GSIA
Technical Report, Carnegie Mellon University.
Bernatzki, K.P., Bussieck, M.R., Lindner, T., and Lübbecke, M.E. (1998), “Optimal Scrap
Combination for Steel Production”, OR Spektrum 20:251-258.
Bixby, R.E., Boyd, E.A., and Indovina, R.R. (1992), “MIPLIB: A Test Set of Mixed Integer
Programming Problems”, SIAM News 25(2), March 1992.
Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.P. (1998), “An Updated Mixed Integer
Programming Library: MIPLIB 3.0”, Optima 58:12-15.
Dolan, E.D., and Moré, J. (2002), “Benchmarking Optimization Software with Performance
Profiles”, Mathematical Programming, Series A 91:201-213.
Driebeek, N.J. (1966), “An Algorithm for the Solution of Mixed Integer Programming Problems”,
Management Science 12:576–587.
Fischetti M., Glover F., Lodi A. (2005) "The Feasibility Pump", Mathematical Programming A
104:91-104.

25

Jariwala A. (1995), “Efficient Branch and Bound Algorithm for the Dynamic Layout Problem”,
Master’s thesis, College of Engineering and Technology, Ohio University.
Johnson E.L., Nemhauser G.L., Savelsbergh M.W.P. (2000), "Progress in Linear-ProgrammingBased Algorithms for Integer Programming: An Exposition", INFORMS Journal on Computing
12:2-23.
Linderoth,J.,(2009),"Coral:Mixed
Integer
http://coral.ie.lehigh.edu/mip-instances/, accessed May 2009.

Programming

Instances",

Linderoth, J., and Ralphs, T. (2004), “Noncommercial Software for Mixed-Integer Linear
Programming”, Technical Report 04T-023, Department of Industrial and Systems Eng., Lehigh
Univ. Online: www.lehigh.edu/~jtl3/teaching/ie418/papers/MILP04.pdf.
Makhorin, A. (2008), “GNU Linear Programming Kit Reference Manual Version 4.28”,
http://www.gnu.org/software/glpk/, [Accessed May 2008].
Meyer, R.R., D’Souza,W.D., Ferris, M.C., and Thomadsen, B.R. (2003), “MIP Models and BB
Strategies in Brachytherapy Treatment Optimization”, Journal of Global Optimization 25:23–42.
Patel, J., and Chinneck, J.W. (2007), “Active-Constraint Variable Ordering for Faster Feasibility ofMixed Integer Linear Programs”, Mathematical Programming, Series A 110:445-474.
Pesant, G., and Quimper, C.G. (2008), “Counting Solutions of Knapsack Constraints”, CPAIOR
2008, Lecture Notes in Computer Science 5015:203–217.
Pryor, J. (2009), "Branching Variable Direction Selection in Mixed Integer Programming",
Master's thesis, Systems and Computer Engineering, Carleton University.
Tomlin, J.A. (1971), “An Improved Branch-and-Bound Method for Integer Programming”,
Operations Research 19:1070–1075.

26