TECHNICAL REPORT

arXiv:1008.3551v1 [cs.CE] 20 Aug 2010

YL-2010-004

INVENTORY ALLOCATION FOR ONLINE GRAPHICAL DISPLAY
ADVERTISING

Jian Yang
Erik Vee
Sergei Vassilvitskii
John Tomlin
Jayavel Shanmugasundaram
Tasos Anastasakos
Yahoo! Labs
701 First Ave
Sunnyvale, CA 94089
{ jianyang, erikvee, sergei, tomlin, jaishan,
tasos}@yahoo-inc.com
Oliver Kennedy
Computer Science Department
Cornell University
Ithaca, NY 14840
okennedy@cs.cornell.edu

Bangalore • Barcelona • Haifa • Montreal • New York
Santiago • Silicon Valley

Yahoo! Labs Technical Report No. YL-2010-004

Yahoo! Labs Technical Report No. YL-2010-004
INVENTORY ALLOCATION FOR ONLINE GRAPHICAL DISPLAY
ADVERTISING

Jian Yang
Erik Vee
Sergei Vassilvitskii
John Tomlin
Jayavel Shanmugasundaram
Tasos Anastasakos
Yahoo! Labs
701 First Ave
Sunnyvale, CA 94089
{ jianyang, erikvee, sergei, tomlin, jaishan, tasos}@yahoo-inc.com
Oliver Kennedy
Computer Science Department
Cornell University
Ithaca, NY 14840
okennedy@cs.cornell.edu
ABSTRACT: We discuss a multi-objective/goal programming model for the allocation
of inventory of graphical advertisements. The model considers two types of campaigns:
guaranteed delivery (GD), which are sold months in advance, and non-guaranteed delivery
(NGD), which are sold using real-time auctions. We investigate various advertiser and
publisher objectives such as (a) revenue from the sale of impressions, clicks and conversions,
(b) future revenue from the sale of NGD inventory, and (c) “fairness” of allocation. While
the first two objectives are monetary, the third is not. This combination of demand types
and objectives leads to potentially many variations of our model, which we delineate and
evaluate. Our experimental results, which are based on optimization runs using real data
sets, demonstrate the effectiveness and flexibility of the proposed model.

1

Yahoo! Labs Technical Report No. YL-2010-004
1.

Introduction

Online graphical display advertising is a form of online advertising where advertisers
can explicitly or implicitly target users visiting Web pages, and show graphical (e.g., image,
video) ads to those users. For instance, a brokerage firm may wish to target Males from
California who visit a Finance web site in the month of November 2010, and show an ad
promoting its special offers to those users. Similarly, a different advertiser may wish to
automatically target users who visit a Finance web site, specifically those who are likely to
click on their ad highlighting a lower mortgage rate. Online graphical display advertising is
a multi-billion dollar industry that is related to, but distinct from, sponsored search advertising [2], where advertisers bid for keywords entered by users on a search page, and from
content match advertising [8], where advertisers bid for clicks and text-matching techniques
(as opposed to user targeting) are used to show contextually relevant text advertisements
on Web pages.
As with most forms of online advertising [7], one of the central questions that arises in
the context of online graphical display advertising is that of inventory allocation, i.e., determining how to allocate supply/inventory (user visits) to demand (advertiser campaigns) so
as to optimize for various publisher and advertiser objectives. However, even formulating
the inventory allocation problem for online graphical display advertising is quite challenging,
for two reasons.
First, the same inventory can be sold in two different forms: guaranteed delivery and nonguaranteed delivery. In guaranteed delivery, an advertiser can purchase a certain number of
targeted user visits from a publisher several months in advance, and the publisher guarantees
these visits and incurs penalties if the guarantees are not met. For instance, an advertiser
may wish to purchase 100 million user visits by Males in California on a Sports web site
during Superbowl 2011, and the Sports web site publisher will guarantee these user visits
even though the serving date is months away from the booking date. On the other hand, in
non-guaranteed delivery, advertisers can bid in real-time in a spot market for user visits, and
the highest bidder obtains the right to show an ad to the user. For instance, if a user visits a
Finance web page, then there may be multiple advertisers bidding for the ad slot on the page,
and the highest bidder can show an ad to the user. An interesting aspect is that the same
user visits are eligible for both guaranteed delivery and non-guaranteed delivery. A typical
use case is that some inventory not fully allocated to guaranteed campaigns can be sold to
non-guaranteed campaigns. However, not all visits from this inventory will fetch the same
price in the spot-market. This leads to the first question addressed by this work: How does
a publisher allocate inventory to both guaranteed and non-guaranteed advertising campaigns,
while still ensuring that the guaranteed advertiser objectives are met, and publisher revenue
is maximized?
Second, unlike sponsored search and content match advertising, where the goals of advertisers are to obtain clicks/ conversions on ads, the goals of advertisers in online graphical
display can be quite varied. At one end of the spectrum are brand advertisers (e.g., major department stores), whose primary goal is to reach a large and diverse audience and
2

Yahoo! Labs Technical Report No. YL-2010-004
promote their brand, rather than immediate clicks or purchases. At the other end of the
spectrum are performance advertisers (e.g., credit card companies), whose primary goal is
to obtain immediate online clicks and conversions. In the middle, there are performancebrand advertisers (e.g., car companies), whose goal is both to promote the brand, as well as
to obtain immediate leads of users who are in the market to buy a car. The varied goals of
advertisers also lead to multiple currencies by which graphical display advertisements are
bought: brand advertisers typically buy impressions (expressed in CPM, or Cost Per Mille
(1000 impressions)), while performance advertisers typically pay per click (CPC or Cost
Per Click) or conversion (CPA, or Cost Per Action), while brand-performance advertisers
may use a combination of CPM and CPC/CPA. Thus, the second question we address is:
How does a publisher allocate inventory across diverse advertisers and payment types so
that advertiser and publisher objectives are met?
1.1.

Contributions

