WIXLIB

15.053/8March 14, 2013Introduction to Integer Programming– Integer programming models1

Quotes of the Day“Somebody who thinks logically is a nicecontrast to the real world.”-- The Law of Thumb“Take some more tea,” the March Hare said toAlice, very earnestly.“I’ve had nothing yet,” Alice replied in anoffended tone, “so I can’t take more.”“You mean you can’t take less,” said the Hatter.“It’s very easy to take more than nothing.”-- Lewis Carroll in Alice in Wonderland2

Combinatorial optimization problems INPUT: A description of the data for an instance of theproblem FEASIBLE SOLUTIONS: there is a way of determining fromthe input whether a given solution x’ (assignment of values todecision variables) is feasible. Typically in combinatorialoptimization problems there is a finite number of possiblesolutions. OBJECTIVE FUNCTION: For each feasible solution x’ there isan associated objective f(x’).Minimization problem. Find a feasible solution x* that minimizesf( ) among all feasible solutions.3

Example 1: Traveling Salesman Problem INPUT: a set N of n points in the plane FEASIBLE SOLUTION: a tour that passesthrough each point exactly once. OBJECTIVE: minimize the length of the tour.4

Example 2: Balanced Partition INPUT: A set of positive integers a1, , an FEASIBLE SOLUTION: a partition of {1, 2, n}into two disjoint sets S and T.– S T , S T {1, , n}OBJECTIVE : minimize i S ai -Example: i T ai 7, 10, 13, 17, 20, 22These numbers sum to 89The best split is {10, 13, 22} and {7, 17, 20}.5

Example 3. Exam Scheduling INPUT: a list of subjects with a final exam;class lists for each of these subjects, anda list of times that final exams can be scheduled.Let aij denote the number of students that aretaking subjects i and j. FEASIBLE SOLUTION: An assignment ofsubjects to exam periods OBJECTIVE: minimize {aij : i and j are scheduled at the same time}6

Example 4: Maximum Clique Problem INPUT: a friendship network G (N, A). Ifpersons i and j are friends, then (i, j) A. FEASIBLE SOLUTION: a set S of people suchthat every pair of persons in S are friends. OBJECTIVE: maximize S 7

Example 5: Integer programming INPUT: a set of variables x1, , xn and a set oflinear inequalities and equalities, and a subset ofvariables that is required to be integer. FEASIBLE SOLUTION: a solution x’ that satisfiesall of the inequalities and equalities as well as theintegrality requirements. OBJECTIVE: maximize i ci xiExample:maximize3x 4ysubject to5x 8y 24x, y 0 and integer8

Which of the following is false?1. The Traveling Salesman Problem is acombinatorial optimization problem.2. Integer Programming is a combinatorialoptimization problem.3. Every instance of a combinatorial optimizationproblem has data, a method for determiningwhich solutions are feasible, and an objectivefunction value for each feasible solution.4. Warren G. Harding was the greatest American President.9

The advantages of integer programs Rule of thumb: integer programming can modelany of the variables and constraints that youreally want to put into an LP, but can’t. Binary variables– xi 1 if we decide to do project i (else, it is 0)– xi 1 if node i is selected in the graph (else 0)– xij 1 if we carry out task j after task i (else, 0)– xit 1 if we take subject i in semester t (else, 0)10

Examples of constraints If project i is selected, then project j is not selected. If x1 0, then x1 10. x3 5 or x4 8. x1, x2, x3, x4, x5, are all different integers in {1, 2, 3, 4, 5} x is divisible by 7 x is either 1 or 2 or 4 or 8 or 3211

Nonlinear functions can be modeled usinginteger programmingf(x)753y00379x24xy 2xif 0 x 3y 9–xif 3 x 7y -5 xif 7 x 912

You mean, thatyou can writeall of thoseconstraints inan integerprogram.That’s so easy.No. That’s not what we mean! Wemean that we can take any of theseconstraints, and there is a way ofcreating integer programmingconstraints that are mathematicallyequivalent. It’s not so easy at first,but it gets easier after you see someexamples.We’ll show you how to dothis one step at a time. Butfirst, we’ll review what wemean by integer programs.13

