How to formulate this NLP problem correctly?

Current status on the problem (what I've done)

I'm working on a NLP problem and I got a formulation of the problem, together with the necessary constraints, but I think it needs some adjustments to ensure feasibility and efficiency.

I was using the NLP-solver 'Ipopt' but switched to 'SCIP' and 'Bonmin' because of the binary variables I'm using. SCIP seems to have a lot of trouble with finding a solution as it keeps on running. I can limit the time and then stop it: it gives me a more or less optimal solution but the result shows that my constraints are not enforcing what I want. The Bonmin-solver gives me an error ('solver didn't exit normally'), but on other problems I have, Bonmin works just fine. This makes me think that my constraints are overcomplicated or not stated correctly. Therefore this question.

The problem formulation (what I want)

We have $$n$$ items ($$i=1, 2, \dots, n$$) and every item has (constant) parameters $$D_i =$$ demand and $$P_i =$$ price. We rank the items on the demand-parameter, so $$D_i \ge D_{i+1}$$. After this, we calculate a new parameter $$c_i$$ per item as the cumulative demand, so $$c_i= \sum_{j=1}^i D_i$$ for $$i = 1, 2, \dots, n$$. And we know that $$c_n = 1$$ and $$c_i \le c_{i+1}$$.

Now we want to assign a variable $$x$$ to ever item $$i$$ where we have the constraint that $$x_i \ge x_{i+1}$$ Then a nonlinear function $$g$$ is applied with arguments $$x_i, c_i, D_i$$ and $$P_i$$ and this function needs to be minimized with the constraint $$\sum_{i=1}^n D_ix_i = \beta \sum_{i=1}^n D_i$$, where $$0 \le \beta \lt 1$$. $$\beta$$ is a fixed parameter.

BUT.

We want to split up the items in $$3$$ classes based on the variable $$c_i$$ (the cumulative demand). We want to do this by assigning two boundaries $$b_1, b_2$$ that can split up the items with the simple logical expression: "if $$c_i \le b_1$$ then class 1, if $$b_1 \lt c_i \le b_2$$ then class 2, else class 3". Then every class gets one of the 3 $$x$$-variables : $$x_1, x_2, x_3$$. So we don't have a $$x_i$$-variable but only $$3$$ variables $$x_1, x_2$$ and $$x_3$$.

Now we always want 3 classes and $$x_1$$ is always assigned to class 1, $$x_2$$ to class 2 and $$x_3$$ to class 3.

Let

$$0 \le x_3 \le x_2 \le x_1 \le 1-\delta$$, where $$\delta$$ is small value like $$0.0001$$.

$$0 + \epsilon \le b_1 \le b_2 - \epsilon \le 1-\epsilon$$ where $$\epsilon$$ is high enough to make sure there are $$3$$ classes.

To formulate it mathematically, I'm using binary variables and create a new variable $$z_i$$.

Objective function

$$\min_{x_1, x_2, x_3, b_1, b_2} g(D_i, P_i, z_i)$$

Constraints

• $$\sum_{i=1}^n D_iz_i = \beta \sum_{i=1}^n D_i$$
• $$z_i = a_{i1}x_1 + a_{i2}x_2 +a_{i3}x_3$$
• $$b_1-c_i \le a_{i1}M$$
• $$c_i -b_2 \le a_{i3}M$$
• $$a_{i1}+a_{i2}+a_{i3} = 1$$
• $$c_i-b_1 \le Mk_{i1}$$
• $$b_2 - c_i \le Mk_{i2}$$
• $$k_{i1}+ k_{i2} - 1 \le a_{i2}$$
• $$b_1 \le b_2 - \epsilon$$
• $$x_3 \le x_2 \le x_1$$

, where $$M$$ is a large constant.

Variables

$$a_{i1}, a_{i2}, a_{i3} \in \{0, 1\}$$ and initialized to $$0$$,

$$0 \le x_1, x_2, x_3 \lt 1$$,

$$b_1, b_2 \in [0+\epsilon, 1-\epsilon]$$

$$k_{i1}, k_{i2} \in \{0, 1\}$$ and initialized to $$0$$,

$$z_i$$

Which constraints need to be adjusted or added to ensure everything I want? It doesn’t enforces $$z_i \ge z_{i+1}$$ which is something I want. But how can I write a constraint that enforces this? And how can I generally improve the mathematical formulation?

• Several things need clarification or correction here. First, you cannot have strict inequalities in a typical math programming model, so $x_i < 1$ would need to be either $x_i\le 1$ or $x_i \le 1-\epsilon$ for some $\epsilon > 0.$ Second, it is very unclear whether $D_i$ and $P_i$ are variables or parameters (constants). Third, is $\beta$ a parameter or a variable?
– prubin
Dec 4, 2022 at 20:39
• @prubin did some edits based on your comment. Dec 4, 2022 at 20:48
• I haven't carefully read the question, but is there a reason you can';t just include the constraints, $z_i \ge z_{i+1}$ if that's what you want? Dec 5, 2022 at 0:23
• @MarkL.Stone the thing is that in the implementation at item n, $z_{n+1}$ doesn’t exist and it will give an error because the index is out of range. Dec 5, 2022 at 6:07
• Then you need to think carefully about what, if any, should be the constraint at this "boundary condition". Dec 5, 2022 at 8:05