Given the aforementioned unique requirements for online graphical display advertising,
one of the main technical contributions of this paper is an inventory allocation optimization
model that can capture these requirements. At a high-level, the proposed allocation model
represents forecasts of future inventory (user visits) and guaranteed advertiser campaigns
as nodes in a bipartite graph. Each edge of the bipartite graph connects a user visit to an
eligible guaranteed advertiser campaign. In addition, each user visit is annotated with a
forecast of the highest bid fetched on the non-guaranteed marketplace and a forecast of the
expected pay-out. Similarly, each edge of the graph is annotated with a forecast of the click
or conversion probability for the advertiser campaign and the specific user visit.
Given the previous model, the objectives for online graphical display advertising are
captured as follows. There are two parts to the objective function: one that captures guaranteed campaigns, and the other that captures non-guaranteed campaigns. The objective
for the latter is simply to maximize the revenue for the publisher, since advertisers only bid
for what the user visit is worth to them. The objective for the guaranteed campaigns, on
the other hand, is more complex because advertisers could be interested in brand awareness,
or performance, or both. Furthermore, the publisher faces penalties for under-delivering –
that is displaying an advertisement to fewer users than agreed on.
In our model, delivery guarantees are treated as feasibility constraints. (If the instance is
infeasible, we trim the demand to find the feasible solution with the minimum under-delivery
penalties.) The objective for guaranteed contracts has two parts. The brand awareness
objective is captured in terms of “representativeness” (see [15]), which tries to maximize
the reach of the guaranteed campaign by uniformly distributing the contracts among the
user visits to the extent possible 1 . The performance objectives for guaranteed campaigns
are captured as the expected pay-out, i.e., the probability of clicks and conversions, times
the value of each click and conversion.
1

Reach can also be specified in terms of users as opposed to user visits (as above) by using user cookie
information, but we do not elaborate on this extension here

3

Yahoo! Labs Technical Report No. YL-2010-004
Consequently, the final allocation objective has three parts: non-guaranteed revenue,
guaranteed representativeness, and guaranteed clicks/conversions. While multi-objective
programming has been a standard technique for some time, previous optimization models
for online advertising (see e.g. [17, 18]) have used a single objective function. One of our
major contributions is to use the multi-objective optimization framework [24] to model the
sometimes conflicting objectives in a rigorous way.
While the multi-objective optimization model described above captures the various objectives, it also introduces a new set of challenges both in terms of operability and in terms
of computational feasibility. Specifically, with regard to operability, the question that arises
is: how do we trade-off between the various objectives (such as representativeness and nonguaranteed revenue), which do not even have the same units? With regard to computational
feasibility, the question that arises is: how do we solve a multi-objective formulation efficiently over large volumes of data (tens of billions of user visits per day and hundreds of
thousands of advertiser campaigns per year)? Another key technical contribution of this
paper is a method that enables operators of the system to trade-off between multiple objectives based on the monetary unit of a single objective. For instance, an operator can
trade-off representativeness in terms of the impact it has on non-guaranteed revenue, which
is expressed in monetary units. A significant advantage of this method is that it also allows
for an efficient solution, which can be solved on a small sample of the original bipartite
graph, without significantly compromising accuracy.
We note that there are two other closely related topics that impact inventory allocation:
pricing and ad serving. While the details of these methods are beyond the scope of this
paper, the proposed allocation method works with quite general pricing and ad serving
techniques. Specifically, in terms of pricing, we assume that guaranteed campaigns are
priced using some external method (which may itself use forecasts of non-guaranteed bids
to ensure appropriate prices), and the inventory allocation model can work with the booked
prices without regards to how exactly the prices were computed. Similarly, we assume that
we have some forecast of non-guaranteed bids, but do not make any assumptions on how
the bids by themselves are generated by individual campaigns. In terms of ad serving, the
allocation model produces both a primal and dual solution, the latter of which can be stored
compactly and interpreted by the ad server to serve ads to user visits in an online, real-time
manner (e.g., see [10, 26]).
We have implemented the proposed inventory allocation model and the solution techniques, motivated by the context of an operational online graphical display advertising
system. Our results using real user visits, guaranteed campaigns, non-guaranteed bids, and
click/conversion data, indicate that the proposed approach is both versatile in capturing
and trading off between various advertiser and publisher objectives, as well as efficient to
solve with high accuracy.
In summary, the main contributions of this paper are:
• A formalization of the inventory allocation model and objectives for online graphical
display advertising (Section 2).
4

Yahoo! Labs Technical Report No. YL-2010-004
• A multi-objective optimization formulation and various solution techniques for optimizing the multiple objectives (Section 3).
• An experimental evaluation of the proposed techniques using real data sets (Section 4).

2.

Model and Objectives

We begin by first defining some notation, and then motivating and formalizing the
various objectives in online graphical display advertising.
2.1.

Supply and Demand Model

As mentioned earlier, the main goal of inventory allocation is to match supply (user
visits) and demand (advertising campaigns). We thus begin by modeling user visits, advertising campaigns, and their interaction.
User visits can be represented as attributes-value pairs, where the attributes represent
the properties of a user, the properties of the page they visit, as well as the time stamp
of the visit. An example user visit could be represented as: Gender = Male, AgeGroup =
30-40, Interests = {Sports, Finance}, Location = California, ..., PageCategory = {Sports},
..., Day = 15 Jan 2011, Time = 12:35pm GMT.
A display advertising campaign targets a subset of user visits by specifying a targeting
predicate. For instance, an advertising campaign that targets Males in California visiting
Sports pages in the month of Jan 2011 can be represented as: Gender ∈ {Male} ∧ Location
∈ {California} ∧ PageCategory ∈ {Sports} ∧ Duration ∈ [1 Jan 2011 - 31 Jan 2011]. A
user visit is said to be eligible for an advertising campaign if the attribute-value pairs of
the user visit satisfy the targeting predicate of the advertising campaign. In the rest of this
paper, we will focus on just the eligibility relationship between user visits and advertising
campaigns, and not on the specific attribute-value pairs or the targeting predicates.
Advertising campaigns can be of two types: guaranteed campaigns, whereby the publisher guarantees a fixed number of user visits to an advertiser in advance, and nonguaranteed campaigns, where advertisers bid in real-time for user visits. Both guaranteed
and non-guaranteed campaigns can have one or more advertiser goals: to obtain user visits (this is the only goal that is guaranteed in a guaranteed campaign), to obtain clicks,
and/or to obtain conversions. In non-guaranteed campaigns, however, these objectives are
converted into a bid by a bidding agent and thus, for the purpose of modeling, they can be
represented as a bid for each user visit. Guaranteed campaigns, on the other hand, need
to be modeled in more detail. Specifically, a guaranteed campaign has a user visit goal
(the guarantee), a penalty function that specifies the penalty to be paid by the publisher if
the guarantee is not met, and a value for each click and/or conversion. A key aspect that
enables yield optimization for clicks and/or conversions is the probability of a click and/or
conversion given a user visit.

5

