scipy minimize SLSQP - 'Singular matrix C in LSQ subproblem'

Question

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)

Micronesia

If the model is linear, SLSQP is not really a good candidate to solve it. A solver for linear models would be more an obvious choice. – Mittel

Thanks for the quick reply. I looked into scipy's linprog module but I'm having a hard time defining some of my constraints. For instance, the 'four_weeks_order_distance' method imposes a constraint which basically says that an order can't be placed until four weeks after any other order. This constraint doesn't really translate well into matrix form, or atleast from my experience level. – Micronesia

Counting is typically done using binary variables. Linear solvers supporting binary variables are called MIP (Mixed Integer Programming) solvers. Scipy does not have one (but MIP solvers for use in a Python environment are readily available). Your constraint as stated is bad for SLSQP, as it violates smoothnes assumptions. – Mittel

Answer 1

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

Depositary

if and abs are not twice continuously differentiable. It may work sometimes, but again, this is violating the smoothness assumptions of SLSQP. – Mittel

can be asked directly at OR.stackexchange.com – Gramineous