0
$\begingroup$

Essentially, I am working on developing a programmatic solution to an optimization problem that I've been unable to approach in a non-brute force manner. I'll do my best to explain this problem with the correct terminology, but my limited experience in this area doesn't extend beyond simple linear programming.

The problem begins with two non-integer parameters x1,x2. For constraints, we have the following (if that is the proper description):

    S = x2 - x1
    V1 = ax1, V2 = bx2    (for real numbers a, b)
    Vmin = min(V1, V2)

Further, we have the following piece-wise constant functions that will ultimately comprise our objective function:

    P1 = {
                 S > 1.5               0
                 1 < S <= 1.5          1
                 0.5 < S <= 1          2
                 1 < S <= .5           4
         }

    P2 = {
                 Vmin < 250            0
                 250 <= Vmin < 500     1
                 500 <= Vmin < 1000    2
                 1000 <= Vmin < 3000   3
                 3000 <= Vmin          4
          }

Our objective function is then simply the sum of P1 and P2.

If anyone could point me in the right direction as far as approaching, classifying or solving this problem, that'd be greatly appreciated. I've researched some other optimization problems that involved piece-wise objective functions but none seem to be quite this complex. Thanks in advance!

$\endgroup$
0
$\begingroup$

First, I think you have a typo. I'll assume that you want the last range of $P_1$ to be $(0, .5]$ rather than the somewhat empty $(1, 0.5]$. Second, be warned in advance that strict inequalities are not math programming-friendly. You may have to settle either for some ambiguity at an endpoint (for instance, $S=1$ means the solver gets to choose between 1 or 2 for $P_1$) or for some gaps in function coverage (e.g., change $1 < S \le 1.5$ to $1+\epsilon \le S \le 1.5$ for some small $\epsilon > 0$ and live with the model not allowing $S\in (1, 1+\epsilon)$).

All that said, this can be formulated as a mixed integer linear program. You have three nonlinearities to deal with: the $\min()$ operator defining $V_{min}$ and the two piecewise-linear functions.

Let's deal with $V_{min}$ first. You did not specify a direction for you objective function. If you are maximizing (so that higher values of $P_2$, and thus higher values of $V_{min}$, are preferable), you can handle this just by replacing $V_{min} =\min(V_1, V_2)$ with the two constraints $V_{min} \le V_1,\ V_{min} \le V_2$. If you are minimizing, so that smaller values of $V_{min}$ are preferable, you need those two constraints plus something to prevent the solver from picking a value of $V_{min}$ smaller than the minimum. You do that by adding a binary variable $\beta$ and the two constraints $V_{min}\ge V_1 - M_1\beta,\ V_{min}\ge V_2 - M_2(1-\beta)$. Here $M_1$ and $M_2$ are constants large enough to ensure that $V_2-M_2\le V_1$ and $V_1-M_1\le V_2$. $\beta$ essentially picks out which of $V_1$ and $V_2$ will be smaller.

On to the step functions. You introduce more binary variables, one for each step in each function. I'll illustrate for $P_1$; $P_2$ follows similarly, albeit with its own set of binary variables. Let $\alpha_0,\dots,\alpha_3$ be the binary variables (in ascending interval order for $S$). Add the following constraints: \begin{align*} \alpha_{0}+\dots+\alpha_{3} & =1\\ P_{1}(S) & = 4\alpha_0 + 2 \alpha_1 + 1 \alpha_2 + 0\alpha_3\\ S & \le0.5\alpha_{0}+1\alpha_{1}+1.5\alpha_{2}+M_{S}\alpha_{3}\\ S & \ge0\alpha_{0}+0.5\alpha_{1}+1\alpha_{2}+1.5\alpha_{3} \end{align*} where $M_S$ is an upper bound on $S$. (The $\alpha$ variables form a "Type 1 Special Ordered Set", or SOS1, which is easy to look up if you're curious.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.