0
$\begingroup$

I am trying to do (global) integer constrained optimization using NMinimize. I have some polynomial consisting of many variables $x_{1,1}...x_{5,8}$ and a couple of constraints $A, B, ..., F$. I am having problems with a particular constraint. Unfortunately I am not able to create a minimal working example, as it seems that the problem is related to the complexity of the calculation.

Let's say that

A = 
-800.  + x[1, 1] + x[2, 1] + x[3, 1] + x[4, 1] + x[5, 1] >= 0 && 
-500.  + x[1, 2] + x[2, 2] + x[3, 2] + x[4, 2] + x[5, 2] >= 0 && 
-2000. + x[1, 3] + x[2, 3] + x[3, 3] + x[4, 3] + x[5, 3] >= 0 && 
-5000. + x[1, 4] + x[2, 4] + x[3, 4] + x[4, 4] + x[5, 4] >= 0 && 
-1000. + x[1, 5] + x[2, 5] + x[3, 5] + x[4, 5] + x[5, 5] >= 0 && 
-6000. + x[1, 6] + x[2, 6] + x[3, 6] + x[4, 6] + x[5, 6] >= 0 && 
-1000. + x[1, 7] + x[2, 7] + x[3, 7] + x[4, 7] + x[5, 7] >= 0 && 
-4000. + x[1, 8] + x[2, 8] + x[3, 8] + x[4, 8] + x[5, 8] >= 0

Then, Mathematica successfully solves the problem

NMinimize[{Func, A && B && C && D && E && F}, Flatten@X];

Now, if I make the one constraint A more complex by allowing also 0 for each row, I am getting

NMinimize::bcons: The following constraints are not valid: ... Constraints should be equalities, inequalities, or domain specifications involving the variables.

A then reads:

A = 
(x[1, 1] + x[2, 1] + x[3, 1] + x[4, 1] + x[5, 1] >= 800. || 
 x[1, 1] + x[2, 1] + x[3, 1] + x[4, 1] + x[5, 1] == 0) && 
(x[1, 2] + x[2, 2] + x[3, 2] + x[4, 2] + x[5, 2] >= 500. || 
 x[1, 2] + x[2, 2] + x[3, 2] + x[4, 2] + x[5, 2] == 0) && 
(x[1, 3] + x[2, 3] + x[3, 3] + x[4, 3] + x[5, 3] >= 2000. ||
 x[1, 3] + x[2, 3] + x[3, 3] + x[4, 3] + x[5, 3] == 0) && 
(x[1, 4] + x[2, 4] + x[3, 4] + x[4, 4] + x[5, 4] >= 5000. ||
 x[1, 4] + x[2, 4] + x[3, 4] + x[4, 4] + x[5, 4] == 0) && 
(x[1, 5] + x[2, 5] + x[3, 5] + x[4, 5] + x[5, 5] >= 1000. ||
 x[1, 5] + x[2, 5] + x[3, 5] + x[4, 5] + x[5, 5] == 0) && 
(x[1, 6] + x[2, 6] + x[3, 6] + x[4, 6] + x[5, 6] >= 6000. ||
 x[1, 6] + x[2, 6] + x[3, 6] + x[4, 6] + x[5, 6] == 0) && 
(x[1, 7] + x[2, 7] + x[3, 7] + x[4, 7] + x[5, 7] >= 1000. ||
 x[1, 7] + x[2, 7] + x[3, 7] + x[4, 7] + x[5, 7] == 0) && 
(x[1, 8] + x[2, 8] + x[3, 8] + x[4, 8] + x[5, 8] >= 4000. ||
 x[1, 8] + x[2, 8] + x[3, 8] + x[4, 8] + x[5, 8] == 0)

I checked that it works with the condition A alone, i.e., without B...F, so it's not syntax or anything. Also, this second version of A would also allow solutions of the first version. What causes my error here?


Edit: I tried to remove stuff from the notebook step-by-step while keeping the error. I believe the code below is a minimal working example. I hope, the error's origin really is the same as in my original problem.

