1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – prubin
    Dec 4, 2022 at 20:39
  • $\begingroup$ @prubin did some edits based on your comment. $\endgroup$ Dec 4, 2022 at 20:48
  • $\begingroup$ 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? $\endgroup$ Dec 5, 2022 at 0:23
  • $\begingroup$ @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. $\endgroup$ Dec 5, 2022 at 6:07
  • $\begingroup$ Then you need to think carefully about what, if any, should be the constraint at this "boundary condition". $\endgroup$ Dec 5, 2022 at 8:05

2 Answers 2

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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)}$ ? $\endgroup$ Dec 5, 2022 at 8:38
  • $\begingroup$ I edited my answer to add a constraint ensuring all three classes are used. $\endgroup$
    – prubin
    Dec 5, 2022 at 17:03
  • $\begingroup$ 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. $\endgroup$ Dec 5, 2022 at 19:15
  • $\begingroup$ 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. $\endgroup$
    – prubin
    Dec 5, 2022 at 20:43
-2
$\begingroup$

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()
$\endgroup$
1
  • 1
    $\begingroup$ 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}$. $\endgroup$ Dec 4, 2022 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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