Yahoo! Labs Technical Report No. YL-2010-004
Finally, for reasons of scale, it is usually not practical to work with all future user visits
for a duration of many months (many large publishers have billions of impressions per day).
Consequently, the inventory allocation problem often has to be solved on a sample of user
visits, and thus each sampled user visit is annotated with a sample weight.
The following notation summarizes the above discussion:
• I: Set of user visits
• si : Sample weight of user visit i ∈ I
• ri : The payout for user visit i ∈ I by non-guaranteed campaigns
• J : Set of guaranteed campaigns
• dj : User visit goal for guaranteed campaign j ∈ J
• Pj : N → R: Penalty function for guaranteed campaign j ∈ J , which maps underdelivery (how much a guarantee is missed) to a penalty.
• Wjc : The value of a click for a guaranteed campaign j ∈ J
• Wja : The value of a conversion (action) for a guaranteed campaign j ∈ J
• pcij : The probability that a user corresponding to user visit i ∈ I clicks on an ad
corresponding to guaranteed campaign j ∈ J
• paij : The probability that a user corresponding to user visit i ∈ I converts on an ad
corresponding to guaranteed campaign j ∈ J
• Bj : Set of user visits ∈ I that are eligible for guaranteed campaign j ∈ J .
It is often convenient to view the user visits and guaranteed campaigns in a bipartite
graph, with user visits I on one side, guaranteed campaigns, J on the other, and an edge
(i, j) between a user visit i and a guaranteed campaign j if i ∈ Bj , that is if i satisfies the
targeting predicates of j. An example of such graph is shown in Figure 1.
It should be noted that the construction of this graph, which may involve tens of thousands of nodes and millions of edges, is in itself a major computational task.
2.2.

Objectives

In this section, we motivate and formalize the various objectives that are relevant to the
inventory allocation problem. In the next section, we introduce a mathematical model to
trade-off and optimize across these different objectives.
An overriding objective of publishers is to minimize the penalties incurred in case guarantees are not met. Minimizing penalties is important because the publisher not only incurs
an immediate monetary loss, but also because the publisher could suffer longer-term losses

6

Yahoo! Labs Technical Report No. YL-2010-004

Supply:
ad opportunities

Demand:
contracts

Figure 1: Example of the allocation graph.
due to advertiser attrition. Define yij as the weight of user i ∈ I that is allocated to guaranteed
P campaign j ∈ J . Then the amount of user visits delivered to a guaranteed campaign
j is i yij , and the objective of minimizing penalties can be formalized as:
X
X
min
Pj (dj −
yij )
(1)
j

i

However, in this paper we avoid this issue by ensuring feasibility of the constraints (see
section 3.1).
At a high-level, there are two parts to the inventory allocation problem, corresponding
to non-guaranteed and guaranteed campaigns. The objective for non-guaranteed campaigns
is simple: to maximize the revenue for the publisher, since advertisers only bid what each
user visit is worth to them. Modeling the objectives for guaranteed campaigns, on the other
hand, is more complex because advertisers could be interested in brand awareness/reach or
performance (clicks, conversions) or both. We thus have three objectives: non-guaranteed
revenue, brand awareness/reach, and performance.
Before formalizing the above objectives, we introduce some notation:
P
• zi = si − j yij : The weight of user visit i ∈ I that is allocated to non-guaranteed
campaigns
P
• Sj = i∈Bj si : The total amount of user visits eligible for guaranteed campaign j ∈ J
d

• θij = si Sjj : The ideal fully representative target allocation fraction of user visit i ∈ I
to guaranteed campaign j ∈ J (motivated further below)
2.2.1. Non-Guaranteed Revenue The prices paid by non-guaranteed advertisers depend heavily on the particular user. Therefore, a natural goal of an allocation is to maximize
7

Yahoo! Labs Technical Report No. YL-2010-004
the publisher’s revenue by allocating the highest valued user visits to the non-guaranteed
contracts. Since the amount of revenue that a publisher obtains from a user visit i is ri zi ,
this objective is written as:
X
max
ri zi
(2)
i

2.2.2. Brand Awareness/Reach There are two primary reasons why it is important
to have a brand awareness/reach objective. The first reason is that brand advertisers typically want to reach a large swath of their target audience. For instance, a brand advertiser
who targets user visits from the US will likely be quite unhappy if all of their delivered user
visits are from fourteen year old males in Wyoming, and none from the rest of the population (even though all the delivered user visits technically satisfy the targeting predicate
of the advertiser). In other words, brand advertisers often want a representative subset of
their target audience2 .
The second reason for having a brand awareness and reach objective is more subtle, and
it relates to the interaction with non-guaranteed campaigns. Specifically, if the primary goal
of the publisher was to maximize short-term revenue, then he could allocate all of the highvalue impressions to the highest bidding non-guaranteed campaigns, and allocate only the
remaining impressions to the guaranteed campaigns. However, this is clearly detrimental
to the advertiser, and is also a dangerous road to take for the publisher: by selectively
allocating the most expensive user visits to the non-guaranteed contracts, the publisher
risks alienating in the long term the guaranteed advertisers, many of whom pay a large
premium for guarantees. In fact as Ghosh et al. [15] recently argued, in these situations
price serves as a signal of value, thus the user visits with the highest ri may also be the
ones most desired by the guaranteed contracts.
Therefore, it is in the long-term interests of publishers to allocate each guaranteed
campaign a representative sub-set of targeted user visits. Ideally, every eligible user visit
i ∈ Bj should be equally likely to see an ad from j. A similar argument holds on a temporal
scale. A week long contract should have the same probability of being displayed on all days
of the week. That is, it should be allocated uniformly during the course of the week—after
all, if an advertiser wanted the contract to be shown only on Tuesday, she would have added
that to the targeting constraints.
To model these representativeness constraints, let θij be the ideal target allocation.
Note that θij directly encodes the fact that no user visit i is preferred by j over others. To
maximize long term revenue, the publisher should strive to find an allocation close to θij .
In this paper we use the L2 -norm distance to measure closeness to the target allocation.
We denote Vj the importance of a representative allocation to advertiser j and write the
2
Advertisers could potentially control their target allocation (other than uniformly at random) more
closely if they desire, at the cost of targeting more defined, and therefore likely more expensive, inventory

8

Yahoo! Labs Technical Report No. YL-2010-004
objective as:
min

X X Vj
(yij − θij )2
2θij
j

(3)

i∈Bj

For consistency with other objectives, we will use the maximization form:
max −

X X Vj
(yij − θij )2
2θij
j

(4)

