Pricing of blends/mixtures across multiple timesteps

Question

I have a simple blending problem, where each final product is a blend or mixture of several raw materials, and want to calculate the price per unit of weight for each of the products. So for a given product, the price $P$ per unit weight is given by:

$$ P = \frac{p_1 x_1 + p_2 x_2 + \dots + p_n x_n}{x_1 + x_2 + \dots+ x_n} $$

where the $x_i$ are the weights of each of the constituent raw materials (the decision variables), and the $p_i$ are the prices per unit weight of the raw materials (constants in each time period).

There are other constraints on the proportions of each raw material that can be present in the final product, but these are typically quite wide ranges and are not difficult to achieve, so are not directly relevant here.

This is also a multi-time period problem. The raw material availabilities and prices vary from one week to the next, and the amount of each product required each week also varies. The blend of the raw materials in the product is allowed to vary from one week to the next.

An important constraint in the overall problem is that the price per unit weight of the product must not differ by more than a small amount (maybe 5 - 10%) from one week to the next, so if we have the final product unit prices for each week as $P_1, P_2, \dots, P_m$ then we need constraints like:

$$ 0.9 P_{i-1} \le P_i \le 1.1 P_{i-1} $$

so that the unit price of the product cannot change more than 10% from one week to the next.

I am using a MILP solver for this problem, and this is giving me an issue because this expression for the price of the final product involves the division of one expression by another, where both the numerator and denominator contain decision variables. I cannot yet see how I can reformulate this model to linearise it.

So does anyone have a way to restructure or reformulate this problem model so that I can model the final product unit prices and limit the variability of the final product prices from one week to the next in a multi-period problem using MILP?

Answer 1

I don't think a MILP is in the cards. Here's one formulation that at least might be (somewhat) solvable. In the formulation, $i$ indexes a product, $j$ indexes a raw material and $t$ indexes a time period. Parameters are the cost of a material ($p_j$), the penalty for each unit shortfall in production of a product ($c_i$), and the demand for each product ($D_{it}$). Variables are the fraction of a product that comes from a raw material in a given period ($r_{ijt}$), the quantity of a product made in a period ($q_{it}$), the shortfall of a product in a period ($s_{it}$), and the unit cost of the output of a product in a period ($P_{it}$). I'm assuming that inventory carryover is not allowed, but if it is, inventory terms are easy to add.

All variables are nonnegative. The first constraint is $$\sum_{j}r_{ijt}=1\,\forall i,t,$$ which enforces the fact that the $r$ variables are mixture proportions. Next, $$q_{it} + s_{it}=D_{it}\,\forall i,t$$ defines shortfalls. $$P_{it} = \sum_{j} p_j r_{ijt}\,\forall i,t$$ defines the unit production costs for the outputs. Finally, $$0.9P_{i,t-1}\le P_{i,t}\le 1.1P_{i,t-1}\,\forall i,\forall t>1$$ is your limitation on product variability.

So far everything is linear. Where we get in trouble is the objective function:$$\min \sum_t\sum_i (P_{it} q_{it} + c_i s_{it}).$$ The objective function is not convex (nor concave), so you cannot just hit it with any old MILP solver. I believe that CPLEX (and perhaps Gurobi?) can solve problems like this one. There are special purpose solvers for nonconvex problems (although I'm not familiar with any). You can also try approximating the quadratic portion with piecewise linear functions (which will give you an approximate solution).

Answer 2

You can introduce a continuous variable $y$ such that $$\frac{p_1 x_1 + p_2 x_2 + \dots + p_n x_n}{x_1 + x_2 + \dots+ x_n} = y.$$ Multiplying by the denominator gives $$p_1 x_1 + p_2 x_2 + \dots + p_n x_n = x_1y + x_2y + \dots+ x_ny.$$ This turns your problem into a non-convex (MI)QCQP (abbreviation list), depending on whether you have integer variables or not.

Manual reformulation

Depending on you problem, you may be able to linearize the quadratic constraints. If the $x_i$ are binary, you can linearize the product $x_i y$ as explained on StackExchange and on OR in an OB World in more detail. Something similar can be done when the $x_i$ are integer.

If the $x_i$ are not integer, you can make your own discretization to obtain an approximation of the optimal solution. For example, if you only allow prices $P \in \{0, 0.1, 0.2, \dots, 1\}$, you may add the variable $z \in \{0,1,2,\dots,10\}$ and substitute $y = 0.1z$. Then, you can linearize the product $(x_1 + x_2 + \dots+ x_n) z$ as above, etc.

Software

Instead of reformulating yourself and using a MILP solver, there may be software to help you.

• As mentioned by prubin, CPLEX can solve non-convex quadratic programs, but only if the constraints are linear (i.e., MIQP instead of MIQCQP). Hence, if you are able to put all quadratic terms in the objective, you can use CPLEX.
• Gurobi does not seem to support non-convex problems at this time. If I recall correctly, they are planning to add support for MIQCQP in version 9.0. This conference talk at least seems to hint in this direction.
• Global optimization software exists, but I am less familiar with it. It seems that BARON might be able to solve your problem.

Create your own method

You may also create your own algorithm. The following paper explains how CPLEX deals with non-convex quadratic objectives. This might not be sufficient for your problem, but the ideas may be useful.

Bliek, C., Bonami, P., & Lodi, A. (2014, October). Solving mixed-integer quadratic programming problems with IBM-CPLEX: a progress report. In Proceedings of the twenty-sixth RAMP symposium.