### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Intro Integer Prog IOE 518

UM

GPA 3.76

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Industrial Engineering

This 5 page Class Notes was uploaded by Loy King on Thursday October 29, 2015. The Class Notes belongs to IOE 518 at University of Michigan taught by Staff in Fall. Since its upload, it has received 20 views. For similar materials see /class/231597/ioe-518-university-of-michigan in Industrial Engineering at University of Michigan.

## Reviews for Intro Integer Prog

### 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/29/15

Lecture 3 Valid inequalities Last time gt Examples of MIP formulations including gt Disjunctive constraints gt Uncapacitated Facility Location UFL gt Uncapacitated Lot Sizing ULS gt Comparing IP formulations for feasible region X gt Polyhedral view of a formulation X P Zquot gt Ideal formulation convX gt Better formulations Today gt Identifying valid inequalities gt Strengthening the formulation by adding valid inequalities gt Cutting plane algorithms next time Leculre 3 Formulations better and best Recall gt Pure IP gt Feasible region ofan IP X X AX b X E 21 gt A formulation of the set X polyhedron P C Rquot such that P W Zquot X gt Mixed IP gt Feasible region of a MIP XWyElRquotgtltZiAwG b gt A formulation of the set X polyhedron P E R Hp such that Pm Rn X 2quot x gt Stronger formulation if P1 and P2 are two formulations ofX and P1 C P2 P1 is a stronger formulation gt Ideal formulation convX if it s a polyhedron Proposition 81 convX is a polyhedron if A7 C7 b are rational We will always be assuming the IP data is rational from now on Formulallon revlew Motivation strengthening formulations of difficult IPs gt Solving maXcTX X E X is the same as solving maXcTX X E convX gt If we can find A 3 such that convX X AX g b X Z O we can solve our IP or MIP as an LP maXcTX AX g b X Z O gt Easy to do for some classes of problems but hard for most gt Can we improve the formulation of a particular instance of the problem Formulatlon review Valid inequalities Definition 81 An inequality 7TTX 3 no is a valid inequality for set X g R if 7TTX no for all XEX For example if X X E Z AX g b and convX X E R AX g then all of the constraints aITX g b and ITX g b are valid inequalities for X gt Idea given a formulation P for X identify additional valid inequalities for X and add them to the formulation quotcuttingquot away regions of P that contain no feasible solutions and thus obtaining better formulations for X gt Can be done as a pre processing step or in an ad hoc manner Valid Inequalllla Examples of valid inequalities Example 1 Logical inequalities X X6 85 3X1 4X22X3 3X4X5 g 2 Observe gt If X2 2 X4 0 then 3X1 2X3 X5 g 2 impossible Hence X2 X4 Z 1 is a valid inequality gtle1 2 1 and X220 then O 32X3 3X4X5 g 2 impossible Hence X1 3 X2 is a valid inequality Valid Inequallus Examples of valid inequalities continued Example 2 Mixed O 1 set XXyx 9999y7 O X 57 ye Bl Then X g min579999y is a valid inequality Application Consider a capacitated facility location problem with client demands 3 i e M and capacities of potential depots bj7 j E N Feasible region characterized by Dem Xij S bjyj W E V Ejeinj a for Vi e M XUZOVIGMJEN yjeO1VjeN Valid inequalities xij g minbjayj for all i and j Valid Inequalllla Examples of valid inequalities continued Example 3 Mixed integer set XXyxg 10y ngg 14 y Z The inequality X g 14 42 y 6 4y is valid To see how we came up with it draw the feasible region Generalization if XcxyxCy osxsb yea where C does not divide b the inequality X b K y whereK andcyzb CK 1 is a valid inequality for X Valid Inequallus Maximum cardinalityweight matching problem Given a graph G V E a matching is a set of disjoint edges We are usually interested in finding a matching of maximum cardinality or maximum total weight if we are given a weight for every edge IP formulation forie V let 6ie Eeij forsomeje V max 2X6 st Zea axe g 1 ie V in X6 23 Valid Inequalllla Examples of valid inequalities continued Example 4 Combinatorial set matchings Consider the set X of incidence vectors of matchings XXEZ E I Z XeglforallieV7 e66i where 6i e e E e 2 OJ for somej E V Let T g V have odd cardinality Let E T be the set of edges having both endpoints in T Then 2 XeSITIT l e ET is a valid inequality valid Muslims Examples of valid inequalities continued Example 5 Integer rounding Consider X P 0234 where P x e 1R1 13x1 20X2 11X3 6X4 2 72 All inequalities below are valid gt Multiply both sides by X1 X2 X3 X4 2 gt Round the LHS coefficients up 2X1 2X2 X3 X4 Z gt Round the RHS coefficient up 2X1 2X2 X3 X4 2 7 Note that the point x 07 07 667 O E P violates the newly derived valid inequality thus adding it improved our relaxation valid Inequalities

### 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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.