Author 
Message 
Fan science forum beginner
Joined: 31 Dec 2005
Posts: 7

Posted: Tue Jul 11, 2006 7:05 pm Post subject:
How to solve the linear objective function with max function, and linear constraints?



Consider the following problem: a piecewise linear objective function
with max function, and linear constraints.
Is this still a linear program? What solver can find the solution
quickly?
E.g., x belongs to R_3. Define the max function [y]_+ = max {0,y}.
min [5x_1  4x_2]_+ + [3x_3  x_1]_+
s.t. x >= 0,
x_1 + 3x_2 > 4
Thanks,
Fan 

Back to top 


Robert B. Israel science forum Guru
Joined: 24 Mar 2005
Posts: 2151

Posted: Wed Jul 12, 2006 8:47 pm Post subject:
Re: How to solve the linear objective function with max function, and linear constraints?



In article <1152644735.439243.76610@s13g2000cwa.googlegroups.com>,
Fan <fyanguw@gmail.com> wrote:
Quote:  Consider the following problem: a piecewise linear objective function
with max function, and linear constraints.
Is this still a linear program? What solver can find the solution
quickly?

It is not a linear programming problem. In some cases
(minimizing a convex piecewise linear objective, or maximizing
a concave one) it can be written as one.
Quote: 
E.g., x belongs to R_3. Define the max function [y]_+ = max {0,y}.
min [5x_1  4x_2]_+ + [3x_3  x_1]_+

Since the max of linear functions is convex, this is OK. You can
write it as
min p_1 + p_2
s.t. p_1 >= 5 x_1  4 x_2
p_1 >= 0
p_2 >= 3 x_3  x_1
p_2 >= 0
(and your other constraints)
Quote: 
s.t. x >= 0,
x_1 + 3x_2 > 4

I hope you mean >=. Strict inequality constraints, when
they aren't redundant, mean there won't be any optimal solutions.
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada 

Back to top 


C W science forum addict
Joined: 25 May 2005
Posts: 64

Posted: Wed Jul 12, 2006 11:53 pm Post subject:
Re: How to solve the linear objective function with max function, and linear constraints?



Fan wrote:
Quote: 
Consider the following problem: a piecewise linear objective function
with max function, and linear constraints.
Is this still a linear program? What solver can find the solution
quickly?
E.g., x belongs to R_3. Define the max function [y]_+ = max {0,y}.
min [5x_1  4x_2]_+ + [3x_3  x_1]_+
s.t. x >= 0,
x_1 + 3x_2 > 4

If the conmstraints read :
x_1>=0,x_2>0,x_3>=0,x_1 + 3x_2 >= 4
then min [5x_1  4x_2]_+ + [3x_3  x_1]_+ = 0 at [x_1,x_2,x_3] = [16/19, 20/19,
0] is the minimum.


Back to top 


Google


Back to top 



The time now is Mon Aug 20, 2018 5:39 am  All times are GMT