Integer ProgramsInteger programs: a linear program plus theadditional constraints that some or all of thevariables must be integer valued.We also permit “xj {0,1},” or equivalently,“xj is binary”This is a shortcut for writing the constraints:0 xj 1 and xj integer.14

Types of Integer ProgramsMixed integer linearprograms(MILPs or MIPs)Pure Integer Programs0-1 IntegerProgramsxj 0 and integer for some or all j.xj 0 and integer for every j.xj {0,1} for every j.Note, pure integer programming instances that are unboundedcan have an infinite number of solutions. But they have afinite number of solutions if the variables are bounded.15

Goals of lectures on Integer Programming. Lectures 1 and 2– Introduce integer programming– Techniques (or tricks) for formulatingcombinatorial optimization problems as IPs Lectures 3 and 4.– How integer programs are solved (and whythey are hard to solve). Rely on solving LPs fast Branch and bound and cutting planes Lecture 5. Review and modeling practice16

A 2-Variable Integer programmaximize3x 4ysubject to5x 8y 24x, y 0 and integer What is the optimal solution?17

The Feasible Region5Question: What is theoptimal integer solution?34What is the optimal linearsolution?012Can one use linearprogramming to solve theinteger program?012345

A rounding technique that sometimesis useful, and sometimes not.012345Solve LP (ignoreintegrality) get x 24/5,y 0 and z 14 2/5.Round, get x 5, y 0,infeasible!Truncate, get x 4, y 0,and z 12Same solution value atx 0, y 3.Optimal is x 3, y 1, andz 13012345

001122334455Consider the feasible regions for thetwo integer programs on this slide.01234max3x 4ys.t.5x 8y 245x, y 0 and integer0123max3x 4ys.t.x 45y 42x 3y 9x, y 0 and integer20

Which of the following is false for the twointeger programs on the previous slide?1. The two models are the same in that theyhave the same feasible regions and thesame objective function.2. Model 1 will be solved faster because ithas fewer constraints.3. If we removed the integrality constraintsfrom both models, they would becometwo different linear programs.4. Model 1 has the fewest number ofconstraints for an IP with this feasibleregion.21

Why integer programs? Advantages of restricting variables to take oninteger values– More realistic– More flexibility Disadvantages– More difficult to model– Can be much more difficult to solve22

On computation for IPs Much, much harder than solving LPs Very good solvers can solve large problems– e.g., 50,000 columns 2 million non-zerosHard to predict what will be solved quickly andwhat will take a long time.23

Running time to optimality (CPLEX)number of columns1,000,000 1 Hour 1 hourNot yet solved100,00010,000Instances are takenfrom MIP Lib1,0001,00010,000100,000number of rows1,000,00024

Mental Break25

On formulating integer programsConsider an instance of a combinatorial optimizationproblem (COP).When we form the integer program (IP), we usuallywant the following:1.2.3.If x is feasible for the COP, then x is feasible for the IP.If x is feasible for the IP, then x is feasible for the COP.If x is feasible, then its objective function value is the samefor both the IP and COP.Note: We often need to add variables to the COP(especially 0-1 variables), when formulating integerprograms.26

Example : Maximum Clique ProblemINPUT: a friendship networkG (N, A). If persons i and jare friends, then (i, j) A.Decision variablesFEASIBLE SOLUTION: a setS of people such that everypair of persons in S arefriends.OBJECTIVE: maximize S 27

The Game of Fiver.Click on a circle, andflip its color and thatof adjacent colors.Can you make all ofthe circles red?28

The game of fiver.Click on (3, 3)29

The game of fiver.Click on (3, 1)Click on (4, 4)30

The game of fiver.Next: anoptimizationproblem whosesolution solvesthe problem inthe fewestmoves.31

On forming Integer programs1.First select the set of decision variables.It turns out that timing does not matter in thisgame. All that matters is what square areclicked on.2.Write the objective.3.Write the constraints. If it is easier to express itusing non-linear constraints, or logicalconstraints, then do this first.32