i∈Bj

Note that alternative forms such as an entropy function or K-L divergence can also
be used, as they retain the essential features of separability (by advertiser) and convexity.
Similarly, other target allocations besides the perfectly uniform target allocation can also
be considered but these variants are beyond the scope of this paper.
2.2.3. Clicks/Conversions for Guaranteed Campaigns An advertiser in a guaranteed campaign may have multiple objectives, such as clicks and conversions, besides
obtaining the guaranteed user visits. The publisher’s objective is to maximize the yield
from such goals, while also directing such clicks and conversions to the advertisers who
value them the most. This can be modeled as trying to maximize the expected value of
clicks and conversions across all user visits:
XX

Wjc pcij yij + Wja paij yij
j

i∈Bj

For compactness we define:
wij = Wjc pcij + Wja paij .
Then we can rewrite the performance objective as:
XX
wij yij .
max
j

(5)

(6)

i∈Bj

Note that when we refer to “clicks” below, it is to be understood to include the subsequent
conversions.
3.

The mathematical models

In the previous section we described the competing objectives faced by a publisher in
allocating user visits to guaranteed contracts. In this section we formally state the mathematical problem that incorporates these objectives subject to the feasibility constraints.
There are three types of constraints that the allocation must satisfy to be feasible. First,
the desired number of user visits must be allocated for each guaranteed contract:
X
yij = dj (Demand Constraints)
∀j
i∈Bj

9

Yahoo! Labs Technical Report No. YL-2010-004
Next, each user visit can be allocated to exactly one guaranteed or non-guaranteed contract.
X
yij + zi = si (Supply Constraints)
∀i
j|i∈Bj

Finally, we must ensure that the allocation is always non-negative.
yij ≥ 0 (Non-Negativity Constraints)
zi ≥ 0

∀i, j

∀i

Putting together the objectives from the previous section with the set of constraints, we
may state our generic multi-objective optimization:

 P P
V
− j i∈Bj 2θjij (yij − θij )2
P P


(7)
max 

j P
i∈Bj wij yij
i ri zi
subject to

P

j|i∈Bj

P

yij + zi = si ∀i

(8)

∀j

(9)

i∈Bj

yij = dj

yij ≥ 0

∀i, j

(10)

zi ≥ 0

∀i

(11)

Note that the non-negative variables zi transform what would be inequality supply
constraints into equalities. Since zi is actually the leftover
P supply inventory that will be
sold to the non-guaranteed delivery spot market, the term i ri zi can be viewed as the total
non-guaranteed revenue that can be obtained for an allocation y, with remnant inventory z.
The second objective is the revenue obtained from clicks on the displayed advertisements.
3.1.

Ensuring feasibility

In this model formulation, guarantees are treated as constraints (Demand Constraints).
Consequently, before we optimize for the other objectives, we need to ensure that the
model is feasible, i.e., there is sufficient supply for guaranteed campaigns. Note that even if
a publisher is careful to accept only guaranteed campaigns that are feasible at the time of
booking, the model could become infeasible at a later point because forecasts of user visits
could change due to unforeseen events.
In order to make the model feasible, we add dummy user visits that have unlimited
supply but a very high cost of being used, and connect them to all the guaranteed campaigns. The cost associated with using each dummy user visit for a guaranteed campaign j
corresponds to the penalty Pj > 0 incurred by that guaranteed campaign in case of underdelivery (note that if Pj has multiple penalty values for under-delivery, then these can be
10

Yahoo! Labs Technical Report No. YL-2010-004
represented as multiple dummy user visits, each with a different cost of being used). The
cost associated with using real user visits is 0.
Given the above set up, the goal is to find the minimum cost allocation to guaranteed
campaigns. Since this problem is a pure network with a linear objective function, it can be
solved very efficiently [4]. If the cost of the optimal allocation is 0, then it implies that all
the guaranteed campaigns can be satisfied, and hence that the original model is feasible. If
the cost of the optimal allocation is greater than 0, then it implies that some guaranteed
campaigns will under-deliver. Furthermore, the optimal allocation to the dummy user visits
will indicate how much each guaranteed campaign needs to under-deliver so that overall
penalty cost is minimized. In this case, the user visit goal dj for each guaranteed campaign
is reduced by the amount of allocation to the dummy user visits in order to make the model
feasible. We then follow one of the procedures described in the remainder of this section.
3.2.

Multi-objective programming

We may approach a multi-objective function model in a number of ways (see [24]).
One general approach is to obtain an “efficient frontier” of solutions where at each point
on the curve the value of one objective can only be improved at the expense of degrading
another (see the generic example in Figure 2, where we notionally trade off total revenue and
“representativeness”). The user may then choose any point on this curve as the “solution”.

Figure 2: Efficient Frontier
More algebraic approaches include using a weighted sum of the multiple objectives
and/or using “goal programming”, whereby the objectives are handled sequentially, with
11

Yahoo! Labs Technical Report No. YL-2010-004
the additional constraint(s) that previous objectives retain a certain fraction of their optimal
value. Since we have three objectives here there are clearly several variations, which we
explore below.
In what follows, it will be convenient to define the 3 objective components as follows:
X X Vj
(yij − θij )2
2θij
j i∈Bj
XX
F2 (y) =
wij yij
F1 (y) = −

F3 (z) =

j

i∈Bj

X

ri zi

(12)
(13)
(14)

i

Depending on the data available, we may formulate solution strategies which employ:
1. A single parametrized objective function.
2. A two-objective function model in various flavors
3. A three-objective function model, also in several flavors.
3.3.

Single objective

We consider a multi-component objective function:
max {γF1 (y) + ξF2 (y) + F3 (z)}

(15)

subject to (8)-(11)
The parameter γ ≥ 0 is the weight for the “representativeness” component. The parameter ξ, in conjunction with the wij reflects the means by which we attribute value to
clicks. We observe that a feature of this model is that the shadow value βi of the supply
constraint i is always no less than the reserve price, i.e. βi ≥ ri .
Here, we assume that a value of γ is available, from either historical data or business
considerations. We consider explicitly two cases for the value of ξ:
• The values of the wij are computed via (5) with Wjc = Wja = 1. Then ξ is the value
of a click relative to a unit of revenue from the objective F3 (z).
• The wij are actual expected monetary value of allocating an impression of type i to
contract j, in which case ξ = 1.
In both cases, the model involves the addition of a linear term in y to the strictly convex
distance function F1 (y). The objective thus remains strictly convex quadratic in y and
linear in z. Optimization of this model is straightforward in principle, using a commercial
solver such as XpressMP [27]. If a sufficiently powerful large-scale nonlinear network code
were available, this could also be used since our constraints are of the pure network type.
12

