Algorithmic Game Theory and Applications
Lecture 5: Introduction to Linear Programming
AGTA: Lecture 5
Copyright By PowCoder代写 加微信 powcoder
“real world example”: the diet problem
• You are a fastidious eater. You want to make sure that every day you get enough of each vitamin: vitamin 1, vitamin 2,…., vitamin m.
• You are also frugal, and want to spend as little as possible.
• There are n foods available to eat: food 1, food 2, …., food n.
• Each unit of food j has ai,j units of vitamin i.
• Each unit of food j costs cj.
• Your daily need for vitamin i is bi units.
• Assume you can buy each food in fractional amounts. (This makes your life much easier.)
• How much of each food would you eat per day in order to have all your daily needs of vitamins, while minimizing your cost?
AGTA: Lecture 5
A Linear Programming Example
Find (x,y) ∈ R2 so as to:
Maximize 2x + y
Subject to conditions (“constraints”):
x+y≤6 x≤5 y≤4
x + y <= 6
2 x + y = 11
Much of this simple “geometric intuition” generalizes nicely to higher dimensions. (But be very careful! Things get complicated very quickly!)
AGTA: Lecture 5
The General Linear Program Definition: A Linear Programming or Linear Optimization
problem instance consists of
1. A linear objective function f : Rn → R, given by: f(x1,...,xn)=c1 x1 +c2 x2 +...+cn xn +d
where we assume the coefficients ci and constant d are rational numbers.
2. An optimization criterion:
Opt ∈ {Maximize, Minimize}.
3.A set (or “system”) C(x1,...,xn) of m
, or linear inequalities/equalities,
Ci(x1,...,xn), i = 1,...,m, where each Ci(x) has the form:
ai,1 x1 +ai,2 x2 +...+ai,n xn ∆ bi where ∆ ∈ {≤, ≥, =},
and where ai,j’s and bi’s are rational numbers. AGTA: Lecture 5
linear constraints
What does it mean to solve an LP?
For a constraint Ci(x1,...,xn), we say a vector v = (v1,...,vn) ∈ Rn satisfies Ci(x) if, plugging in v for the variables x = (x1, . . . , xn), the constraint Ci(v) holds true. E.g., (3, 6) satisfies −x1 + x2 ≤ 7.
A vector v ∈ Rn is called a solution to the system C (x), if v satisfies every constraint Ci ∈ C . I.e., C1(v) ∧ . . . ∧ Cm(v) holds true.
Let K(C) ⊆ Rn denote the set of all solutions to the system C(x). We say C is feasible if K(C) is not empty.
An optimal solution, for Opt = Maximize (Minimize), is some x∗ ∈ K(C) such that
f(x∗)= max f(x) x∈K(C)
(respectively, f(x∗) = minx∈K(C) f(x)).
Given an LP problem (f,Opt, C), our goal in principle
is to find an “optimal solution”.
Oops!! There may not be an optimal solution!
AGTA: Lecture 5
Things that can go wrong
At least two things can go wrong when looking for an optimal solution:
1. There may be no solutions at all! I.e., C is not feasible, i.e., K(C) is empty. Consider:
Maximize x Subject to:
x ≤ 3, and x ≥ 5
2. max / minx∈K(C) f(x) may not exist! because f(x) is unbounded above/below in K(C). Consider:
Maximize x Subject to: x≥5
So, we revise our goals to handle these cases.
Note: If we allowed strict inequalities, e.g., x < 5, there would have been yet another problem:
Maximize x Subject to: x<5
AGTA: Lecture 5
The LP Problem Statement
Given an LP problem instance (f,Opt,C) as input, output one of the following three:
1. “The problem is Infeasible.”
2. “The problem is Feasible But Unbounded.”
3. “An Optimal Feasible Solution (OFS) exists. One such optimal solution is x∗ ∈ Rn.
The optimal objective value is f(x∗) ∈ R.”
Oops!! It seems yet another thing could go wrong:
“What if every optimal solution x∗ ∈ Rn is irrational? How can we “output” irrational numbers?
Likewise, what if the Opt value f(x∗) is irrational?” Fact
As we will soon see, this problem never arises. The above three answers cover all possibilities, and furthermore, as long as all our coefficients and constants are rational, if an OFS exists, there will be a rational OFS x∗ and the optimal value f(x∗) will also be rational.
AGTA: Lecture 5
Simplified forms for LP problems
1. In principle, we only need to consider Maximization, because
minf(x) = −max−f(x) x∈K x∈K
(either side is unbounded if and only if both are.)
2. In principle, we only need an objective function
f(x1,...,xn) = xi, for some xi, because we can
• Introduce new variable x0. Add constraint f(x) = x0 to the constraint set C.
• Make the new objective “Optimize x0”.
3. We don’t need equality constraints, because
α = β if and only if (α ≤ β and α ≥ β).
4. Wedon’tneed“α≥b”,whereb∈R,
because α ≥ b if and only if −α ≤ −b.
5. We can constrain every variable xi to be xi ≥ 0: Introduce two variables x+i ,x−i for each variable xi. Replace each occurence of xi by (x+i − x−i ), and add the constraints x+i ≥ 0, x−i ≥ 0.
(N.B. can’t do both (2.) and (5.) together.)
AGTA: Lecture 5
A lovely but terribly inefficient algorithm for LP
Input: LP instance (x0,Opt, C(x0, x1, . . . , xn)). 1. Fori=ndownto1
(a) Rewrite every constraint involving xi as either: α≤xi oras xi≤β
(one of the two is possible). Let these be: α1 ≤xi,...,αk ≤xi ; xi ≤β1,...,xi ≤βr (Retain these constraints, Hi, for later.)
(b) Remove Hi, i.e., all constraints involving xi. Replace them with all constraints:
αj ≤βl , j=1,...,k,andl=1,...,r.
2. Only x0 (or no variable) remains. All constraints havetheformsaj ≤x0,x0 ≤bl,oraj ≤bl, where aj’s and bl’s are constants. It’s easy to check “feasibility” & “boundedness” for this one(or zero)-variable LP, and to find an optimal x∗0 if it exists.
3. Once you have x∗0, plug it into H1. Solve for x∗1. Then use x∗0,x∗1 in H2 to solve for x∗2, ...,usex∗0,...,x∗i−1 inHi tosolveforx∗i. ... x∗ = (x∗0, . . . , x∗n) is an optimal feasible solution.
AGTA: Lecture 5
remarks on the lovely algorithm
• This algorithm was first discovered by Fourier (1826). It was rediscovered in the 1900’s, by Motzkin (1936) among others.
• It is called Fourier-Motzkin Elimination, and can be viewed as a generalization of Gaussian
, used for solving systems of linear equalities.
• Why is Fourier-Motzkin so inefficient? In the worst case, if every variable xi is involved in every constraint, each iteration of the “For loop” squares the number of constraints. So, toward the end we could have roughly m2n constraints!!
• Let’s recall Gaussian Elimination. It is much nicer and does not suffer from this explosion.
(You would expect nothing less from Gauss!)
• In 1947, Dantzig invented the celebrated Simplex Algorithm for LP. It can be viewed as a much more refined generalization of Gaussian Elimination. Next time, Simplex!
Elimination
AGTA: Lecture 5
further remarks
• Immediate Corollaries of Fourier-Motzkin: Corollary 1: The three possible “answers” to an LP problem do cover all possibilities.
(In particular, unlike “Maximize x; x < 5”, If an LP has a “Supremum” it has a “Maximum”.)
Corollary 2: If an LP has an OFS, then it has a rational OFS, x∗, and f(x∗) is also rational. Proof: We used only addition, multiplication, & division by rationals to arrive at the solution.
• Although Fourier-Motzkin is bad in the worst case, it can still be quite useful.
It can be used to remove redundant variables. Redundant constraints could also be removed, and sometimes the worst-case may not arise.
• Generalizations of Fourier-Motzkin are actually used in competitive tools (e.g., [Pugh,’92]) to solve “Integer Linear Programming”, where we seek an optimal solution x∗ not in Rn, but in Zn. ILP is a much harder problem! (NP-complete.)
• For ordinary LP however, Fourier-Motzkin can’t compete with Simplex.
AGTA: Lecture 5
• Food for Thought: Think about what kinds of clever heuristics and hacks you could use during Fourier-Motzkin to keep the number of constraints as small as possible. E.g., In what order would you try to eliminate variables?
(Clearly, any order is fine, as long as x0 is last.)
AGTA: Lecture 5
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com