Optimizing the game of fiver.112345Let x(i,j) 1 if I click onthe square in row i andcolumn j.x(i,j) 0 otherwise.234533

Let’s write the formulationx(i,j) 1 if I click on the square in row i andcolumn j.x(i,j) 0 otherwise.34

Optimizing the game of fiverMinimize i,j 1 to 5x(i, j)s.t. x(i, j) x(i, j-1) x(i, j 1) x(i-1, j) x(i 1, j)is odd for all i, j 1 to 5.x(i, j) is 0 or 1 for all i, j 1 to 5.x(i, j) 0 otherwise. This (with a little modification) is an integer program.35

Optimizing the game of fiverMinimize i,j 1 to 5x(i, j)s.t. x(i, j) x(i, j-1) x(i, j 1) x(i-1, j) x(i 1, j) - 2 y(i, j) 1 for all i, j 1 to 5.x(i, j) is 0 or 1 for all i, j 1 to 5.x(i, j) 0 otherwise0 y(i, j) 2;y(i, j) integer for i, j 1 to 5.This is an integer program.x is odd if there is an integer y such that x – 2y 1.36

Should I give away the solution?37

Trading for ProfitNooz is a contestant on Trading for Profits. Its mainslogan is“ITrading for Profit”Nooz has just won 14 IHTFP points. We now join thequiz show to see what the 14 points are worth.38

iPad5 pointsData server7 pointsMIT ‘Brass Rat’ring4 points 500 giftcertificate toAu Bon PainTutoring in 6.041ProbabilisticSystems AnalysisDinner with Prof.Orlin and the15.053 TAs3 points4 points6 points39

iPadData server5 points7 points16 utils22 utilsTutoring in6.041ProbabilisticSystemsAnalysisDinner withProf. Orlin andthe 15.053 TAs4 points6 points11 utils19 utilsMIT ‘Brass Rat’ring4 points12 utils 500 giftcertificate toAu Bon Pain3 points8 utilsNooz determines whateach prize is worth tohim. He measureeverything in “utils” on ascale from 1 to 25.40

221281119Au BonPain6.041tutoring15.053dinnerBudget: 14 IHTFP points.Write Nooz’s problem as an integer program. 1Let x i 0if prize i is selectedotherwise41

Integer Programming FormulationObjective and Constraints?Max 16x1 22x2 12x3 8x4 11x5 19x65x1 7x2 4x3 3x4 4x5 6x6 14xj {0,1} for each j 1 to 6We will solve this problem in two lectures.42

Knapsack or Capital Budgeting You have n items to choose from to put into yourknapsack. Item i has weight wi, and it has value ci. The maximum weight your knapsack (or you) canhold is b. Formulate the knapsack problem.43

The mystery of integer programming Some integer programs are easy (we can solveproblems with millions of variables) Some integer programs are hard (even 100variables can be challenging) It takes expertise and experience to know whichis which It’s an active area of research at MIT andelsewhere44

Using Excel Solver to Solve IntegerPrograms Add the integrality constraints (or add that a variable isbinary) Set the Solver Tolerance. (Integer optimality %)(The tolerance is the percentage deviation from optimalityallowed by solver in solving Integer Programs.)– The default used to be 5%.– A 5% default is way too high– It often finds the optimum for small problems45

Some Comments on IP models There are often multiple ways of modeling thesame integer program. Solvers for integer programs are extremelysensitive to the formulation. (not true for LPs)46

Summary on Integer Programming Dramatically improves the modeling capability– Economic indivisibilities– Logical constraints– capital budgeting– games Not as easy to model Not as easy to solve. Next lecture: more IP formulations47

MIT OpenCourseWarehttp://ocw.mit.edu15.053 Optimization Methods in Management ScienceSpring 2013For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.

Example 5: Integer programming INPUT: a set of variables x. 1, , x. n. and a set of linear inequalities and equalities, and a subset of variables that is required to be integer. FEASIBLE SOLUTION: a solution x' that satisfies all of the inequalities and equalities as well as the integrality requirements. OBJECTIVE: maximize . i. c. i. x .