I'm trying to solve a pretty basic optimization problem using SciPy. The problem is constrained and with variable bounds and I'm pretty sure it's linear.
When I run the following code the execution fails with the error message 'Singular matrix C in LSQ subproblem'. Does anyone know what the problem might be? Thanks in advance.
Edit: I'll add a short description of what the code should do here.
I define a 'demand' vector at the beginning of the code. This vector describes the demand of a certain product indexed over some period of time. What I want to figure out is how to place a set of orders so as to fill this demand under some constraints. These constraints are;
- We must have the items in stock if there is a demand at a certain point in time (index in demand)
- We can not place an additional order until 4 'time units' after an order has been placed
- We can not place an order in the last 4 time units
This is my code;
from scipy.optimize import minimize
import numpy as np
demand = np.array([5, 10, 10, 7, 3, 7, 1, 0, 0, 0, 8])
orders = np.array([0.] * len(demand))
def objective(orders):
return np.sum(orders)
def items_in_stock(orders):
stock = 0
for i in range(len(orders)):
stock += orders[i]
stock -= demand[i]
if stock < 0.:
return -1.
return 0.
def four_weeks_order_distance(orders):
for i in range(len(orders)):
if orders[i] != 0.:
num_orders = (orders[i+1:i+5] != 0.).any()
if num_orders:
return -1.
return 0.
def four_weeks_from_end(orders):
if orders[-4:].any():
return -1.
else:
return 0.
con1 = {'type': 'eq', 'fun': items_in_stock}
con2 = {'type': 'eq', 'fun': four_weeks_order_distance}
con3 = {'type': 'eq', 'fun': four_weeks_from_end}
cons = [con1, con2, con3]
b = [(0, 100)]
bnds = b * len(orders)
x0 = orders
x0[0] = 10.
minimize(objective, x0, method='SLSQP', bounds=bnds, constraints=cons)
Though I am not an Operational Researcher, I believe it is because of the fact that the constraints you implemented are not continuous. I made little changes so that the constraints are now continuous in nature.
from scipy.optimize import minimize
import numpy as np
demand = np.array([5, 10, 10, 7, 3, 7, 1, 0, 0, 0, 8])
orders = np.array([0.] * len(demand))
def objective(orders):
return np.sum(orders)
def items_in_stock(orders):
"""In-equality Constraint: Idea is to keep the balance of stock and demand.
Cumulated stock should be greater than demand. Also, demand should never cross the stock.
"""
stock = 0
stock_penalty = 0
for i in range(len(orders)):
stock += orders[i]
stock -= demand[i]
if stock < 0:
stock_penalty -= abs(stock)
return stock_penalty
def four_weeks_order_distance(orders):
"""Equality Constraint: An order can't be placed until four weeks after any other order.
"""
violation_count = 0
for i in range(len(orders) - 6):
if orders[i] != 0.:
num_orders = orders[i + 1: i + 5].sum()
violation_count -= num_orders
return violation_count
def four_weeks_from_end(orders):
"""Equality Constraint: No orders in the last 4 weeks
"""
return orders[-4:].sum()
con1 = {'type': 'ineq', 'fun': items_in_stock} # Forces value to be greater than zero.
con2 = {'type': 'eq', 'fun': four_weeks_order_distance} # Forces value to be zero.
con3 = {'type': 'eq', 'fun': four_weeks_from_end} # Forces value to be zero.
cons = [con1, con2, con3]
b = [(0, 100)]
bnds = b * len(orders)
x0 = orders
x0[0] = 10.
res = minimize(objective, x0, method='SLSQP', bounds=bnds, constraints=cons,
options={'eps': 1})
Results
status: 0
success: True
njev: 22
nfev: 370
fun: 51.000002688311334
x: array([ 5.10000027e+01, 1.81989405e-15, -6.66999371e-16,
1.70908182e-18, 2.03187432e-16, 1.19349893e-16,
1.25059614e-16, 4.55582386e-17, 6.60988392e-18,
3.37907550e-17, -5.72760251e-18])
message: 'Optimization terminated successfully.'
jac: array([ 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 1., 0.])
nit: 23
[ round(l, 2) for l in res.x ]
[51.0, 0.0, -0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, -0.0]
So, the solution suggests to make all the orders in the first week.
- It avoids the out of stock situation
- Single purchase(order) respects the no order in the next four week after an order.
- No last 4 week purchase