X = Array[Subscript[x, ##] &, {3, 3}];

s = {{0.3`,0.3`,1.2`},{1.2`,1.2`,0.3`},{1.4`,1.4`,1.4`}};
b = {10000.`,5000.`,10000.`};
m = {800.`,500.`,2000.`};

MinOr[xx_,mm_] = xx >= mm || xx == 0;

C1 = AllTrue[MapThread[MinOr,{Total[X,1],m}], # &];
C2 = AllTrue[Total[Transpose[X],1]-b, # == 0 &];
C3 = AllTrue[Flatten@X, # >= 0 &];
C4 = AllTrue[Flatten@X,Element[#, Integers] &];

C12 = AllTrue[Total[X, 1] - m, # >= 0 &];

NMinimize[{Total[Flatten[X*s]], C1 && C2 && C3 && C4},Flatten@X]

Replacing C1 with C12 Mathematica is able to solve it, but not with C1.

$\endgroup$

closed as off-topic by happy fish, m_goldberg, MarcoB, Feyre, Young Jun 1 '17 at 15:37

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question cannot be answered without additional information. Questions on problems in code must describe the specific problem and include valid code to reproduce it. Any data used for programming examples should be embedded in the question or code to generate the (fake) data must be included." – happy fish, m_goldberg, MarcoB, Feyre, Young
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ can you post the complete code to reproduce this problem? $\endgroup$ – happy fish May 14 '17 at 9:36
  • 1
    $\begingroup$ Please do not use MathJax for Mathematica code. Use markdown. Click on the question-mark icon at the right end of the editor toolbar to get editing help. $\endgroup$ – m_goldberg May 14 '17 at 11:45
  • $\begingroup$ E is a protected symbol. Try N[E] and see what you get or look it up in the docs. Avoid capital single-letter variables. $\endgroup$ – Michael E2 May 14 '17 at 11:56
  • $\begingroup$ @m_goldberg: I will reformat the question tomorrow. However, all the Subscript[]s really make it less readable. @happyfish: I will try again to find a working, self-contained example. Right now, it is a huge .m file, that reads parameters from external files and such. @MichaelE2: The names I chose in this question are arbitrary, I just wanted to have as short code as possible. I am sure that I don't use any reserved names. $\endgroup$ – janoliver May 14 '17 at 17:30
  • $\begingroup$ I have now reformatted the question and added a working example. $\endgroup$ – janoliver May 15 '17 at 7:20
0
+100
$\begingroup$

Mathematica seems to choke on the fact the some of the parts of the logical expansion C1&&C2&&C3&&C4 are pathological. In particular, when you define

cons = LogicalExpand[C1 && C2 && C3 && C4]

then

NMinimize[{Total[Flatten[X*s]], cons[[1]]},Flatten@X]

produces an error message. cons[[1]] is case that all MinOr options are set to zero. This case is clearly pathological since the combination with C3 means that all x must vanish. (Which may be hard for Mathematica to figure out without at total Reduce of the constraints.)

Mathematica's problem in this case can be circumvented by introducing a new constraint

C0 = AllTrue[Flatten[X], (# == 0 &)]

and using it explicitly resolve the pathological constraint:

NMinimize[
 {Total[Flatten[X*s]], C0||LogicalExpand[C1 && C2 && C3 && C4][[2 ;; 8]]},
 Flatten@X
]

It thus seems that the error is caused by a pathology in your constraints. Of course it may be that the pathology is inherit to your MWE. In that case proceeding by applying LogicalExpand to your complete constraints and trying to NMinimize with each toplevel Or statement may be useful to pin down the problem.

Update If the problems are indeed caused by incompatible linear equations in your real world problem than it might help to apply the following to you constraints cons:

LogicalExpand[cons] /. A : And[_Equal, (_Equal) ..] :> Reduce[A]

This will try to reduce the subpart of your constraints consisting of equalities, eliminating those branches of the expanded constraints with incompatible equalities. This works for your MWE at least.

$\endgroup$
  • $\begingroup$ Hi mmeent, I think it really might have to do with expansion of conditions and then invalid conditions. My actual problem doesn't allow the all-zero solution. In fact, LogicalExpand gives a total of 256 possible logical combinations, of which many are invalid. Is there any way to tell NMinimize to just ignore these paths instead of finding out the valid ones and using only these? $\endgroup$ – janoliver May 16 '17 at 12:52
  • $\begingroup$ One approach would be to runNMinimize with each of the 256 Or combinations (discarding those results with fatal errors), and then taking the smallest result. $\endgroup$ – mmeent May 16 '17 at 20:20
  • $\begingroup$ That's what I was doing yesterday. Only about 5 gave me reasonable results, but luckily the best result was not the one where none of the Or conditions was zero, so I did make progress. Thank you again! I'll reward the bounty when I can. $\endgroup$ – janoliver May 17 '17 at 6:35

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