How to Convert or Solve a Non-Linear Optimization Problem with Non-Linear Objective Function & Constraints

Question

Overview

I am working on an order allocation problem with variable and fixed costs. The initial formulation of this problem was a linear optimization, but when fixed and variable costs were introduced, it required the formulation to be non-linear due to the decision variable (Xij being multiplied with the switching variable Sj). Now that the formulation has changed, I have the following questions:

• Is the formulation of the problem correct?
• If the formulation is correct: Can the problem be converted to an equivalent linear optimization problem instead of nonlinear? If so, what would the formulation be?
• If the formulation is correct and it cannot be converted into a linear form: How can the problem be solved as a nonlinear problem in a program such as Python? Which solver can be used?
• I initially used the PuLP library, but the package gave an error because of the nonlinear form of the problem.

Problem Statement

Order No.	Product	Process Time (hours)	Site 1	Site 2	Site 3
1	P1	MH1	X11	X12	X13
2	P2	MH2	X21	X22	X23
3	P3	MH3	X31	X32	X33
4	P4	MH4	X41	X42	X43
5	P5	MH5	X51	X52	X53
6	P6	MH6	X61	X62	X63

Site 1	Site 2	Site 3
Fixed Capacity (hours)	FCa1	FCa2
Fixed Cost	FCo1	FCo2
Variable Cost	VCo1	VCo2

• MH1 = Man hours required to build P1
• X11 = Binary Variable
• 1: If product P1 is decided to be built in Site 1
• 0: If product P1 is decided to not be built in Site 1
• FCa1 = Fixed capacity at Site 1
• FCo1 = Fixed Cost at Site 1
• VCo1 = Variable Cost at Site 1

A company has 3 manufacturing sites, and it must decide on how to allocate various products to all three sites to reduce manufacturing cost meeting all the constraints. The constraints are that all products must be built and only in one site. The man hours required to build the product in the manufacturing site is mentioned in the above table as MH.

In every site there is a fixed manufacturing capacity (FCa) in terms of man hours it can process, and this fixed capacity has an associated fixed cost (FCo). If the allocation of orders to the site is less than the fixed capacity for a site, it will have total cost equal to fixed cost and if the allocation is greater than the fixed capacity a Variable Cost (VCo) would kick-in.

Example: If site has a fixed capacity say 2000 hours with an associated fixed cost of $100,000 and variable cost of $100 per hour after that.

Case 1: Allocation to the site is less than the fixed capacity of the site Suppose the allocation of orders is equal to 1800 MH ⟹ Total Cost would be $100,000.

If order allocation < FCa
Total Cost = FCo

Case 2: Allocation to the site is greater than the fixed capacity of the site Suppose the allocation of orders is equal to 2100 MH ⟹ Total cost would be $110,000.

If order allocation > FCa
Total Cost = FCo + (order allocation - FCa) × VCo

Indices

i = Orders: (1,2,3,4,5,6)
j = Sites: (1,2,3)

Decision Variable

Xij: binary integer decision of order i being built in site j

Parameters

MHi = Man hours required to build product i

FCaj = Fixed capacity at site j

FCoj = Fixed cost at site j

VCoj = Variable cost at site j

Objective Function

Objective Function

Constraints

Switching Variable Constraints

Switching Variable Constraint #1

When Fixed Capacity > Order Allocation:
⟹ sj = 0 and the objective function will consider fixed cost only

Switching Variable Constraint #2

When Fixed Capacity > Order Allocation:
⟹ sj = 1 and the objective function will consider fixed cost and variable cost

Order Allocation Constraint

Make sure all the products are allocated and being built at one site: Order Allocation Constraint

Answer 1

1. PuLP only does linear models. For non-linear models, you need to use different tools.

2. A product like X[i,j]*s[j] where X is a continuous variable and s binary variable can be linearized as follows.

Let XS[i,j]=X[i,j]*s[j] with XS a non-negative continuous variable. Further let 0 <= X[i,j] <= U[i,j]. I.e. we know an upperbound on X (capacity). So we have:

  X[i,j]  ∈ [0,U[i,j]]
  XS[i,j] ∈ [0,U[i,j]]

Then we can write:

  XS[i,j] <= U[i,j]*s[j];
  XS[i,j] <= X[i,j]
  XS[i,j] >= X[i,j]-(1-s[j])*U[i,j]

To verify:

case 1: s[j]=0. Then we have

  XS[i,j] <= 0;
  XS[i,j] <= X[i,j]
  XS[i,j] >= X[i,j]-U[i,j]
  
  ==> XS[i,j] = 0

case 2: s[j]=1. Then we have

  XS[i,j] <= U[i,j];
  XS[i,j] <= X[i,j]
  XS[i,j] >= X[i,j]
  
  ==> XS[i,j] = X[i,j]