Notation alert: I will use $$g(i)\in \lbrace 1,2,3 \rbrace$$ to denote the group into which item $$i$$ is placed. So your $$D_i z_i$$ is my $$D_i x_{g(i)}.$$

Introduce new continuous variables $$w_i$$ to represent $$D_i x_{g(i)}.$$ We define them via the constraints $$D_i [x_j - (1-a_{i,j})] \le w_i \le D_i [x_j + (1-a_{i,j})] \quad \forall i=1,\dots,n; \forall j=1,2,3.$$ If item $$i$$ is in group $$j$$ ($$a_{i,j}=1$$), then $$w_i = D_i x_j.$$ Otherwise $$a_{i,j}=0$$ and the constraint that $$x_j < 1,$$ along with the presumption that $$D_i > 0,$$ means $$D_i [x_j - (1-a_{i,j})] < 0 \le D_i x_{g(i)}$$ and $$D_i [x_j + (1-a_{i,j})] > D_i \ge D_i x_{g(i)},$$ making the constraints nonbinding.

You already have the constraint $$a_{i,1}+a_{i,2}+a_{i,3}=1,$$ ensuring each item is assigned to a unique group. What is left is to enforce monotonicity with respect to cumulative demand. We can do that with the constraint $$a_{i,1} + 2a_{i,2} +3 a_{i,3} \le a_{i+1,1} + 2a_{i+1,2} +3 a_{i+1,3}\quad \forall i=1,\dots,n-1.$$ That simply says that no item is assigned to a higher index group than the next item.

Assuming the $$b$$ and $$k$$ variables were concocted only to achieve the monotonic group assignments, you can presumably drop them and $$M.$$

Addendum: To ensure that all three classes are used, we can add the constraints $$\sum_i a_{i,j} \ge 1 \quad j=1,2,3.$$

• does this also ensures that there are always 3 classes? The variables $b$ are used for that in my formulation. Also, is there a specific reason you introduce variable $w_i$ instead of just using $D_ix_{g(i)}$ ? Dec 5, 2022 at 8:38
• I edited my answer to add a constraint ensuring all three classes are used.
– prubin
Dec 5, 2022 at 17:03
• accepted! Two small questions: Nice trick to define $z_i$. That's equivalent to my $z_i = ...$ constraint right? Did you do this to make them non-binding? You say: monotonic group assignments: does this mean that my constraints with the $b$ and $k$ variables is equivalent to enforcing monotonicity wrt cumulative demand? Looks like that. Dec 5, 2022 at 19:15
• Did you mean nice trick to define $w_i$? My $w_i$ is basically your $D_i z_i$ (I think). If I'm interpreting your $b$ and $k$ constraints correctly, their purpose is to ensure that group 1 items have lower cumulative demand than group 2 items and group 2 lower cumulative demand than group 3. That's what I mean by monotonic group assignments. Since, as you noted in the question, $c_i \le c_{i+1},$ that translates to nondecreasing group numbers (the first bunch of items in group 1, the next bunch in group 2 and the last bunch in group 3), which is what my "monotonicity" constraints enforce.
– prubin
Dec 5, 2022 at 20:43

Using gurobi and python..Used an arbitrary objective g involving D,p & z. It gives a feasible model. Let me know if I should try with diff parameters.

n=8
item=[*range(n)]
p = {0:3,1:2,2:4,3:5.5,4:2.5,5:6,6:4,7:3.2}
D = {0:10,1:12,2:14,3:15.5,4:12.5,5:16,6:14,7:13.2}
c = {i:D[i]+c[i-1] for i in item[1:]}
c.update({0:D[0]})
#print(c)
e,ep,M = 1e-1,1e-3,200

model = Model('Test')
#x = [1,2,3]# x3,x2,x1

#Constraints

C2 = model.addConstrs((b1 - c[i] <= a[i,1]*M for i in item),'C2')
C3 = model.addConstrs((c[i] - b2 <= a[i,3]*M for i in item),'C3')

C4 = model.addConstrs((c[i] - b1 <= k[i,1]*M for i in item),'C4')
C5 = model.addConstrs((b2 - c[i] <= k[i,2]*M for i in item),'C5')
C6 = model.addConstrs((k[i,1] + k[i,2] - 1 <= a[i,2] for i in item),'C6')

C7 = model.addConstrs((a.sum(i,'*') == 1 for i in item),'C7')

C8 = model.addConstr(b1 <= b2 - e,'C8')


• No this model doesn’t ensures a feasible solution of what I’m trying to do. It doesn’t forces $z_i \ge z_{i+1}$. Dec 4, 2022 at 22:35