1. Transforming non-linear problems
We've covered linear programming, convex constrained optimization, and mixed integer linear programming. Next, we'll explore transforming non-linear problems with three examples, followed by global optimization and sensitivity analysis.
2. Maximize a non-linear function
In our first example, an artist can produce up to 16 similar paintings before starting a new commission. The cost function C of q equals the square root of q where q is the number of paintings made. Inverse demand for the paintings is p equals 3 over the square root of q.
Inverse demand calculates demand as a function of quantity rather than price. For instance, with multiple prints of a painting, people may pay less per item compared to a single print where they may pay more.
How many paintings should the artist produce to maximize profit?
To find profit, we subtract cost from revenue, which simplifies to 2 times the square root of q.
We also need to consider that q is less than or equal to 16.
3. SciPy or PuLP?
Should we use SciPy or PuLP?
Since SciPy's milp requires a linear objective, let's go with PuLP.
We'll define a model, a variable and the objective.
PuLP doesn't accept powers of LpVariables, but there's a workaround.
4. Substitute to linearize
Substituting z equals the square root of q linearizes our objective.
The constraint also required substituting q with z squared being less than or equal to 16, or equivalently z being less than or equal to 4.
Both PuLP and SciPy can solve this now. Remember to convert z back to q after solving.
The optimal number of paintings is 16.
5. Capital budgeting with dependent projects
Now, let's examine a budgeting problem involving binary and continuous variables.
A firm considers three projects, A, B and C, where A is a prerequisite for B. The projects yield profits, V, of $250, $200 and $300, respectively, in the thousands. The initial investments, I, required are $2000, $1900, and $2500.
With only $4600 for investment, let's model the problem.
Define binary variables oA, oB, and oC to indicate project selection.
For project B, both oA and oB must be 1 to proceed.
The objective is to maximize profit by summing project profits while ensuring the total investment does not exceed $4600.
6. Linearization: product of binaries
We introduce a new variable, oAB, to replace the binary product of projects A and B, maintaining the constraints. oAB must be less than either original binary variable for A and B and greater than their sum minus one. This ensures oAB can only be one if both A and B projects are selected. This technique preserves the linearity of the problem, avoiding the nonlinearity introduced by the product of binary variables.
The profit maximization problem now incorporates the new variable. Along with the $4600 investment limit, it must adhere to the constraints on AB. The solving steps remain unchanged; you'll solve this in the exercises.
7. Resource allocation with training cost
In our final example, a manager allocates 120 tasks to a senior a junior and an intern software engineer with objective to minimize cost.
Before taking on any tasks, the intern must undergo training that costs $500. The variable c represents the cost per task for each team member, reflecting their productivity and salary. Let x be the vector of optimally assigned tasks, and o be a binary variable indicating whether the intern receives training. The total cost, TC, is calculated as the sum of the product of the cost and the number of tasks per team member.
Our formula involves a non-linear product of a binary and a continuous variable, so linearization is required.
8. Linearization: product of binary and continuous
The BigM method replaces the product of the binary and continuous variable by introducing a large number, M.
It replaces the product with a new variable, z, and stipulates that when o is one (indicating the intern is trained), z equals the product. Conversely, when o is zero, there is no cost associated.
9. Let's practice!
Alright, let's practice these skills!