Issue with constraints returning "infeasible or unbounded"

Answered

Lili Cai

October 08, 2020 14:34

• 
• 
• 

Could someone help?

The premise is I have a grocery cart of 5 items, and I want to add at least another item to the grocery cart (making it >= 6 items total).  Each item has nutrition information of 50 nutrients. The item I add should maximize the nutrient content, relative to the goal daily value. 

Here's the code. 

It returns "model is unfeasible or unbounded" 

Here's what happens depending on the constraints I define: 

prob = cp.Problem(objective,[G @ x >= j, P @ x == q])  #--> this returns "model is unfeasible or unbounded"

prob = cp.Problem(objective,[G @ x <= h, P @ x == q])     # --> this returns an optimal solution, however the optimal solution is the items I already have in the cart, the optimal solution does not add another item. This is not desirable for me because I want to add another item to the cart. 

Thanks for any help you can provide! 

 

====

import numpy as np
import cvxpy as cp

np.random.seed(1234)

N_products = 100  # number of products
N_nutrients = 50  # number of nutrients

prices = np.ones([1, N_products]) # Each item is $1
budget = 8  # Maximum $8 to spend

nutrients = np.random.rand(N_nutrients,N_products)  # nutrient composition of each product in nutrient

print('nutrient max', np.max(nutrients))
print('nutrient min', np.min(nutrients))
print('nutrient mean', np.mean(nutrients))

################## To have integer and budget constraints #####################

print('')
print('Constrained MIP')

# Objective function formulated as || Ax - b ||^2

A = nutrients
b = np.ones(N_nutrients)  # Goal amount of nutrients

# Inequality constraints (budget, max value of x ...)

G = np.concatenate((prices,np.eye(N_products),-1.*np.eye(N_products)),axis=0)
h = np.concatenate((np.asarray([budget]),np.ones([N_products]),np.zeros([N_products])),axis=0)
j = np.concatenate((np.asarray([6]),np.ones([N_products]),np.zeros([N_products])),axis=0)

# Equality constraints (if some products already selected...)

P = np.zeros([N_products,N_products])
q = np.zeros([N_products])

# If the customer has already selected a list of the products

list_selected = [4, 5, 60, 59, 96]  # List of 5 products already in cart
for index_customer in list_selected:

  P[index_customer,index_customer] = 1
  q[index_customer] = 1

x = cp.Variable(N_products, integer=True)
objective = cp.Minimize(cp.sum_squares(A @ x - b))
prob = cp.Problem(objective,[G @ x >= j, P @ x == q])

#prob = cp.Problem(objective,[G @ x <= h, P @ x == q])     # --> this yields optimal solution, but does not recommend another item

prob.solve(solver=cp.GUROBI, verbose=True)
print(x)

sol_int_cons = x.value

print("Status: ", prob.status)

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 03:06 Edited

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Lili Cai

  October 08, 2020 23:19

  • 
  • 
  • 

  Nevermind, someone offline solved the problem

  The correct format should be: 

  G = np.concatenate((-prices, prices, np.eye(N_products),-1.*np.eye(N_products)),axis=0)
  h = np.concatenate((np.asarray([-min_budget]),np.asarray([budget]),np.ones([N_products]),np.zeros([N_products])),axis=0)

  Then delete j variable 

  And use this for problem definition:

  prob = cp.Problem(objective,[G @ x <= h, P @ x == q])

  0

Post is closed for comments.