CODEWITHSUNDEEP
cplex
MINHEE KIM
MINHEE KIM

Reputation: 1

CPlex infeasible solutions because of "limit number" constraint

I am doing a CPlex experiment, and the "limit number" constraint makes the problem infeasible...

The work is successfully done without the limit constraint. I want to make a number limit of dealers which are connecting to the hub dc. I cannot figure it out for days.

My code:

> 
execute PARAMS {
    cplex.tilim = 43200;
//  cplex.tilim = 10;
 }

// parameters
int nDealer = ...;
int nSite = ...;
range dealer = 1..nDealer; // destinations
range site = 1..nSite; // distribution centers (candidate sites for hub and depot)

int numHub = ...;
int numDepot = ...;
int limit = ...;
float flow[dealer] = ...;
float capacity[site] = ...;
float xDealer[dealer] = ...;
float yDealer[dealer] = ...;
float xSite[site] = ...;
float ySite[site] = ...;
float dist[dealer][site];
float distSite[site][site];
float M;

dvar boolean a[dealer][site]; // alpha_ij = 1 if dest i uses DC j
dvar boolean b[site]; // beta_j = 1 if DC (hub) j is established
dvar boolean c[site]; // gamma_k = 1 if DC (depot) k is established
dvar boolean w[site][site]; // w_jk = 1 if hub j is connected to depot k.
dvar float volume[site]; // total flow volume assigned to DC j
dvar boolean z[dealer][site];

execute DISTANCE { // Euclidean Distance
    for (var i in dealer) {
        for (var j in site) {
            dist[i][j] = Opl.sqrt(Opl.pow(xDealer[i] - xSite[j], 2) + Opl.pow(yDealer[i] - ySite[j], 2));       
        }   
    }
    for (var j in site) {
        for (var k in site) {
            distSite[j][k] = Opl.sqrt(Opl.pow(xSite[j] - xSite[k], 2) + Opl.pow(ySite[j] - ySite[k], 2));   
        }   
    }
    M = 0;
    for (var i in dealer) {
        M += flow[i];
    }
}

// models
minimize sum(i in dealer) flow[i]
    * (sum(j in site) (dist[i][j] * a[i][j] + sum(k in site) distSite[k][j] * w[k][j]));
/* wrong Obj Func
minimize sum(i in dest, j in DC) (flow[i] * dist[i][j] * a[i][j]
        + (sum(k in DC : j != k) (flow[i] * distDC[j][k] * w[j][k])) ); // sum(f_i * sum(metro + regional))
*/

subject to {

    sum(j in site) (b[j]) == numHub;
    sum(k in site) (c[k]) == numDepot;

    forall(i in dealer) {
        sum(j in site) (a[i][j]) == 1;

        forall(j in site) {
            a[i][j] <= b[j] + c[j];     
        }
    }

    // w[j][k] <= b[j] * c[k]
    // Hub j can be connected to a single depot.
    forall(j in site) {
        b[j] + c[j] <= 1;

        // capacity restriction
        // volume = metro + regional
        volume[j] == sum(i in dealer) flow[i]
                    * (a[i][j] + (sum(k in site : k != j) a[i][k] * w[j][k]));
        volume[j] <= capacity[j] + M * (1 - b[j]); // only Hub concerned with its capacity

        forall(k in site : j != k) {
            2 * w[j][k] <= b[j] + c[k];
        }
    }

    // at least 1 hub must be connected to depot
    forall(k in site) {
        sum(j in site : j != k) (w[j][k]) == c[k];
    }


    forall (j in site){
        forall (i in dealer){
            ((a[i][j]+b[j])/2) <= z[i][j];
        }   

        sum(i in dealer) (z[i][j]) <= limit;
    }
}

Upvotes: 0

Views: 139

Answers (2)

Alex Fleischer
Alex Fleischer

Reputation: 10059

In the documentation IDE and OPL > CPLEX Studio IDE > IDE Tutorials you could have a look at the section "Relaxing infeasible models".

Plus to get help you could attach here the .dat file.

Upvotes: 1

TimChippingtonDerrick
TimChippingtonDerrick

Reputation: 2072

You have given us no information about the size of your problem, or the limit you are trying to impose. You may just be trying to impose too small a limit - we can't tell.

Two things to try:

First, if you leave out your limit constraints, what values do you get for the z[i][j] variables? Do those values look reasonable and sensible? If not, maybe you have some mistake in the formulation or the input data.

Secondly, if you include the limit constraints with large values for the limit (e.g. bigger than the values of z[i][j] in the unconstrained case) then you should still get the same solutions. Try reducing the value of the limit and re-solving. You should find a value for the limit where the problem becomes infeasible. Explore what happens around that critical limit value and see what happens to the rest of the solution values.

Upvotes: 1

Related Questions