Report

Modeling problems with Integer Linear Programming (ILP) Name: Chuan Huang Use of ILP Solution to network or graph problems. Traveling salesman problem Shortest path Minimum spanning tree Knapsack Definition of ILP • Linear programming (LP) : mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear equations. • Integer linear programming(ILP) : LP with some or all of the variables are restricted to be integers. • Canonical form: minimize cTx subject to Ax b Modeling with ILP Problem description Formulation Input Output: Identify the decision variable which is binary; Objective function: Minimize/Maximize a function under the constraints. Constraints: Rules that the feasible solutions will satisfy. Solution Solution to ILP Package GNU Linear Programming Kit (GLPK) Cplex: mathematical optimizer AMPL: A modeling language for Mathematical programming developed by BELL Laboratories. Gusek - LP IDE in Windows http://gusek.sourceforge.net/gusek.html Example 1 - Vertex Cover • Vertex cover: Is there a vertex cover of size K or less for G(V, E) such that for each edge {u, v} E at least one of u and v belongs to V. B C D A E • F Minimum vertex cover: Find a smallest vertex cover in a given graph. B C E F A D Example 1 - Input and Output Minimum vertex cover B C E F D A Input: (1) Set of vertexes V; (2) Set of edges E; (3) Costs of each vertex, c(i) = 1, where i V; Output: The set of the vertexes; x(i) = 1 if ith vertex belongs to the set; otherwise x(i) = 0; Objective: Minimum costs, c(i) x(i) . iV Example 1 – Input and Output(Cont) Input /* Number of blocks */ param m, integer, > 0; /* Set of basic blocks */ set V, default {1..m}; /* Set of edges */ set E, within V cross V; /*Cost of vertex*/ param c{i in V}, default 0; Output param m:=6; param : V : c := 1 1, 2 1, 3 1, 4 1, 5 1, 6 1; param : E : a := 1 2 1, 1 5 1 , 2 3 1, 2 5 1, 3 4 1 , 6 3 1, 6 5 1; var x{i in V}, binary, >=0; /*Decision*/ Vertex_cover.mod Vertex_cover.dat Example 1 – Objective and Constraints Mathematic description: AMPL: Objective: Minimize c(v)xv minimize obj: sum{i in V} x[i]*c[i]; vV (Minimize the total cost) Constraint: xv {0, 1} for all v E (Vertex is either in the vertex cover or not) xu+xv ≥ 1 s.t. phi{(i,j) in E}: x[i]+x[j] >= 1; Solve; for all {u, v} E (Cover every edge of the graph) Vertex_cover.mod Example 2 - Vertex Cover with non-linear Costs B C E F D A Assume input, output and objective are same except Cost of each vertex: c(i) x( j) ( i , j )E Objective : Minimize c(i) x(i) iV Decided by output x(i) X2! Not Linear! Example 2 - Vertex Cover with non-linear Costs Linearise the equations by using new variable Define variable cost(i), i B which represents the final cost of ith node. Cost of each vertex: c(i) x( j) ( i , j )E Cost of each vertex cost(i ) c(i ) (1 x(i )) * when x(i) is decided: cost(i ) 0 Equivalent objective : Minimize cost(i) iV Linear! Example 2 - Vertex Cover with non-linear Costs B C E F D A Output: x = [1, 1, 0, 1, 0, 1]; cost = [1, 1, 0, 0, 0, 0]; Total cost = 2