Binary and Integer Program in Python

Question

I have a binary/integer program that I am trying to solve using milp in Python. Below the image and below is the code I have so far. When I run it, I get

`bounds.lb` and `bounds.ub` must contain reals and be broadcastable to `c.shape`.

I believed I accounted for the upper and lower bounds in the "bounds" variable. But apparently not. What is missing?

from scipy.optimize import linprog
import numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds 
c = [3, 5, 7, 9, 2, 8, 6, 4, 1]  # x1 to x9 (office setup cost multipliers)
c = c + [0]*36     


A = [
    [1700, 3600, 2100, 2500, 3100, 2700, 4100, 3400, 4100] + [24.3]*9 + [32.4]*9 + [28.9]*9+[26]*9,  # Setup and transfer costs
    [0, 0, 0, -1, 0, -1, 1, 0, 0] + [0]*36,  # x7 <= x4 + x6
    [1, 0, 0, 0, 0, 1, 0, 0, 0] + [0]*36,  # x1 + x6 <= 1
    [0]*9 + [1]*9 + [0]*27,  # Chicago
    [0]*18 + [1]*9 + [0]*18,  # Charlotte
    [0]*27 + [1]*9 + [0]*9,  # Pittsburgh
    [0]*36 + [1]*9   # Houston
]

b = [
    14000,  
    0,  
    1,  
    29, 
    22, 
    19,  
    27,  
]

# Define bounds for each variable (0 <= xi <= 1 for binary variables, 0 <= yij)
x_bounds = [(0, 1)] * 9  # Bounds for the x variables
y_bounds = [(0, None)] * 36  # Bounds for the y variables (unbounded upper limit)

# Combine bounds
bounds = x_bounds + y_bounds

integrality = ([1]) * 45

milp(c, integrality = integrality,
    bounds = Bounds(bounds),
     constraints = LinearConstraint(A, b))

Oskar Hofmann · Accepted Answer · 2024-03-15 23:15:36Z

1

There are two issues with your code. First, to disable bounds or define "unbounded bounds", one should use np.inf or -np.inf instead of None.

Second, you are currently giving a list of tuples to scipy.optimize.Bounds which does not work. Instead you should provide a list of the lower bounds and a list for the upper bounds.

To resolve these issues, you can change the last part of your code to:

# Define bounds for each variable (0 <= xi <= 1 for binary variables, 0 <= yij)
x_bounds = [(0, 1)] * 9  # Bounds for the x variables
y_bounds = [(0, np.inf)] * 36  # Bounds for the y variables (unbounded upper limit)

# Combine bounds
bounds = x_bounds + y_bounds

integrality = ([1]) * 45

l_bounds = [x for (x,y) in bounds]
u_bounds = [y for (x,y) in bounds]

milp(c, integrality = integrality,
    bounds = Bounds(l_bounds, u_bounds),
     constraints = LinearConstraint(A, b))

Instead of the list comprehension you could also use the zip function for a more concise solution:

l_bounds, u_bounds = zip(*bounds)

or directly

bounds = Bounds(*zip(*bounds))

Personally, I prefer the solution using list comprehension as it is clearer to the reader what is happening and with lists of this length, performance is not really an issue.

edited Mar 15, 2024 at 23:15

answered Mar 15, 2024 at 20:23

Oskar Hofmann

8676 silver badges16 bronze badges

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

1 Comment

gunsnfloyd Over a year ago

Ah! I see, thank you! Now I see that my program is not set up correctly, which is a completely different issue.

Collectives™ on Stack Overflow

Binary and Integer Program in Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related