6

I am new to thinking about math programming and I have a particular constraint I am hoping to reformulate, I just don't know the proper mathematical translation for what I am hoping to do. Enforcing the non-negativity constraint on $X$ in Constraint (1) seems to make my model infeasible, and so I am hoping that with a reformulation of my problem the solver I am using (knitro) will be able to report feasibility.

My original constraint looks like this:

$$ X_{t} = X_{t-1} + aY_{t-1} - Z_{t-1}, \quad t\in[1,T] \tag1 \\X_{t} \ge 0 \\ \\ X_{0}, Y_{0}, Z_{0} \ge0 $$

The way that I am thinking about the new formulation is shown in Constraint (2), but I feel that this is where I will need some correction on the formulation:

$$ X_t = \begin{cases} 0, & \text{if} \quad X_{t-1} + aY_{t-1} - Z_{t-1} \le 0 \\ X_{t-1} + aY_{t-1} - Z_{t-1}, & \text{otherwise} \end{cases} \tag2 \\t\in[1,T] \\ X_{0}, Y_{0}, Z_{0} \ge0 $$

I apologize if this is straightforward, I just don't know the precise wording to Google my problem because this is not my field of study.

If someone would be able to (1) help me classify what type of constraint this would be called and possibly a way to linearize it or a useful resource I can follow up on, I would be appreciative of that.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
GrayLiterature
  • 2,309
  • 7
  • 27
  • If your $t$ index starts from 1, what happens to $X_{t-1}$? Do you have an initial value for your first (or here, zeroth) index? – EhsanK Oct 08 '19 at 13:28
  • @EhsanK I updated the problem formulation. But you are correct, t starts from 1 and there are initial values supplied so that X_(t=1) would exist. – GrayLiterature Oct 08 '19 at 13:48
  • 2
    If $a$ is a parameter (not a decision variable) then constraint (1) is linear, and constraint (2) is not. So constraint 91) should be the way to go. If you are finding that your model is infeasible, it is not due to any nonlinearity, but due to something else in your model or your data. – LarrySnyder610 Oct 08 '19 at 13:57
  • Oh, I see -- the problem is that you are setting $X_t$ equal to something in the first constraint, and then requiring it to be nonnegative. If the first constraint sets it equal to something negative, the second constraint will be violated. In cases like this, sometimes you can replace the first constraint with $\ge$, assuming that your objective function wants to minimize $X_t$. – LarrySnyder610 Oct 08 '19 at 13:58
  • You could also try to adapt the approach here – LarrySnyder610 Oct 08 '19 at 13:59
  • 1
    Your first formulation would result in infeasibility if any $X_t$ came out $< 0$. Your 2nd formulation amounts to $ X_{t} = \text{max}( X_{t-1} + aY_{t-1} - Z_{t-1},0)$. plus any constraints on the Y 's and Z 's. The best way to handle that depends on the rest of the model and on the solver. – Mark L. Stone Oct 08 '19 at 14:02
  • @LarrySnyder610 This is exactly where I believe the infeasibility in my problem is occuring. When I do not implement a non-negativity constraint on X then constraint (1) eventually becomes negative because of Z overpowering the other 2 positive terms, but when I impose the non-negativity constraint, I get the infeasibility. So I guess with the responses that both you and Mark wrote, formulating the problem as a max constarint might be a possible path to go down. – GrayLiterature Oct 08 '19 at 14:07
  • To put some context into the problem. You can imagine that if the problem setting was in a forest and X represented the growth of trees, Y was something like planting new trees, and Z represented tree harvesting - then you might harvest too much, but you can never have "negative" trees, the least amount of trees you can have would be 0. – GrayLiterature Oct 08 '19 at 14:10
  • 1
    Edit to my comment: Didn't see @Larry comments before mine. Yes, you can do per his link, which requires bnary variables which KNITRO can handle, but if the overall model (excluxding binaries) is not convex, KNITRO's solution will be heuristic (could be totally "wrong"). Other approach is depending on front end used, directly implement max, and hope to blast through any non-diffeerentiabilities. – Mark L. Stone Oct 08 '19 at 14:12
  • @Mark L. Stone The method Larry mentioned worked for me. In fact, if you recall I had posted the other day about this exact equation reporting infeasibilities, and formulating the constraint as a maximum actually helped to alleviate the infeasibility that I was facing. – GrayLiterature Oct 08 '19 at 15:12

1 Answers1

6

Solution provided by LarrySnyder610, full original post can be found here:

We want a set of constraints that enforces $X = \max\{x_1,x_2\}$. Define a new binary decision variable $y$, which will equal 1 if $x_1 > x_2$, will equal 0 if $x_1 < x_2$, and could equal either if $x_1 = x_2$. Let $M$ be a constant such that $x_1,x_2 \le M$ in any "reasonable" solution to the problem.

The following constraints enforce the definition of $y$: $$\begin{align} x_1 - x_2 & \le My \\ x_2 - x_1 & \le M(1-y) \end{align}$$ Then, the following constraints enforce $X = \max\{x_1,x_2\}$: $$\begin{align} X & \ge x_1 \\ X & \ge x_2 \\ X & \le x_1 + M(1-y) \\ X & \le x_2 + My. \end{align}$$ The first two constraints say $X \ge \max\{x_1,x_2\}$, as you suggested in the question. Combined with these constraints, the last two constraints say that $X = x_1$ if $x_1 > x_2$ (so $y=1$) and $X = x_2$ if $x_2 > x_1$ (so $y=0$).

GrayLiterature
  • 2,309
  • 7
  • 27
  • I think that constraints bellow are not necessary

    \begin{align} x_1 - x_2 & \le My \tag0 \ x_2 - x_1 & \le M(1-y) \tag1 \end{align}

    Check eq(1) is (-1)eq(3)+eq(4) and eq(0) is (-1)eq(2)+eq(5). Thus eq(0) and eq(1) are redundant.

    \begin{align} X & \ge x_1 \tag2 \ X & \ge x_2 \tag3 \ X & \le x_1 + M(1-y) \tag4 \ X & \le x_2 + My \tag5. \end{align}

     – Alexandre Frias Oct 10 '19 at 16:44