Yahoo! Labs Technical Report No. YL-2010-004
3.4.

Two objectives

If all of the above data are not available to us, we must resort to multi-objective or goal
programming. Let us first assume that γ is not known, but the click-related data (ξ, wij )
are available. In this case, we may initially solve:
max {ξF2 (y) + F3 (z)}

(16)

subject to (8)-(11). Note that this is a linear pure network minimum cost flow problem
which can be solved very rapidly by special purpose software (e.g., see Bertsekas [4]). Let
the optimal value of this linear program (LP) be M ∗ .
We may now append a constraint specifying that at least a certain fraction ψ (0 < ψ < 1)
of this monetary value be preserved and solve the model:
max F1 (y)

(17)

X

(18)

subject to (8)-(11) and
ξ

XX
j

wij yij +

ri zi ≥ ψM ∗

i

i∈Bj

It may be shown (see Appendix) that the unknown parameter γ is equal to the inverse of
the dual value for the constraint (18).
Suppose now that a value for γ is available but ξ is not. We may initially solve
max F2 (y)

(19)

subject to (8)-(11). Let the optimal value of this linear program (LP) be P ∗ . We may
now append a constraint specifying that at least a certain fraction ω of this “click value”
(however it is quantified) be preserved, and solve the model:
max {γF1 (y) + F3 (z)}

(20)

XX

(21)

subject to (8)-(11) and
j

wij yij ≥ ωP ∗

i∈Bj

The third variant combines the two objectives F1 and F2 in the second stage model, after
solving a first stage model:
max F3 (y)
(22)
subject to (8)-(11). Since this is also a linear pure network minimum cost flow problem is
can be solved very rapidly by special purpose software. Let the optimal value of this linear
program be R∗
In this approach, the second model is of the form:
max {γF1 (y) + ξF2 (y)}
13

Yahoo! Labs Technical Report No. YL-2010-004

subject to (8)-(11) and

X

ri zi ≥ ηR∗

(23)

i

where η (0 < η < 1) is the fraction of NGD revenue we wish to preserve.
This model would require us to have the relative weights on F1 and F2 available. This
model is also guaranteed to be feasible if the original constraints (8)-(11) are feasible.
3.5.

Three objectives

From an operability point of view, it is unlikely that both the parameters γ and ξ
would be known, or even understood very well. In that case, we cannot avoid turning to
goal programming and the use of more intuitive “knobs” for the business to use in the
decision making process. Our goal program reduces to a sequence of three models. In
principle, these models could be solved in any order, but we take the point of view that the
nonlinear objective F1 (y) should be optimized last, in order to avoid imposing a nonlinear
constraint. Such a non-linear constraint would be computationally crippling at the scale
we are contemplating. The last model therefore must optimize representativeness subject
to constraints on non-guaranteed revenue and click value.
We again emphasize that, given appropriate wij , these last two quantities can reasonably
be thought of in monetary terms, whereas F1 may not.
Since non-guaranteed revenue is undeniably monetary, the most intuitive procedure
might be to first solve for F3 , i.e. solve the problem (22) and then solve for maximum click
value:
max F2 (y)
(24)
subject to (8)-(11) and
X

ri zi ≥ ηR∗

(25)

i

where η, R∗ are as defined in constraint (23). Let the optimum objective function value be
P ∗∗ .
We may now optimize the representativeness function F1 (y) subject to (8)-(11) and
X
ri zi ≥ ηR∗
(26)
i

XX
j

wij yij ≥ ωP ∗∗

(27)

i∈Bj

Clearly we could reverse the first two steps. This would likely produce different results,
but both would be feasible.
There is however a severe computational disadvantage to this 3 step process. While step
1 is a pure network optimization model, the second step involves a side constraint (23) or
(21) which destroys the orders of magnitude speed advantage of pure network optimizers
14

Yahoo! Labs Technical Report No. YL-2010-004
over general LP solvers. In an effort to avoid this, we might omit the side constraint from
the second model, leaving it a pure network model. However there is now no guarantee
that the third model, incorporating (26), will be feasible. We might then relax the side
constraints until feasibility is obtained, but rigor is lost.
4.

Experiments

We now present some experimental results using a snapshot of real online graphical
display advertising data sets. The main goal is to quantify the benefits of the multi-objective
optimization approach proposed in this paper as compared to the more traditional singleobjective optimization approaches. We note that our specific focus is on quantifying the
relative benefits of the various optimization approaches for a given data/forecast snapshot,
and not on online ad serving mechanisms (e.g., [10, 26]) that account for forecast errors,
and could use periodic re-optimization.
4.1.

Experimental setup

