Linear program modeling
This week we will showcase a few examples of optimization prob- lems that can be modeled as linear programs: how to approximate a set of points with a line, production planning and flow prob- lems. We will also touch on the more general integer programming framework.
3.1 Production planning
Suppose we are given demand projection data d1d2 . . . dn for n time periods. We are to decide how much to produce at each time period while obeying lower and upper bounds on the number of units we can produce at each time period (say at least m units and at most M units) to minimize storage costs.
We can model this problem using variables xi to capture the number of units produced at period i and si to capture the number units that we need to carry over from period i to i + 1.
minimize subject to
si = si−1 +xi −di si ≥0
i = 2,…,n i=1,…,n i=1,…,n i=1,…,n
3.2 Fitting a line through a point set
Our second application is that of fitting a line y = ax + b through a set of points (x1,y1),(x2,y2),…,(xk,yk). The goal is to pick a line that “explains” the point set well; informally, we would like yi ≈ axi + b. There are several criteria for picking a and b. One common criterion is to find a and b minimizing the square of the errors:
y = ax + b
© Copyright 2021 Julián Mestre.
This work is licensed under a Creative Commons Attribution-NonCommercial- ShareAlike 4.0 International License.
2 (yi −axi −b)
In some circumstances, this is not the most appropriate criterion since a single outlier can have a disproportionate influence on the
week 3 – linear program modeling
discrete optimization 2
solution. In such cases a better criterion is to minimize the sum of
the absolute errors:
|yi −axi −b| i
We can model the problem with a linear program where a and b are variables, and we have an error variable ei for each input point (xi, yi).
The first two constraints guarantee that ei ≥ |yi −axi −b| for each i = 1,…,k. Therefore, because the program
is trying to minimize e , in an
minimize subject to
ei ≥ yi −axi −b
ei ≥ −(yi −axi −b) ei ≥0
i = 1,…,k i = 1,…,k i=1,…,k
optimal solution ei = |yi − axi − b|.
3.3 Flow problems
Given a directed graph G = (V,E) with edge capacities c : E → R+, a circulation is an edge function f : E → R+ that obeys flow conser- vation at every vertex while obeying edge capacity constraints.
The maximum flow problem is to find a circulation maximizing the flow along an edge (t, s) for two distinguished vertices s and t called the source and the sink.
This problem can be modeled as linear program where the vari- ables are the flow values fu,v for each (u, v) ∈ E.
maximize subject to
fv,u = fu,v (v,u)∈δin (u) (u,v)∈δout (u)
fu,v ≤ cu,v fu,v ≥0
u ∈ V (u,v) ∈ E
There are efficient algorithms for solving the maximum flow problem, however, the linear programming framework has the advantage of being easily extensible to handle many generalizations of the basic problem, like adding vertex capacities, having multiple commodities, and finding minimum cost maximum flows.
3.4 Integer programming
While many optimization problems can be modeled as linear pro- grams, many more problem are computationally hard (more specif- ically, they are NP-hard), so they cannot be solved using linear pro- gram (otherwise, P = NP). These problem, however, can usually be cast as integer linear programs, which is nothing more than a stan- dard linear program with the additional constraint that variables must take integral values.
week 3 – linear program modeling
discrete optimization 3
Most common ILPs are binary programs where variable are restricted to {0, 1}. To exemplify the power of the binary program
let us model the classic NP-hard vertex cover problem where we are given an undirected graph G = (V,E) and we are select a minimum cardinality subset of the vertices C ⊆ V such that every edge has at least one endpoint in C.
We use a variable xu ∈ {0, 1} as an indicator variable for whether u is chosen into the cover (if xu = 1 then u ∈ C, otherwise, u ∈/ C).
minimize u∈V xu
subjectto xu+xv ≥1 (u,v)∈E
xu ∈{0,1} u∈V
1. Suppose that we add to production planning problem from Sec- tion 3.1 an overflow area of capacity C in the factory that we can use for free. Any unit beyond this has to be carried to an offsite
warehouse and thus incur a cost. In this scenario we would like
to minimize i max(0, si − C). Show how to modify the model to handle this objective.
2.Supposeyouaregivenatrainingsetofpointsp1,p2,…,pk ∈ Rn. The points are divided into two categories, say “red” and “blue”. A linear classifier is a function that takes a new point p and classifies as “red” or “blue” based on whether a·p > b or a·p ≤ b, where a ∈ Rn and b ∈ R are parameters defining the classifier. We say the classifier is accurate on the training set if it correctly classifies all the points in the set. Design an algorithm for testing if a given training set can be correctly classified.
3. Show how to find a maximum flow where every vertex u ∈ V has a capacity cu that limits how much flow can go through the vertex.
4. Given an auxiliary edge weight function w : E → R+, show how
to find a maximum s-t flow with minimum cost
5. Binary programs are a special class of integer program where the variables can take one of two values: 0 or 1. Prove that an integer linear program with n variables over the range {0, . . . , T } can be reduced to a binary linear program with n (1 + ⌊log T ⌋) variables.
week 3 – linear program modeling
discrete optimization 4
6. Model the problem of solving a sudoku puzzle as an integer program with variables zijk that denote the fact that cell (i, j) is assigned the digit k where i,j,k ∈ {1,2,…,9}.
*7. Givenapointp ∈ Rn andaradiusr ∈ R+,wedefinetheball B(p,r)={x∈Rn :∥x−p∥≤r}tobethesetofpointatdistanceat most r from p.
Let P be a polyhedron defined by a set of m linear inequalities. Come up with a linear programming formulation for the problem of finding the largest ball that fits inside of P.