Transcript entropy.ijcai07

Information-theoretic approaches to branching in search*
Andrew Gilpin and Tuomas Sandholm, CMU, CSD
*This was work was funded by, and conducted at, CombineNet, Inc., Fifteen 27th St., Pittsburgh, PA 15222.
Abstract
• Deciding what to branch on
at each node is a key element
of search algorithms
• We present four families of
methods for selecting what
question to branch on
• Each is informationtheoretically motivated to
reduce uncertainty in
remaining sub-problems
• Experiments demonstrate
improvement over state-ofthe-art
Motivation
Strong branching[2]
• Tie-breaking
• Use SB, EB to break ties
• Can consider “close” ties
• Combinational
• Convex combination
• Combining ranks of each
• Since strong branching and
entropic branching are such
similar computations, there is no
overhead for combining
Branching on multiple
variables
• Generalizes one-step look-ahead
on individual variables
• Given a set X := {x1,…,xn} of
variables, let k := floor(x1+…+xn)
• We can generate these branches:
x1+…+xn ≤ k and x1+…+xn ≥ k+1
• This is the only value of k worth
consider: all others lead to one
child being the same
• Can skip evaluation of sets where
their fractional sum is already
integral
• Let X be a binary random variable
with events A and B
• Let p be the probability of A and 1-p
the probability of B
entropy(X) := -p log2 p – (1-p) log2 (1-p)
• Beginning of search: total uncertainty
about optimal solution
• End of search: zero uncertainty about
optimal solution
• Idea: Measure uncertainty and drive the
search to minimize this uncertainty quickly
1. Let w be fractional sol’n at current node:
w := argmin {c’w : Aw ≤ b}
2. Let C := {c1,…,cn} be index set for n fractional
variables (the candidates)
3. For each i in C:
a. xi,l := argmin {c’x : Ax ≤ b, xci ≤ floor(wci)}
b. xi,r := argmin {c’x : Ax ≤ b, xci ≥ floor(wci) + 1}
4. Branch on variable
j := mini max {c’xi,l, c’xi,r}
Combining strong branching
and entropic branching
Information theory and
entropy
• Integer programming problem:
x*=argmin {c’x : Ax ≤ b, xi integer}
• Integer programs are at the center of
many multi-agent systems (combinatorial
market clearing, equilibrium computation)
• These problems are usually solved using
algorithms based on branch-and-bound
• Entropy is additive for independent
random variables
• Big assumption: treat variables as
independent random variables
Entropic branching
1. Let w be fractional sol’n at current node:
w := argmin {c’w : Aw ≤ b}
2. Let C := {c1,…,cn} be index set for n fractional
variables (the candidates)
3. For each i in C:
a. xi,l := argmin {c’x : Ax ≤ b, xci ≤ floor(wci)}
b. xi,r := argmin {c’x : Ax ≤ b, xci ≥ floor(wci) + 1}
4. Branch on variable
j := mini max {entropy(xi,l), entropy(xi,r)}
IEB experimental results
Indicator entropic
branching (IEB)
Combinatorial procurement
• M = {1,…,m} goods to procure
• S = {1,…,s} suppliers
• B = {1,…,n} bids, indicating bundle,
price from a supplier
• Buyer specifies max number of
winning suppliers K
• Want min cost allocation satisfying
max supplier constraint
• NP-complete, even if bids on single
items only[3]
Branching strategy
• Integer programming methods
have been successful in clearing
combinatorial markets[1], but still
need to be improved
• Natural formulation of above
problem contains an indicator
variable for each supplier
• For each supplier, compute the
entropy on that supplier’s bids
• Strategy: Branch on the indicator
variable for the supplier having the
greatest entropy
s
CPLEX
CPLEX-IF IEB
20 10 10 100 5
r
m
b
k
25.63
15.13
30 15 15 150 8
5755.92 684.83
40 20 20 200 10 37.05%
32.38%
11.81
551.82
30.57%
s:suppliers, r:regions, m:items/region,
b:bids/region, K:max suppliers
Solution time for complete search (third row
indicates gap after 1 hour)
1.
2.
3.
Selected bibliography
Arne Andersson, Mattias Tenhunen, and Fredrik
Ygge. Integer programming for auctions with bids
for combinations. In Proc. 4th International
Conference on Multi-Agent Systems (ICMAS-00),
2000.
David Applegate, Robert Bixby, Vasek Chv´atal,
and William Cook. The traveling salesman problem.
Technical report, DIMACS, 1994.
Tuomas Sandholm and Subhash Suri. Side
constraints and non-price attributes in markets. In
IJCAI-2001 Workshop on Distributed Constraint
Reasoning, Seattle, WA, 2001.