New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Kennith Herman


Kennith Herman
GPA 3.54

Jakayla Robbins

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Jakayla Robbins
Class Notes
25 ?




Popular in Course

Popular in Mathematics (M)

This 7 page Class Notes was uploaded by Kennith Herman on Friday October 23, 2015. The Class Notes belongs to MA 416G at University of Kentucky taught by Jakayla Robbins in Fall. Since its upload, it has received 22 views. For similar materials see /class/228142/ma-416g-university-of-kentucky in Mathematics (M) at University of Kentucky.

Similar to MA 416G at UK

Popular in Mathematics (M)




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/23/15
NAME INTEGER PROGRAMMING MA 416 When we solved the GTMC problem we were very lucky to nd an optimal solution that was integral In other words each of the variables in the optimal solution had an integer value In fact since it is impossible to make only part of a gadget or part of a trinket we needed integer values for the variables in this problem Technically we should have added a extra constraint to the GTMC linear program specifying that 1 and 2 had to be integers Lucky for us this constraint was unnecessary because the simpler linear program just happened to have an optimal solution that was integral This will not always be the case Consider the integer program shown below maximize z 2x1 3x2 subject to 4x1 12 S 39 20L 24 g 90 1 S 2 12 Z 0 zhzg integer Notice that we called this an integer program77 or an IP77 because the last constraint indicates that the variables must have integer solutions Graphically we are trying to nd the best lattice point in the feasible region We can still sweep over the feasible region with a set of increasing pro t lines but now we wish to nd the last lattice point not the last corner point that the pro t lines encountered The rst thing to note about integer programs is that the integer constraint may be necessary It was not necessary in the GTMC problem but it is necessary in the problem given above The LP relaxation of an integer program is the integer program without integer constraint For the problem above the LP relaxation is maximize z 2x1 3x2 subject to 4x1 12 S 39 20x1 24x2 3 90 1 S 2 12 Z 0 The graph below may be helpful to you as you answer the following questions 1 What is the optimal solution of the LP relaxation of this IF 2 What is the closest lattice point to this solution 3 What is the closest feasible lattice point to this solution 4 What is the optimal solution to the IF Notice that the optimal solution of the LP is not integral Hence7 the integer constraints of the IP are necessary Also notice that the closest lattice point to the optimal solution of the relaxation is not feasible for the IF What lesson should you learn from this What other lessons should you learn from this example We were able to solve the IP in this worksheet geometrically This was a small problem We have seen before that geometry goes out the window as soon as we enter four dimensions and if your drawing ability is anything like mine it is essentially useless when we have three dimensions Nevertheless it is good to have a small problem that we understand so that can test proposed algorithms for larger problems Today we are going to investigate the branch and bound algorithm for solving integer programs Let7s use the branch and bound algorithm to solve the integer program we have been examining today Let P0 denote the relaxation of the 1P We begin by solving P0 P03 1 1 x2 291667 2 1075 Clearly this cannot be the solution to the 1P because the 2 value is not integral We would like to eliminate the possibility of nding a solution to our LP in which 2 can be equal to 291667 If we force 2 to be greater than or equal to 3 or less than or equal to 2 then we have ruled out the possibility of 2 being equal to 291667 We are going to create or branch into two new linear programs The rst linear program will be called P1 We obtain this LP by adding the constraint 2 3 2 to P0 The second linear program will be called P2 We obtain this LP by adding the constraint x2 2 3 to P0 The feasible regions of these LP7s contain all of the integer points of our original lP but they do not contain the point 1 1x2 291667 So the optimal solution for our lP lies somewhere in the feasible region of P1 or the feasible region of P2 Let7s solve these LP7s P03 1 1 952 291667 2 1075 2 Sf 2 2 3 P1 3 P2 3 1 2 1 2 2 2 3 z 10 z 105 The optimal solution to P1 was integral so we put two boxes around P1 There is no need to branch further on this LP because we will not nd a better integer solution in the feasible region for P1 On the other hand the optimal solution for P2 was not integral We will need to branch here because it is possible that there is an integer solution in the feasible region for P2 that is even better than the integer solution we found with P1 You cannot stop When you nd an integer solution You need to make sure that there is not a better integer solution The optimal solution for P2 has an 1 value equal to 075 We need to exclude this fractional value We can exclude it by requiring 1 3 0 or 1 2 1 We are going to add the constraint 1 3 0 to P2 to create a new linear program called P3 We will add the constraint 1 2 1 to P2 to obtain a new linear program called P4 P0 3 1 1 x2 291667 2 1075 2 S Q 2 2 3 P1 3 P2 3 1 1 2 2 z 10 z 105 1 S 0 1 2 1 P3 3 1 0 P4 3 2 35 infeasible z 97 Notice that P4 was infeasible We put a double box around this LP because we should not branch here Adding more constraints will never make an infeasible LP feasible We do need to branch on P3 Can you decide what the branches should be The branches and their solutions are on the next page P03 1 1 x2 291667 2 1075 2 S Q 2 2 3 P13 P23 1 2 1 2 2 2 z 10 z 105 1 S 0 1 21 P33 1 0 2 z 975 2 S3 P53 1 0 2 z At this point we can stop Each of the leaves of this complete enumeration tree is in a double box indicating that we cannot do any more branching Now we examine the solutions in the double boxes We have two integer solutions The solution for P1 has an objective function value equal to 10 and the solution for P4 has an objective function value equal to 9 Since we are trying to rnaxirnize7 an optimal solution for the original 113 is 1 2 2 2 with a corresponding 2 value equal to 10 You may have noticed that we did a breadth rst search instead of a depth rst search In other words7 we solved each of the LP7s on a given level before proceeding to the next level We did this because it is an organized approach that can be helpful when you are rst learning the about the branch and bound algorithm In practice7 the depth rst search is preferred to the breadth rst search The author of your textbook gives three reasons for this and you should read Chapter 23 of your textbook after class One of the reasons given relates to pruning the tree I want to brie y describe how you can prune an enumeration tree Look at the objective function values as you go down a path on the tree They never increase As you go down a path on the tree7 you are adding more constraints to the LP7s This reduces the size of the feasible region Hence7 the objective function values will never increase as you go down a path on the tree Does anyone see why we did more work than necessary When we solved P17 we found a feasible solution for the 113 that corresponded a 2 value of 10 Now lets consider what can happen by branching on P2 If we nd an integer solution7 then the 2 value can be at most 105 However7 since the objective function is z 2x1 327 any integer solution for 1 and 2 will correspond to an integer 2 value since CT 2 3 is an integer vector Hence7 any integer solution that we nd by branching on P2 will correspond to a 2 value that is less than or equal to 10 We can do no better than the solution that we have already found Therefore we can simply stop after the second level of the tree Note that CT does not need to be an integer vector lf CT had not been an integer vector7 we may not have been able to stop on Pg7 but we de nitely could have stopped on P3 because 975 lt 10 P03 1 1 952 291667 2 1075 x2 S Q 2 3 P1 3 P23 1 2 1 2 2 3 z 10 z 105 STOP The z values cannot exceed 107 and we already have an integer solution corresponding to z 10 l have one nal comment before setting you free to experiment with integer prograrns Suppose you had found a solution to one of your LP7s in which 1 95 and 2 43 At this point you have a choice You can branch to exclude the 1 value of 95 or you can branch to exclude the x2 value of 43 It is your choice Pick one and go forth Assignment 1 Use the branch and bound algorithm to solve following integer program You should draw the enumeration tree You may use AMPL to solve the LP7s in your enurneration tree maximize subject to z 15z1 15z2 15z3 21 22 23 S 4 1 S 1 2 S 1 3 S 1 h z s Z 0 zlz2z3 integer 2 Use the branch and bound algorithm to solve following integer program Draw the complete enumeration tree Do not prune the tree You may use AMPL to solve the LP7s in your enumeration tree maximize subject to z 15z1 15z2 15z3 21 22 23 S 5 1 S 1 2 S 1 3 S 1 1273 Z 0 zlz2z3 integer 3 Find an IP that satis es the following conditions a The relaxation is a feasible unbounded LP b The IP is infeasible HINT Think geometrically and use vertical and horizontal lines You should strive for a simple example


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Amaris Trozzo George Washington University

"I made $350 in just two days after posting my first study guide."

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.