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

Question

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.

Answer 1

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".