0
$\begingroup$

There is a problem I want to solve. The function is:

\begin{align} &\underset{a,b,\textbf{vec}}{\text{minimize} \text{ }\text{ }\text{ }\text{ } } f=\sum_{i=1}^{b}(\textbf{vec}_i)^{a}\\ &\text{subject to } \text{ }\text{ } f \geq F, \text{ } \sum_{i=1}^b \textbf{vec}_i = D, \text{ } a\leq N, b \leq D, \{\textbf{vec}_1,\cdots, \textbf{vec}_b\}\leq D \end{align}

Basically, all the variables are non-negative values. I have two questions:

  1. Because the size of $\textbf{vec}$ is dependent on another parameters $b$, then the number of variables in the objective function are not fixed beforehand. Does it still a MINLP problem?

  2. How to solve it? is there some open-source software can deal with it easily?

$\endgroup$
5
  • 1
    $\begingroup$ Are $a$ and the components of $vec$ nonnegative integers? $\endgroup$
    – Carl Woll
    Jul 28, 2017 at 22:03
  • $\begingroup$ yes, all the variables are nonnegative integers. $\endgroup$
    – WYC
    Jul 28, 2017 at 22:23
  • $\begingroup$ What are ranges of $N$, $D$, and $F$ you are interested in? $\endgroup$
    – Carl Woll
    Jul 28, 2017 at 22:31
  • $\begingroup$ Well, N<=100, D<=200, F<=2000. I was wondering whether it can be solved by MINLP, and how much time it will take to solve this problem. $\endgroup$
    – WYC
    Jul 28, 2017 at 23:10
  • $\begingroup$ Actually, $a$ and $N$ in my problem do not have much impact, but $\textbf{vec}$ and $b$ have more impact. $\endgroup$
    – WYC
    Jul 28, 2017 at 23:19

1 Answer 1

1
$\begingroup$

I'm no expert on NMinimize, but the following might be a useful starting point:

len = 200;
NMinimize[
    {
    Sum[x[i]^3, {i, len}],
    Sum[x[i]^3, {i, len}] >= 2000 &&
    Sum[x[i], {i, len}] == len &&
    And @@ Table[x[i] >= 0, {i, len}]
    },
    Table[x[i],{i,len}],
    Integers
] //AbsoluteTiming

NMinimize::cvmit: Failed to converge to the requested accuracy or precision within 100 iterations.

{30.3566, {2000., {x[1] -> 11, x[2] -> 3, x[3] -> 0, x[4] -> 1, x[5] -> 1, x[6] -> 3, x[7] -> 0, x[8] -> 1, x[9] -> 3, x[10] -> 0, x[11] -> 0, x[12] -> 0, x[13] -> 2, x[14] -> 0, x[15] -> 2, x[16] -> 1, x[17] -> 1, x[18] -> 1, x[19] -> 1, x[20] -> 0, x[21] -> 1, x[22] -> 1, x[23] -> 2, x[24] -> 1, x[25] -> 1, x[26] -> 2, x[27] -> 0, x[28] -> 1, x[29] -> 0, x[30] -> 0, x[31] -> 0, x[32] -> 1, x[33] -> 2, x[34] -> 1, x[35] -> 0, x[36] -> 2, x[37] -> 0, x[38] -> 0, x[39] -> 0, x[40] -> 2, x[41] -> 0, x[42] -> 1, x[43] -> 0, x[44] -> 1, x[45] -> 2, x[46] -> 0, x[47] -> 1, x[48] -> 1, x[49] -> 1, x[50] -> 1, x[51] -> 2, x[52] -> 1, x[53] -> 1, x[54] -> 2, x[55] -> 0, x[56] -> 0, x[57] -> 1, x[58] -> 2, x[59] -> 1, x[60] -> 1, x[61] -> 1, x[62] -> 0, x[63] -> 2, x[64] -> 1, x[65] -> 0, x[66] -> 1, x[67] -> 0, x[68] -> 3, x[69] -> 0, x[70] -> 1, x[71] -> 1, x[72] -> 2, x[73] -> 1, x[74] -> 1, x[75] -> 2, x[76] -> 1, x[77] -> 1, x[78] -> 2, x[79] -> 0, x[80] -> 1, x[81] -> 2, x[82] -> 0, x[83] -> 0, x[84] -> 0, x[85] -> 0, x[86] -> 1, x[87] -> 2, x[88] -> 0, x[89] -> 2, x[90] -> 0, x[91] -> 0, x[92] -> 0, x[93] -> 1, x[94] -> 0, x[95] -> 0, x[96] -> 2, x[97] -> 0, x[98] -> 1, x[99] -> 0, x[100] -> 1, x[101] -> 2, x[102] -> 3, x[103] -> 0, x[104] -> 1, x[105] -> 2, x[106] -> 0, x[107] -> 2, x[108] -> 1, x[109] -> 1, x[110] -> 1, x[111] -> 0, x[112] -> 1, x[113] -> 2, x[114] -> 2, x[115] -> 0, x[116] -> 1, x[117] -> 0, x[118] -> 3, x[119] -> 1, x[120] -> 2, x[121] -> 1, x[122] -> 0, x[123] -> 1, x[124] -> 1, x[125] -> 0, x[126] -> 0, x[127] -> 1, x[128] -> 1, x[129] -> 1, x[130] -> 1, x[131] -> 1, x[132] -> 1, x[133] -> 0, x[134] -> 2, x[135] -> 2, x[136] -> 0, x[137] -> 0, x[138] -> 1, x[139] -> 2, x[140] -> 3, x[141] -> 1, x[142] -> 2, x[143] -> 1, x[144] -> 0, x[145] -> 2, x[146] -> 2, x[147] -> 0, x[148] -> 1, x[149] -> 2, x[150] -> 0, x[151] -> 0, x[152] -> 1, x[153] -> 1, x[154] -> 0, x[155] -> 1, x[156] -> 2, x[157] -> 0, x[158] -> 1, x[159] -> 1, x[160] -> 0, x[161] -> 2, x[162] -> 2, x[163] -> 0, x[164] -> 0, x[165] -> 2, x[166] -> 1, x[167] -> 1, x[168] -> 1, x[169] -> 1, x[170] -> 0, x[171] -> 1, x[172] -> 2, x[173] -> 0, x[174] -> 0, x[175] -> 2, x[176] -> 1, x[177] -> 1, x[178] -> 0, x[179] -> 1, x[180] -> 0, x[181] -> 1, x[182] -> 1, x[183] -> 1, x[184] -> 0, x[185] -> 1, x[186] -> 1, x[187] -> 1, x[188] -> 1, x[189] -> 2, x[190] -> 4, x[191] -> 0, x[192] -> 0, x[193] -> 2, x[194] -> 0, x[195] -> 0, x[196] -> 2, x[197] -> 0, x[198] -> 2, x[199] -> 1, x[200] -> 0}}}

$\endgroup$
1
  • $\begingroup$ Thanks a lot. So this problem can be solved by NMinimize? (forgive me I have no idea about this tool). By the way, can you timing how long it took to find a solution (for example, 100 iterations or more)? $\endgroup$
    – WYC
    Jul 29, 2017 at 7:51

Your Answer

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