Using scipy linprog

Question

Let's say I have the following problem:

objective function c1x1 + c2x2 (we need to minimize it)
-x1 + x2 <= 0
0 <= x1 <= 3
0 <= x2 <= 2

We also assume that c1 = 1 and c2 = -0.5 and another constrain has been added c1x1 + c2x2 = P, were P = -1,0,1.

What is the right way to use linprog in order to solve this problem? is bounds refer to lower bounds?

Thanks for helping.

What do you mean by your equality constraint? Surely, constraining the same expression to equal three different things renders your program infeasible. — fuglede
– fuglede, Commented Nov 24, 2019 at 20:58

fuglede · Accepted Answer · 2019-11-24 21:19:54Z

1

Ignoring the issue about the impossible equality constraint mentioned in the comment, we only have to refer to the documentation:

A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub

Here, lb is 0 by default, so you don't have to bother with the lower bounds at all, and your problem boils down to c = [1, -0.5], A_ub = [[-1, 1], [1, 0], [0, 1]], and b_ub = [0, 3, 2]:

In [57]: linprog(c, A_ub, b_ub)                                                                          
Out[57]: 
     con: array([], dtype=float64)
     fun: 9.37460773860971e-11
 message: 'Optimization terminated successfully.'
     nit: 4
   slack: array([7.91922932e-11, 3.00000000e+00, 2.00000000e+00])
  status: 0
 success: True
       x: array([1.08299862e-10, 2.91075683e-11])

That is, up to numerical issues, the optimal solutions is x1 = x2 = 0 (which is also fairly obvious: The only way to get a negative objective would be let x2 be positive, but your first constraint would then require that x1 be at least as large as x2, which in turn causes your objective to become positive).

edited Nov 24, 2019 at 21:19

answered Nov 24, 2019 at 20:59

fuglede

18.3k3 gold badges62 silver badges107 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

AvivSham Over a year ago

In case the lower bound is not zero, how do I use lb when calling the function? I assume it relates to bounds arg. can you please show me how?

fuglede Over a year ago

Yes, as per the documentation "Note that by default lb = 0 and ub = None unless specified with bounds." Moreover, the documentation for bounds specifies that you should provide a tuple for each variable, e.g. something like [(-5, 10), (-4, 5)] to specify that -5 <= x1 <= 10 and -4 <= x2 <= 5. Alternatively, lower bounds can be encoded in A_ub directly by flipping the sign.

Collectives™ on Stack Overflow

Using scipy linprog

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related