1
$\begingroup$

In this minimization problem we have $N$ items, $j= 1, 2, \dots, N$ and a decision variable $x_j$ which are continuous values. For every item, we have a nonlinear objective function $f$ in function of the decision variables $x_j$ that we want to minimize. We also have a variable $d_j$ that is different for every item and a variable $a_j$ that contains values from the set $\lbrace 0, 1, 2\rbrace$. Look at this $a$-variable as a classification that puts all items in one of three classes. I want to formulate the problem where we minimize $\sum_{j=1}^Nf(x_{j})$ but $x_j$ must be fixed for each class, so there are at most $3$ different values for $x_j$. Apart from that, we have the constraints $0.00 \le x_j < 1.00$ and $$\frac{\sum_{j=1}^N d_jx_{j}}{\sum_{j=1}^N d_j} = \beta,$$ where $0.00 \le \beta < 1.00$.

To make it a bit more clear, you can imagine the following table as an example of a valid (but not necessarily optimal) solution:

item    a    x     d     f(x)

1       0   0.98  198    212.5 
2       1   0.95  50     1245.2  
3       0   0.98  110    100.2     
4       2   0.92  20     120.8
5       1   0.95  80     521.2
6       1   0.95  36     8232.1
7       0   0.98  109    3245.7
8       2   0.92  15     58.2
9       0   0.98  140    5123.2
10      2   0.92  10     4128

In this valid solution, $\beta = 0.97$ and the result of the objective function is $22987.1$.

How can I formulate this NLP problem by enforcing the constraints mentioned?

$\endgroup$
9
  • 1
    $\begingroup$ As written, your ratio constraint forces all $x_i$ to be equal to $\beta$. Are you maybe missing a $\sum_i$ somewhere? $\endgroup$
    – RobPratt
    Feb 7, 2023 at 16:38
  • $\begingroup$ The constraint containing $\beta$ has a subscript $i$ that is neither summed over nor qualified. Should we assume that the constraint is enforced for each $i?$ $\endgroup$
    – prubin
    Feb 7, 2023 at 16:39
  • $\begingroup$ @RobPratt does it make sense to index my x variable on i and j ? Or do I just need to index on j and constraint it to be the same for the same values of a ? $\endgroup$ Feb 7, 2023 at 17:56
  • $\begingroup$ Still trying to understand. What is the explicit formula for $f$? $\endgroup$
    – RobPratt
    Feb 8, 2023 at 2:38
  • 1
    $\begingroup$ In constraint programming, an ELEMENT constraint can model such relationships where a decision variable's index can itself be a decision variable. $\endgroup$
    – RobPratt
    Feb 8, 2023 at 17:53

1 Answer 1

4
$\begingroup$

Given, $a_j\in\{0,1,2\}$, $d_j$, and $\beta$, your problem is to find $x_0,x_1,x_2\in [0,1]$ to minimize $\sum_{j=1}^N f(x_{a_j})$ subject to $$\frac{\sum_{j=1}^N d_j x_{a_j}}{\sum_{j=1}^N d_j} = \beta.$$


For example, here's what it would look like in SAS, where I have used $f(x)=(x-1/2)^4$:

data indata;
   input item a d;
   datalines;
 1 0 198
 2 1  50
 3 0 110
 4 2  20
 5 1  80
 6 1  36
 7 0 109
 8 2  15
 9 0 140
10 2  10
;

proc optmodel;
   set ITEMS;
   num a {ITEMS};
   num d {ITEMS};
   num beta = 0.97;
   set LABELS = setof {j in ITEMS} a[j];

   read data indata into ITEMS=[item] a d;

   var X {LABELS} >= 0 <= 1;
   min Z = sum {j in ITEMS} (X[a[j]] - 1/2)^4;
   con Ratio:
      (sum {j in ITEMS} d[j] * X[a[j]]) / (sum {j in ITEMS} d[j]) = beta;

   solve;
   print a d {j in ITEMS} X[a[j]];
quit;
$\endgroup$
1
  • $\begingroup$ thanks for the additional explanation on the implementation. Managed to get it working in Pyomo as well. Thanks again!! Accepted and upvoted. $\endgroup$ Feb 8, 2023 at 14:42

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.