The data snapshot consists of guaranteed campaigns, forecasts of user visits, nonguaranteed bids and clicks, all based on a subset of historical data from an operational
display advertising system. The generated optimizer graph has 32,390 supply nodes, 2,696
demand nodes and 1,407,753 edges. The supply weight (si ) ranges from 10.83 to 1.18 × 109 .
The user visit goal (dj ) ranges from 1 to 6.96 × 107 . The non-guaranteed price (ri ) ranges
from 0.046 to 4.350. The click probability (pcij ) ranges from 1.290 × 10−6 to 0.947 (the
experiments only evaluate clicks, not conversions).
Figure 3 shows the experimental flow based on the data snapshot. The first step is to invoke the User Visit Forecasting module to generate a forecast of user visits that correspond
to the guaranteed campaigns, and construct the allocation graph. The next two (parallel)
steps are to invoke the Non-Guaranteed Forecasting and Click Forecasting modules to annotate the allocation graph with the non-guaranteed revenue information (ri ) and the click
probabilities (pcij , respectively. The final step is to run the Optimizer to solve the various
optimization methods proposed in the paper.
The metrics that we measure for the various optimization runs are the non-guaranteed
revenue, the total value of clicks, and the representativeness of guaranteed campaigns. The
experiments are run for various values of the model parameter settings. For the experiments,
all the allocation priorities Vj are set to 1 and all the click values Wjc are set to 10.
The experiments were run on a 64bit/64GB/2GHz Linux box using the optimization
package Xpressmp3 [27].
3

Recently acquired by Fair Isaac (FICO)

15

Yahoo! Labs Technical Report No. YL-2010-004

Optimized
Allocation

Optimization
Annotated
Allocation
Graph

Click
Forecasting

Non-Guaranteed
Forecasting
Allocation
Graph

User Visit
Forecasting
Guaranteed
Campaigns

Campaign
Database

Figure 3: Experiment Flowchart
4.2.

Forecast models

Although the forecast models used here are not the focus of this paper, we include a
brief description of each for completeness.
4.2.1. Supply Forecasting User visit forecasting uses time-series trend predictions to
predict the trend/growth in user visits for various pockets of supply such as Sports or
Finance. Our specific implementation uses SARIMA [23] for time-series predictions.
In addition, to generate the allocation graph, we need to produce a sample of user
visits. For this, we follow the sampling procedure outlined in Vee et al [26], which produces
a unbiased sample for the class of optimization models that we consider in this paper.
Specifically, for each guaranteed campaign, the supply forecast selects k eligible user visits
uniformly at random. Once all of the user visits for all campaigns are chosen, the weights
given to each user visit is normalized so that the total weight of any subset of user visits is
— in expectation — equal to the predicted available supply. The allocation graph is then
created by adding edges from the campaigns to their eligible user visits.
4.2.2. Non-Guaranteed Forecasting The goal of the Non-Guaranteed Forecasting
module is to predict the expected revenue obtained by selling a particular user visit in the
non-guaranteed marketplace. We observed that the prices paid for ad opportunities by the
non-guaranteed contracts followed a log normal distribution, with prices ranging from under
$0.10 CPM to above $10 CPM. To predict the price of an individual user visit, we trained
a generalized least squares regression model on the logarithm of the prices. Each user visit
was annotated with a set of user features, for example, age, gender, etc, and a set of page

16

Yahoo! Labs Technical Report No. YL-2010-004
features, for example Sports, Finance, etc. We used the value predicted by the model as
the non-guaranteed price ri .
4.2.3. Click forecasting Click forecasting estimates the probability that a displayed
ad will be clicked in a particular user visit context. Estimation of click-through rates (CTR)
is extensively applied in pay-for-performance systems that attempt to maximize expected
revenue [20, 22]. The estimates can be based on historical click-through performance statistics of features that are selected as significant predictors of CTR. In this work, we use a
logistic regression model with the following functional form:
p(click|{f1 , . . . , fK }) =

1 + exp(

1
PK

k=1 wk fk )

(28)

where fk are predicates of features of the user visit and the ad such as user age and gender,
page content category, ad position in page, etc. Using historical data from web traffic that
consist of page visits with corresponding user visit and click statistics, we learned the logistic
regression parameters.
Finally, each edge in the allocation graph, which represents a contract and a corresponding eligible ad opportunity, is annotated with features fk . The click model is used to
produce an estimate of the probability of click pij for each graph edge.
4.3.

Experimental results

We now present our experimental results for various models and parameter settings.
Each optimization for a particular parameter combination takes about 5 to 10 minutes,
which is quite acceptable as an offline optimization step that can inform online serving
algorithms (e.g., [10, 26]).
4.3.1. Baseline and Single-Objective Solutions As a baseline, we compute the
optimization solution that only ensures feasibility by minimizing the total under-delivery
penalty, but does not explicitly optimize for the other objectives. The result for this baseline
solution is shown in the first row of Table 1) and is used as the basis for normalization. We
then optimize for each single objective separately and report the normalized solutions in
the same table — here NGD refers to non-guaranteed revenue, and GD refers to guaranteed
representativeness. It can be seen that while optimizing a single objective may significantly
improve that objective, it has a potentially significant impact on the other objectives.
4.3.2. Two-Objective Formulation We run the 2-step programming algorithm (Section 3.4) with 100 different values of the η parameter. Table 2 shows the objectives in
normalized scale for a subset of the generated efficient solutions. The whole efficient frontier by using all the 100 points is depicted in Figure 4, which shows the trade-off between

17

Yahoo! Labs Technical Report No. YL-2010-004
Table 1: Baseline and Single-Objective Solutions
Objective
Baseline
NGD
Click
NGD+Click
GD

NGD
1
1.0165
1.0062
1.0131
0.9968

Click
1
1.0905
2.9136
2.9013
0.9226

NGD+Click
1
1.0229
1.1722
1.1774
0.9903

GD
-1
-0.9836
-2.2214
-1.7440
-0.0027

Table 2: 2-Step Goal Programming
η
0.8411
0.8570
0.8729
0.8888
0.9047
0.9205
0.9364
0.9523
0.9682
0.9841
0.9999

NGD
0.9968
0.9978
0.9993
1.0016
1.0047
1.0079
1.0094
1.0110
1.0127
1.0131
1.0131

Click
0.9226
1.1269
1.3260
1.5171
1.6990
1.8810
2.0801
2.2782
2.4763
2.6861
2.9013

NGD+Click
0.9903
1.0090
1.0277
1.0464
1.0651
1.0838
1.1026
1.1213
1.1340
1.1587
1.1774

GD
-0.0027
-0.0028
-0.0034
-0.0046
-0.0069
-0.0109
-0.0181
-0.0328
-0.0660
-0.1474
-1.7440

Figure 4: Efficient Frontier
the monetary objective (non-guaranteed revenue plus click value) and the non-monetary
objective (representativeness).
Figure 4 also shows the baseline and single-objective solutions as different symbols. The
baseline solution and most of the single-objective solutions are located in the interior of

18

Yahoo! Labs Technical Report No. YL-2010-004
the feasible solution region and dominated by efficient solutions on the frontier. Further,
the efficient frontier shows that a very small loss in one objective can lead to a significant
gain in the other objective, thereby enabling a better combined trade-off as compared to
single-objective solutions.
The above results clearly demonstrate that explicitly capturing and solving for multiple
objectives dominates ignoring the objectives, or just optimizing for a single objective.
4.3.3. Three-Objective Formulation We run the 3-step programming algorithm (Section 3.5) with 100 different combinations of the η and ω parameters. Table 3 shows the
objectives in normalized scale for a subset of the generated efficient solutions. Note that
the efficient frontier for the tri-objective optimization problem is a surface in a 3D space.
One way to visualize the efficient frontier is to project it to a 2D space by fixing the level
in the third dimension. Figure 5 shows three such contours in the space of click value and
GD representativeness for evenly-spaced NGD revenues. The trade-off among the three
objectives can be observed by comparing points on the same contour and between different
contours.
Table 3: 3-Step Goal Programming
η
0.9961
0.9961
0.9961
0.9981
0.9981
0.9981
0.9999
0.9999
0.9999

