linear-programmingmathprog

How to take the maximum over all columns of the sum over all rows in MathProg

I am trying to solve an optimisation problem where the variables I am trying to optimise are in a matrix (salesperson X shop, the variable is 1 if that salesperson is assigned to that shop). Each shop has a profit.

This is how I define it:

set SalesPeople;
set Shops;

param profit{Shops} >=0;

var a{i in SalesPeople, j in Shops}, binary;

I am now trying to add a constraint that says that the maximum over all salesperson of the sum over all shops of the profit is greater than a certain number. This is how I formulated it but this does not seem to work.

subject to cond3: max{i in SalesPeople} sum{j in Shops} profit[j]*a[i,j] >= 10;

Can this be done? If so, what is the right syntax?

I have only just started learning MathProg so it is all a bit confusing.

Solution

  • The constraint

     max{i in SalesPeople} sum{j in Shops} profit[j]*a[i,j] >= 10;

    is not linear, so a MIP solver cannot accept this. Unfortunately, this particular form requires extra binary variables. If the constraint was

     max{i in SalesPeople} sum{j in Shops} profit[j]*a[i,j] <= 10;

    we could write:

     cond3{i in SalesPeople}: sum{j in Shops} profit[j]*a[i,j] <= 10;

    For your case we need to do something like:

     var d{i in SalesPeople}, binary; 
 cond3{i in SalesPeople}: sum{j in Shops} profit[j]*a[i,j] >= 10*d[i];
 sumd: sum{i in SalesPeople} d[i] >= 1;

    The last constraint can also be written as:

     sumd: sum{i in SalesPeople} d[i] = 1;

    This construct essentially says: "at least one i should have: sum{j in Shops} profit[j]*a[i,j] >= 10".