float_div

[H. A.]

Hello all,

I have the following:

users - locations - resources

Each user i can be assigned to specific locations, defined in C[i], e.g., C[i] = [2 , 4, 5]; means that user can be scheduled in locations 2, 4 and 5.

I am trying to schedule users on resources found in the different locations.

Each location contains M available resources.

I wish to get the optimal values of binary variables that determine if user 'i' is scheduled on resource 'm' at location 'j' or not. Hence I need to fill a 3D matrix taurum (matrix dimension: #ofUser \times #ofLocations \times #ofresources ).

I have some constraint where a users can be scheduled on at most one resource at a specific location, and if it is scheduled in any location, it should be scheduled on the remaining locations that are defined in the set C[i] for this user.

Also the information in C is restructured in E, where E[j] shows the users that can be assigned in location j.

I'm having two issues in my formulated problem:

1- The objective function contains sum_i of  (constants*log(f(x))), and the solvers on MiniZinc do not support log(float).

2- Even if I drop the log, still f(x) is a ratio where the decision variables are found in both numerator and denominator.

For 2, I have written the problem on MiniZinc and it looks like the solvers do not support dividing floats. The error says:

MiniZinc: internal error: Error: solver backend cannot handle constraint: float_div

I have tried tried using the solvers found in MiniZinc IDE but none is working. In the following is my code. Please advice.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Parameters

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int: Locations; 

int: UsersN;

int: M;

array[1..UsersN] of set of 1..Locations: C;

array[1..UsersN] of int: clusterSize;

array[1..Locations] of set of 1..UsersN: E;

array[1..Locations] of int: usersToServeN;

array[1..UsersN, 1..Locations, 1..M] of float: Usef;

array[1..UsersN] of float: InterfNoiseBasic;

array[1..UsersN, 1..Locations, 1..M] of float: InterfNoiseAdditional;

array[1..UsersN] of float: fairnessWeight;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Variables

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% array[1..UsersN, 1..Locations, 1..M] of var bool: taurum;

array[1..UsersN, 1..Locations, 1..M] of var 0..1: taurum;

var float: utility;

array[1..UsersN] of var float: denominator;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% Constraints

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

constraint forall(j in 1..Locations)(

forall(i in 1..UsersN)(

sum(m in 1..M)(

taurum[i,j,m]

) <= 1

)

);

constraint forall(j in 1..Locations)(

forall(m in 1..M)(

sum(i in E[j])(

taurum[i,j,m] % first usersToServeN[j] values in taurum is what we need

) <= 1

)

);

constraint forall(i in 1..UsersN)(

sum(j in C[i])(

sum(m in 1..M)(

taurum[i,j,m]

)) == 0

\/

sum(j in C[i])(

sum(m in 1..M)(

taurum[i,j,m]

)) == clusterSize[i]

);

constraint forall(i in 1..UsersN)(

denominator[i] == 

( InterfNoiseBasic[i] + 

sum(k in C[i])(

sum(m_prime in 1..M)(

(1 - taurum[i,k,m_prime]) * InterfNoiseAdditional[i,k,m_prime]

)))

);

constraint utility == sum(i in 1..UsersN)(

fairnessWeight[i] *

%ln(1 +

(

sum(j in C[i])(

sum(m in 1..M)(

taurum[i,j,m] * Usef[i,j,m] ) )
/ denominator[i]

)

%)

);

solve maximize utility;

[Krzysztof Kuchcinski]

JaCoP solver works with minizinc and both float_div and float_ln.

[Gleb Belov]

Some non-linear solvers, interfaceable via AMPL's NL format, can handle both log and division, see https://www.minizinc.org/doc-2.4.3/en/solvers.html#non-linear-solvers. However you can open more solvers to this if you formulate division via multiplication and approximate log by a piecewise-linear function, https://www.minizinc.org/doc-2.4.3/en/lib-globals.html. In particularly, Gurobi can handle non-integer multiplication if you compile the MZN develop branch from source and run minizinc with -DQuadrFloat=true. Actually Gurobi 9.0 can approximate log itself, but MZN has no interface to that yet.

[Mikael Zayenz Lagerkvist]

Hi,

Do you have a data-file for the model you posted, for test-running locally?

Cheers,

Mikael

On Sunday, April 26, 2020 at 1:17:59 AM UTC+2, H. A. wrote:

[H. A.]

Hello Mikael, Thank you for your reply. I have attached a toy data file with the Minizinc code (slightly modified).

[Mikael Zayenz Lagerkvist]

Hi,

Thanks, it is always easier to look at something that is runnable.

The standard solver in the MiniZinc IDE, Gecode, reports that a number
is out of limits. I was wondering about this, since I know that it
support float_div, which you stated was the reported error.

Unfortunately, the message is a bit short currently, but I could see
locally that it is the sum computing the utility the goes out of
bounds for Gecode. In general, for constraint programming solvers, it
is important to limit the domains of variables. I'm not sure what
changes would be reasonable for your model to keep reasonable limits
on all sums, but I hope this helps.

Cheers,
Mikael

> --
> You received this message because you are subscribed to the Google Groups "MiniZinc" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to minizinc+u...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/minizinc/853411e1-ac89-45fa-aaad-0b9d36f9a7d1%40googlegroups.com.



--
Mikael Zayenz Lagerkvist

[Krzysztof Kuchcinski]

Hi,

I have check the problem a little bit more and found out that it is a problem with floating-point representation and operations rounding. Both JaCoP and Gecode report unsatisfiability of the problem. For Gecode, one must change "var float: utility;" to "var -1e6..1e6: utility;", for example.

In JaCoP I have traced what constraint causes unsatisfiability and it is constraint 

X_INTRODUCED_11491_ - 2.028E-8 = 1.59E-11

where domain of X_INTRODUCED_11491_  is 2.028E-8..2.02959E-8.

This constraint fails because in "normal" arithmetic 2.02959E-8 -2.028E-8 = 1.59E-11 but in floating-point arithmetic it is 1.5899999999999504E-11 :( Strictly speaking 1.59E-11 != 1.5899999999999504E-11.

I changed in JaCoP domain computations and relaxed constants to encapsulating smallest intervals and JaCoP was able to generate solutions, even for utility variable defined with logarithm (used in the attached solution). I could not get optimal solution but a solution obtained with time-out of 15 minutes is attached to this mail.

/Kris

[H. A.]

Thank you all for your great and much appreciated help.

• Yes, it seems Gecode supports float_div. In my case, replacing (1) by (2) (below in appendix) allows Gecode to solve the problem when there is no log function. But it is very slow.
  

• As for JaCoP, I was able to run it through the command prompt through commands (3) . It seems to support the log function and the division of floats, but it seems to be super slow even for very small problem sizes. I have run it for some time and it is not giving any output.
  
• So, my current problem is that even for a small input, the problem still cannot be solved in reasonable time. I have done some small modifications for the code and I have posted two sample input files just in case anybody needs to check the problem. I think that the problem cannot be solved efficiently with my current utility. I was thinking about using product( f(x)^a) instead of  sum a*log(f(x)) . But I don't think its is possible to write such constraints in MiniZinc, right?
  

Anyway, thank you all for your replies.

Appendix:

(1) var float: utility;

(2) var 10..1e5: utility;

(3) minizinc -c CP_v3.mzn -d input_small.dzn

      java -cp jacop.jar org.jacop.fz.Fz2jacop CP_v3.fzn | minizinc --ozn-file CP_v3.ozn

[Krzysztof Kuchcinski]

Hi,

You do not use any search annotations that is not good for realistic problems. In the solution I have send you I used the following annotation, specific for JaCoP.

include "jacop.mzn";

solve :: restart_luby(1000) :: int_search(taurum, activity_max, indomain_min) maximize utility;

You can also try to run JaCoP with "free search", option -f. With this option JaCoP gets an optimal solution for input_small.dzn and "Total network utility = 15.41982536671624". For input_large.dzn both Gecode and JaCoP indicate unsatisfiability.

/Kris

[Krzysztof Kuchcinski]

In my previous mail I gave a wrong value for the optimal solution. The correct one is 

Total network utility = 15.94523856112685

/Kris

[H. A.]

Thank you for your reply,

So, I should add this line at the beginning of CP_v3.mzn:     include "jacop.mzn";

and I should replace in CP_v3.mzn:   solve maximize utility;   with        solve :: restart_luby(1000) :: int_search(taurum, activity_max, indomain_min) maximize utility;

I have tried this and the program keeps running without giving any output, and when I use the -f, i.e.,

java -cp jacop.jar org.jacop.fz.Fz2jacop -f CP_v3.fzn | minizinc --ozn-file CP_v3.ozn

It gives an exception (attached).

[Krzysztof Kuchcinski]

Sorry! I am using develop branch of JaCoP. Option -f does not defines free search in version 4.7. I defines print-out format. For more options try option -h. Sorry for confusion.

BTW, use option -a when you make search and you will be able to see intermediate results produced by JaCoP.

/Kris

[H. A.]

Thank you so much for your great help. I have tried it, and it is producing results for small to medium-size problems.

Best regards and good luck in your research.