4.4.

ω
0.3812
0.6906
1.0000
0.4073
0.7037
1.0000
0.6967
0.8483
0.9999

NGD
1.0125
1.0125
1.0125
1.0145
1.0145
1.0145
1.0165
1.0165
1.0165

Click
1.1075
2.0067
2.9058
1.1740
2.0281
2.8823
1.1209
1.3649
1.6090

NGD+Click
1.0208
1.0990
1.1772
1.0284
1.1027
1.1770
1.0255
1.0468
1.0680

GD
-0.0084
-0.0180
-1.7272
-0.0129
-0.0232
-1.7225
-0.3264
-0.3280
-0.5039

Discussion

The results above and especially the efficient frontier give us a global picture of the
trade-off among different objectives. It reveals what percentage of one objective can be
gained at the cost of one percent of another objective and how the trade-off rate changes
with the location of the solution, thereby providing valuable insight in setting the right
parameters in a real production system to truly reflect the business priority. Perhaps more
importantly, it demonstrates the significant benefit of a combined optimization model for
multiple objectives, as opposed to optimizing for just a single objective.
5.

Further extensions

We have referred throughout to revenue gained through clicks. We might also include
other non-monetary terms, using ξ or some other parameter as a conversion factor. One
19

Yahoo! Labs Technical Report No. YL-2010-004

Figure 5: Contours of Efficient Frontier
candidate for this treatment is relevance, when wij would encode the probability of relevance
of ad j to user i and the payoff to advertiser j for such relevance.
Another candidate for future work is the exploration of ways to to incorporte uncertainty into the strictly deterministic model we have described here. Preliminary stochastic
programming experiments [5] indicate that uncertainty in the inventory supply can have
a significant impact. Other sources of uncertainty arise in sampling error and click and
conversion rate estimation.
6.

Related work

Operations Research techniques, and optimization in particular, have been used for
decades in planning advertising campaigns in other media, such as print, radio and television (see [6] for example). The potential of the WWW for more targeted advertising was
realized in the 1990’s and became a subject of research. Langheinrich et al [17] reported on
a study where they attempted to target display ads to users in order to optimize expected
revenue, without using intrusive data gathering techniques. While “unintrusiveness” seems
to have become less of a concern to advertisers and publishers, their optimization approach
was influential. Tomlin [25], noting a similarity between this problem and the traffic distribution model (see [28]), suggested adding an entropy term to the linear cost function
proposed in [17] to essentially smooth the allocations and prevent “bang-bang” solutions;
characteristic of LP models. Chickering and Heckerman [9] employed an alternate smoothing technnique, involving binning, and gave computational experience. A good survey of
these and later developments is given in [18].
Since that time, the development of Computational Advertising as a discipline has led to
the consideration of many variants of the graphical advertising allocation problem. A crucial

20

Yahoo! Labs Technical Report No. YL-2010-004
development in this process was the promulgation of the concept of “fairness” in allocation
to offset extreme LP solutions. While we have used the approach of [15], an alternate
approach is taken by [13]. Some of our early work was presented in [1] and [29]. Feldman
et al [14] have considered the online ad allocation problem in the more general setting of the
matching problem, while Roels and Fridgeirsdottir [21] have considered a dynamic version
assuming the inventory follows a Markov process. Easterly [11] and Han [16] discuss online
advertising from a Revenue Management point of view.
Two other modules in the online advertising supply chain make use of the results of an
allocation model such as we have described. These are Ad Serving and Admission Control.
The Ad Server interprets the output of the allocation model as a set of frequencies with
which specific ads should be shown to users in the supply pools when they visit a web
page. Considerable practical advantages ensue when the solution can be stored in compact
form and rapidly reconstructed on the fly by the ad server when a page requests ads. This
process has been studied by Devanur and Hayes [10] and Vee et al [26], using the dual values
associated with the demand constraints and, implicitly, the graph structure to determine
the contracts for which a new arriving impression is eligible. The optimization models we
have studied provide the necessary dual values, but online ad serving is not considered in
this paper.
Admission Control is the process of determining whether a proposed new guaranteed
campaign should be accepted, that is whether the existing obligations can still be satisfied
in a modified solution if the new contract is accepted. Versions of this problem have been
studied by Feige et al [12] and Aleai et al [3] and considered as an (NP-hard) combinatorial
optimization problem. Radovanovic and Zeevi [19] have proposed a relaxed, more tractable,
variant of the Admission Control process.
7.

Conclusion

In this paper we have shown that multi-objective optimization provides an efficient
and flexible framework for the allocation of user visits to guaranteed and non-guaranteed
campaigns. The proposed models also incorporate a very flexible means of taking into
account revenue derived from clicks, as well as non-monetary objectives — in particular
“representativeness” or “fairness” — in the allocation of eligible user visits to campaigns.
We are able to do this using off-the-shelf software, such as a commercial scale optimization
system (we used XpressMP) for large scale quadratic programming, or specialized network
optimization codes for some steps.
We believe that the proposed models can be extended to other objectives of interest
such as ad relevance. As part of future research, we are exploring extensions to the model
to include stochastic elements, such as uncertainty in supply and demand, and nonlinear
pricing.

21

Yahoo! Labs Technical Report No. YL-2010-004
8.

acknowledgments

We gratefully acknowledge the assistance of Sumanth Jagannath and Wenjing Ma in
processing the data for our experiments, and Jianchang Mao for managing much of the
click model development.
References
[1] D. Agarwal, J. Tomlin, and J. Yang. A log-linear model for allocating overlapping
inventory to on-line advertisers. Presented at INFORMS, October 2008.
[2] G. Aggarwal, A. Goel, and R. Motwani. Truthful auctions for pricing search keywords.
In Proc. of the 7th ACM Conf. on Electronic Commerce, pages 1–7, 2006.
[3] S. Aleai, E. Arcaute, S. Khuller, W. Ma, A. Malekian, and J. Tomlin. Online allocation
of display advertisements subject to advanced sales contracts. In Proc. of the 3rd Int.
Workshop on Data Mining and Audience Intelligence for Advertising (ADKDD), pages
69–77, 2009.
[4] D. Bertsekas. Network Optimization: Continuous and Discrete Models. Athena Scientific Press, 1998.
[5] V. Bharadwaj, M. Saunders, and J. Tomlin. Sensitivity of an inventory allocation
model for online advertising with stochastic supply. Presented at EURO XXIV, July
2010.
[6] S. Bollapragada, H. Chen, M. Phillips, M. Garbiras, M. Scholes, T. Gibbs, and
M. Humphreville. NBC’s optimization systems increase revenues and productivity.
Interfaces, 32(1):47 – 60, 2002.
[7] A. Z. Broder. Computational advertising and recommender systems. In RecSys ’08,
pages 1–2, Lausanne, Switzerland, 2008.
[8] A. Z. Broder, M. Fontoura, V. Josifovski, and L. Riedel. A semantic approach to
contextual advertising. In Proc. ACM SIGIR, 2007.
[9] D. M. Chickering and D. Heckerman. Targeted advertising with inventory management.
In EC ’00: Proceedings of the 2nd ACM conference on Electronic commerce, pages 145–
149, New York, NY, USA, 2000. ACM.
[10] N. Devanur and T. Hayes. The adwords problem: Online keyword matching with
budgeted bidders under random permutations. Presented at EC, 2009.
[11] A. Easterly. Revenue management in online advertising: Challenges and opportunities.
Presented at INFORMS, October 2009.

