Abort: Unable to create linear formulation for the `float_times(X_INTRODUCED_44_, X_INTRODUCED_45_, X_INTRODUCED_46_)` constraint

user_16647718 0
Viewed 111

I'm coding a MIP problem using Minzinc with Coin-bc solver. But, It's raise a error like the title. It's due to eta_cpu & cpu_used both are variables, When I remove one of them from the Objective Function income, it become work. System point out set QuadrFloat=ture, but after I did it, Another question comes like this: Backend: [int/float]_times not supported.

MiniZinc version is 2.5.5

Code in here:

include "Untitled1.dzn";
% include "redefinitions.mzn";

QuadrFloat = true;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ENVIRONMENT

int: numHosts;
set of int: hosts = 1..numHosts;

array[hosts] of int: cpu_resource;
array[hosts] of int: memory_resource;
array[hosts] of int: storage_resource;
array[hosts] of int: bandwidth_resource;

int: numVnfs;
set of int: vnf = 1..numVnfs;
array[vnf] of int: vnf_properties_bw;
array[vnf] of int: vnf_properties_cpu;
array[vnf] of int: vnf_properties_mem;
array[vnf] of int: vnf_properties_sto;

int: sliceLen;
set of int: sSlice = 1..sliceLen;
array[sSlice] of int: slice;


float: C;
float: G_c;
float: G_m;
float: G_s;

float: W_min;
float: W_max;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% DECISION VARIABLES AND CONSTRAINTS
var float: income;
array[sSlice] of var hosts: placement;
array[hosts] of var int: cpu_used;
array[hosts] of var int: memory_used;
array[hosts] of var int: storage_used;
array[hosts] of var int: bandwidth_used;
array[hosts] of var 0..1: u;

array[hosts] of var float: eta_cpu;
array[hosts] of var float: eta_mem;
array[hosts] of var float: eta_sto;
array[hosts] of var float: eta_bw;


% RESOUECES UTILIZATION
constraint forall(host in hosts)
(
    cpu_used[host] = sum(s in sSlice where placement[s] = host) (vnf_properties_cpu[slice[s]])
);

constraint forall(host in hosts)
(
    memory_used[host] = sum(s in sSlice where placement[s] = host) (vnf_properties_mem[slice[s]])
);

constraint forall(host in hosts)
(
    storage_used[host] = sum(s in sSlice where placement[s] = host) (vnf_properties_sto[slice[s]])
);

constraint forall(host in hosts)
(
    bandwidth_used[host] = sum(s in sSlice where placement[s] = host) (vnf_properties_bw[slice[s]])
);

% RESOURCE CONSTRAINTS
constraint forall(host in hosts)
(
    cpu_used[host] <= cpu_resource[host]
);

constraint forall(host in hosts)
(
    memory_used[host] <= memory_resource[host]
);

constraint forall(host in hosts)
(
    storage_used[host] <= storage_resource[host]
);

constraint forall(host in hosts)
(
    bandwidth_used[host] <= bandwidth_resource[host]
);

% RESOUECES UTILIZATION RATE
constraint forall(host in hosts)
(
  (
    eta_cpu[host] = 
    if cpu_used[host] > 0
      then cpu_used[host] / cpu_resource[host]
    else
        0
    endif
  )
);

constraint forall(host in hosts)
(
  (
    eta_mem[host] = 
    if memory_used[host] > 0
      then memory_used[host] / memory_resource[host]
    else
        0
    endif
  )
);

constraint forall(host in hosts)
(
  (
    eta_sto[host] = 
    if storage_used[host] > 0
      then storage_used[host] / storage_resource[host]
    else
        0
    endif
  )
);

constraint forall(host in hosts)
(
  (
    eta_bw[host] = 
    if bandwidth_used[host] > 0
      then bandwidth_used[host] / bandwidth_resource[host]
    else
        0
    endif
  )
);

% HOST STATE
constraint forall(host in hosts)
(
    (
       u[host] = 
       if cpu_used[host] > 0 
         then 1
       else 0
       endif
    )
);
          
% OBJECTIVE FUNCTION
income = sum(host in hosts) ((G_c * (1.0 - eta_cpu[host]) * cpu_used[host] + G_m * memory_used[host] + G_s * storage_used[host]) - (W_max - W_min) * eta_cpu[host] + u[host] * W_min) * C;

% income = sum(host in hosts) ((G_c  * cpu_used[host] + G_m * memory_used[host] + G_s * storage_used[host]) - (W_max - W_min) * eta_cpu[host] + u[host] * W_min) * C;

% income = sum(host in hosts) ((G_c * (1 - eta_cpu[host]) + G_m * memory_used[host] + G_s * storage_used[host]) - (W_max - W_min) * eta_cpu[host] + u[host] * W_min) * C;

% income = sum(host in hosts) ((G_c * (1 - eta_cpu[host]) * 10.0 + G_m * 10.0 + G_s * 10.0) - (W_max - W_min) * eta_cpu[host] + u[host] * W_min) * C;                                                                                                        

% solve satisfy;
solve maximize income;

output ["\nplacement: ", show(placement),
        "\ncpu_used: ", show(cpu_used),
        "\nmemory_used: ", show(memory_used),
        "\nstorage_used: ", show(storage_used),
        "\nbandwidth_used: ", show(bandwidth_used),
        "\neta_cpu: ", show(eta_cpu),
        "\neta_mem: ", show(eta_mem),
        "\neta_sto: ", show(eta_sto),
        "\neta_bw: ", show(eta_bw),
        "\nu: ", show(u),
        "\nincome: ",  show_float(0, 5, income),
%         "\n111: ", show_float(0, 5, int2float(2, cpu_used[1]))
       ];

What should I do to solve this problem. Help me. Please. ORZ.

solver minizinc
1 Answers

The issue here is with the type of solver. Coin-or Branch-and-Cut (CBC) is a Mixed Integer Programming solvers. One of the limitations of these types of solvers is that its problems can only contain linear (in-)equalities. So you can multiply decision variables by constants, and you can add these terms together, but you cannot multiply two variables. This is out of scope for the solving mechanism.

For integer multiplication, there is a solution. You can use a decomposition where you split the integers into many 0..1 integer variable each representing whether the original integer takes a certain value. These variables can then be used to reason about the value of the multiplication in multiple seperate constraints. This is especially efficient, but allows us to use integer multiplication (at least some of the time).

Floating point multiplication is a different beast. It requires explicit support from a solver. Problems that use these constraints are called quadratic and you will often see that MIP solver will specify whether they can solve quadratic problems. Among the MiniZinc solvers, CBC does not support quadratic constraints, but I believe the other MIP solvers (SCIP, Gurobi, and CPLEX) do.

user_13515970
Related