MILP optimizer in Python Pyomo/PuLP not finding a feasible solution with open-source solvers

136 views Asked by At

I am looking to utilize an optimizer in Python for solving the following use case:

I have n orders of different widths. These n orders need to be combined together to form multiple patterns.

Following are the constraints:

  1. Each order can be assigned only once.
  2. The combined width of a pattern should be greater than 335 and lesser than 340

My objective function is to maximize the quantity assigned to different patterns.

I have utilized PuLP in Python and tried multiple solvers. Only CPLEX is giving a viable solution (more than 90% of orders have been assigned to multiple patterns in CPLEX while other solvers are giving 0% solution - have run for more than 2 hours). However, I have to utilize an open-source solver for final deployment. I have tried glpk and cbc solvers through Pyomo and PuLP as well. Can I use any other solver or can I modify the code so that a solution is found through glpk or cbc?

There are around 500 orders which need to be assigned.

Following is the code:

import pulp

# Create a LP problem
problem = pulp.LpProblem("Assign_Orders", pulp.LpMaximize)

# Decision variables
num_orders = len(df_order)  # Number of orders
num_patterns = round(len(df_order)/4)  # for pattern assignment

# Binary variable for order assignment
assign = pulp.LpVariable.dicts("Assign", ((i, j) for i in range(num_orders) for j in range(num_patterns)), cat='Binary')

# Binary variable for pattern selection
pattern = pulp.LpVariable.dicts("Pattern", range(num_patterns), cat='Binary')

# Objective function - for maximizing total assigned orders, Column name is width new; order width
problem += pulp.lpSum(df_order.iloc[i]['Width new']*assign[i, j] for i in range(num_orders) for j in range(num_patterns))

# Constraints
# Each order must be assigned to exactly one pattern
for i in range(num_orders):
    problem += pulp.lpSum(assign[i, j] for j in range(num_patterns)) <= 1

# Capacity constraint for each pattern - total width should not exceed a limit

for j in range(num_patterns):
    problem += pulp.lpSum(df_order.iloc[i]['Width new'] * assign[i, j] for i in range(num_orders)) <= 340 * pattern[j]
for j in range(num_patterns):
    problem += pulp.lpSum(df_order.iloc[i]['Width new'] * assign[i, j] for i in range(num_orders)) >= 335 * pattern[j]

# Solve the problem

problem.solve() # have tried multiple solvers here such as glpk, default solver and cplex. only cplex is giving a solution
0

There are 0 answers