22

Yahoo! Labs Technical Report No. YL-2010-004
[12] U. Feige, N. Immorlica, V. Mirrokni, and H. Nazerzadeh. A combinatorial allocation
mechanism with penalties for banner advertising. Presented at INFORMS, October
2008.
[13] J. Feldman, M. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein. Online stochastic
packing applied to display ad allocation. CoRR, abs/1001.5076, 2010.
[14] J. Feldman, A. Mehta, V. Mirrokni, and S. Muthukrishnan. Online stochastic matching:
Beating 1-1/e. Presented at FOCS, October 2009.
[15] A. Ghosh, R. McAfee, K. Papineni, and S. Vassilvitskii. Randomized bidding for
maximally representative allocation. In Proc. WINE, December 2009.
[16] P. Han. Yield optimization in display ad networks. Presented at INFORMS, October
2009.
[17] M. Langheinrich, A. Nakamura, N. Abe, T. Kamba, and Y. Koseki. Unintrusive
optimization techniques for web advertising. In Proc. of World Wide Web Conf.
(WWW1999), 1999.
[18] A. Nakamura and N. Abe. Improvements to the linear programming based scheduling
of web advertisements. J. Electronic Commerce Research, 5:75–98, 2005.
[19] A. Radovanovic and A. Zeevi. Revenue maximization in reservation-based online advertising. Presented at INFORMS, October 2009.
[20] M. Richardson, E. Dominowska, and R. Ragno. Predicting clicks: Estimating the
click-through rate for new ads. In Proc. of World Wide Web Conf. (WWW2007),
2007.
[21] G. Roels and K. Fridgeirsdottir. Dynamic revenue mangement for online display advertising. http://escholarship.org/uc/item/7kq702dz, 2008.
[22] B. Shaparenko, O. Çetin, and R. Iyer. Data-driven text features for sponsored search
click prediction. In Proc. of the 3rd Int. Workshop on Data Mining and Audience
Intelligence for Advertising (ADKDD), pages 46–54, 2009.
[23] R. Shumway and D. Stoffer. Time Series Analysis and Its Applications. Springer, 2007.
[24] R. Steuer. Multiple criteria optimization: theory, computation, and application. Wiley,
New York, 1986.
[25] J. Tomlin. An entropy approach to unintrusive targeted advertising on the web. In
Proc. of World Wide Web Conf. (WWW2000), 2000.
[26] E. Vee, S. Vassilvitskii, and J. Shanmugasundarum. Optimal online assignment with
forecasts. Proc. of the ACM Conf. on Electronic Commerce, 2010.
23

Yahoo! Labs Technical Report No. YL-2010-004
[27] Dash Optimization. XpressMP—Optimizer Reference Manual, 2008.
[28] A. Wilson. Entropy in Urban and Regional Modelling. Pion Press, London, 1970.
[29] J. Yang and J. Tomlin. Advertising inventory allocation based on multi-objective
optimization. Presented at INFORMS, 2008.
Appendix
The goal programming model (17), (8)-(11), (18) in section 3.4 is equivalent to finding
a value of γ which preserves a specified fraction of revenue, given a value of ξ. To see this,
let us write the Lagrangian of the problem (15), (8)-(11) as:
XX
wij yij
Lγ (y, z, αγ , β γ , λγ , µγ ) = γf (y, θ) − ξ
j

−
+

X

βiγ (

i

X

X

ri zi −

X

i

j

yij + zi − si ) −

X

αjγ (

i∈Bj

X

λγij yij −

ij

j|i∈Bj

yij − dj )

i∈Bj

X

µγi zi

i

where the αjγ , βiγ , λγij and µγij are the appropriate Lagrange multipliers on the equality and
inequality constraints.
The KKT optimality conditions for this problem are:
∂Lγ
∂f
=γ
− ξwij − αjγ + βiγ − λγij
∂yij
∂yij
∂Lγ
= −ri + βiγ − µγi
∂zi
∂f
λγij = γ
− ξwij − αjγ + βiγ
∂yij
µγi = βiγ − ri
λγij yij

= 0,

µγi zi

=0
=0
≥0
≥0
=0

Now consider the Lagrangian of the problem (17), (8)-(11), (18), introducing Lagrange
multiplier ρ:

−

X
j

αjη (

X

Lη (y, z, αη , β η , λη , µη , ρ) = f (y, θ)
X η X
yij − dj ) +
βi (
yij + zi − si )
i

i∈Bj

j|i∈Bi

−

X

ληij yij −

ij

−ρ(ξ

XX
j

wij yij +

24

µηi zi

i

X
i

i∈Bj

X

ri zi − ψM ∗ )

Yahoo! Labs Technical Report No. YL-2010-004
The KKT optimality conditions are:
∂f
∂Lη
=
− ρξwij − αjη + βiη − ληij
∂yij
∂yij
∂Lη
= −ρri + βiη − µηi
∂zi
∂f
ληij =
− ρξwij − αjη + βiη
∂yij
µηi = βiη − ρri
ληij yij
ρ(ξ

XX
j

i∈Bj

wij yij +

X

= 0,

µηi zi

=0
=0
≥0
≥0
=0

ri zi − ψM ∗ ) = 0

i

Comparing terms in the Lagrangians and the two sets of KKT conditions we see that
αjη = ραjγ , βiη = ρβiγ , ληij = ρλγij , µηi = ρµγi . In particular, we see that γρ = 1. Thus we
may obtain the parameter γ as 1/ρ from the solution to the goal programming problem.

25

