How to formulate this NLP problem correctly?

Question

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?

Answer 1

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.$$

Answer 2

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')
beta = model.addVar(ub=1-ep,name='beta')
z = model.addVars(item,name='z',ub=1)
b1 = model.addVar(name='b1',ub=1-e,lb=e)
b2 = model.addVar(name='b2',ub=1-e,lb=e)
a = model.addVars(item,[1,2,3],vtype='b',name='a')
x = model.addVars([1,2,3],ub=0.999,name='x')
k = model.addVars(item,[1,2],vtype='b',name='k')
#x = [1,2,3]# x3,x2,x1

#Constraints
#Dz = betaD
C1 = model.addConstr(z.prod(D) == beta*c[n-1],'C1')

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')

C9_1 = model.addConstr(x[3] <= x[2],'C9_1')
C9_2 = model.addConstr(x[2] <= x[1],'C9_2')

C10 = model.addConstrs((z[i] == a[i,1]*x[1]+a[i,2]*x[2]+a[i,3]*x[3] for i in item),'C9')

#Objective
g = quicksum(D[i]*p[i] for i in item) + quicksum(z[i] for i in item)
model.update()
model.setObjective(g,GRB.MINIMIZE)
model.optimize()