Advanced Techniques for Modeling with Piecewise Linear Functions
Explore advanced modeling techniques using piecewise linear functions to address non-binary variables in constrained optimization problems. Learn how to incorporate cost functions and optimize production decisions effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
IP modeling techniques III In this handout, Modeling techniques: Making choices with non-binary variables Piecewise linear functions
Making choices with non-binary variables Recall the furniture manufacturer problem. Extra requirement: From the 3 possible products (tables, chairs, desks), at most two should be chosen to be produced. That is, at most two of xt , xc, xdcan be non-zero. How to achieve this in the model? Introduce new binary variables. For i=t,c,d, = cannot i product if 0 (x 1 if produced be can i product (x 0) i y i = produced be 0) i To enforce the requirement, need the following constraint: yt + yc + yd 2 Need also to relate xi s and yi s. Add constraints: xi Myi for i=t,c,d and large positive M
Piecewise linear functions So far all our functions were linear. In many situations, it might not be the case. Example: Production cost. c1= $11/unit for first 5 items c2= $8/unit for next 4 items c3= $5/unit for next 7 items c4= $7/unit for next 10 items The cost of producing x items is an example of so-called piecewise linear function: + = 4 8 5 11 11 0 5 x if x 11 5 ( 8 ) 5 5 9 x if x ( ) f x 5 + 4 + ( 5 ) 9 9 16 x if x + + + 11 8 5 7 ( 7 16 ) 16 26 x if x
Piecewise linear functions How to include piecewise linear cost functions in an objective function of IP? Idea: Introduce a new variable for each cost segment. For i=1,2,3,4 yi= number of items produced at cost ci Then the total number of items is x = y1+y2+y3+y4. We need constraints 0 y1 5, 0 y2 4, 0 y3 7, 0 y4 10 , and the production cost in the objective function is 11y1 + 8y2 + 5y3 + 7y4 What is the shortcoming of this model? (*)
Piecewise linear functions We should require that y2>0 implies that y1=5 y3>0 implies that y2=4 y4>0 implies that y3=7 Introduce new variables to translate these requirements into linear constraints. For i=1,2,3,4, = otherwise 0 (1) (2) (3) 1 if y upper its at is bound i w i Proper constraints relating wiand yiwill provide that requirements (1)-(3) are satisfied. y2 4w1and 5w1 y1provide (1) y3 7w2 and 4w2 y2provide (2) y4 10w3and 7w3 y3provide (3)
Piecewise linear functions Summarizing, the bound constraints in (*) should be substituted with 5w1 y1 5, 4w2 y2 4w1, 7w3 y3 7w2 , 0 y4 10w3. Generalizing, suppose we have k segments with lengths L1, L2, , Lk. Then the necessary constraints: L1w1 y1 L1, Liwi yi Liwi-1 for i = 2, , k-1 0 yk Lkwk-1
