Setting a Constraint on a Coefficient Factor

I am using the Mixed-integer linear programming (intlinprog function) as a minimization tool. Is there a way to floor the Coefficient Factor, f, in the formula to zero so it will only calculate results that keep the Coefficient factor greater than or equal to zero?

Answer 1

[Matt J]

Yes, remove all negative values from f, and the corresponding columns from the constraint matrices.

keep=(f>0);

f=f(keep);
A=A(:,keep);
Aeq=Aeq(:,keep);

lb=max(lb(keep) ,0);
ub=ub(keep);

[Derek De Vries]

Sorry - I'm struggling to understand how to apply so I thought I'd share an example.

I'm using this to basically determine the quantity of each row (x in Column E) that will result in the sum of each column falling within a constraint. The first row, Row 2, has Column E permanently set to 1 since that will not change and my goal is to find the appropriate quantity of values in Column E.

MATLAB Code:

Data = A1:D6 in the table above
NumRows = size(Data,1);
DataList = [(1:NumRows)',Data];
f = DataList(:,5);
A = DataList(:,2:4)';
A = cat(1,A,-A);
b = [3,3,3]; %These are the constraints.  The sum of a column can be anywhere from -3 to +3.
b = cat(2,b,b);
lb = [1; zeros(NumRows-1,1)];
ub = [1; 50 .* ones(NumRows-1,1)];
intcon = 1:NumRows;
[x, fval] = intlinprog(f, intcon, A, b, [], [], lb, ub, []);

To summarize (not sure if it's a problem with this small example I created), how can I make it so that the vector created in variable x (for Column E) won't result in a cost less than zero (Column D)?

Thanks!

[Matt J]

You mean you want f*x>=0 ? Just include it as one of your inequality constraints.

Incidentally, it doesn't make much sense to include E2 in your unknowns if you know in advance that it is always 1.

[Derek De Vries]

1. How would I include that as an inequality constraint? I'm guessing that's using Aeq and Beq somehow?
2. I need the "Scen" results for Row 2 so I thought then I'd have to include E2 as well for uniformity. Do you think there's a better way to handle that?

[Matt J]

You could just add another row to your A matrix. However, here is how I would re-organize everything, using the problem-based approach.

DataList = [(1:NumRows)',Data];

f = DataList(3:end,5).';
P = DataList(3:end,2:4).';
q = DataList(2,2:4).';

x=optimvar('x',[numel(f),1],'LowerBound',0,'UpperBound',50,'type','integer');

Con.upper=P*x+q<=3;
Con.lower=P*x+q>=-3;
Con.cost=f*x>=0;

prob=optimproblem('Objective',f*x,'Constraints',Con);

sol=solve(prob);

[Derek De Vries]

That's really helpful!

1. Can you show the inequality constraint in the context of the intlinprog code up above? I want to make sure I'm understanding that correctly.

2. For the problem-based approach, how does the function understand Con.cost as a name? And what if the constraints by column vary? Example [-3 5 -22].

[Matt J]

1. Can you show the inequality constraint in the context of the intlinprog code up above?

f = DataList(:,5);
A0 = DataList(:,2:4)';
b0 = [3;3;3];

A = [A0;-A0;-f.'];
b = [b0;+b0;0];

lb = [1; zeros(NumRows-1,1)];
ub = [1; 50 .* ones(NumRows-1,1)];
intcon = 1:NumRows;
[x, fval] = intlinprog(f, intcon, A, b, [], [], lb, ub, []);

2. For the problem-based approach, how does the function understand Con.cost as a name?

Con is just a struct variable. The solver doesn't use the field names in any way - I just named one of the fields "cost" for code clarity's sake.

And what if the constraints by column vary? Example [-3 5 -22].

Don't they already?

[Derek De Vries]

Sorry, to clarify - Is there a way to use the problem-based approach if b varies (right now it's just set to 3)? What if I wanted the constrants to be:

Column 1 -- (-3) <= SumProduct(Column1,x) <= 3

Column 2 -- (-5) <= SumProduct(Column2,x) <= 5

Column 3 -- (-22) <= SumProduct(Column3,x) <= 22

[Derek De Vries]

Also, I changed the data table to something simple that I knew would have a solution. I'm getting an answer with the original MILP approach:

Data = [-150 200 160 0; 0 -20 0 5; 15 0 0 3; 0 0 -8 7; -1 0 0 -1];
NumRows = size(Data,1);
DataList = [(1:NumRows)',Data];
f = DataList(:,5);
A0 = DataList(:,2:4)';
b0 = [3;3;3];
A = [A0;-A0;-f.'];
b = [b0;+b0;0];
lb = [1; zeros(NumRows-1,1)];
ub = [1; 50 .* ones(NumRows-1,1)];
intcon = 1:NumRows;
[x, fval] = intlinprog(f, intcon, A, b, [], [], lb, ub, []);

However, I'm unable to reach an answer using the problem-based approach:

Data = [-150 200 160 0; 0 -20 0 5; 15 0 0 3; 0 0 -8 7; -1 0 0 -1];
NumRows = size(Data,1);
DataList = [(1:NumRows)',Data];
f = DataList(2:end,5).';
P = DataList(2:end,2:4).';
q = DataList(1,2:4).';
x = optimvar('x',[numel(f),1],'LowerBound',0,'UpperBound',50,'type','integer');
Con.upper = P*x+q <= 3;
Con.lower = P*x+q >= 3;
Con.cost = f*x >= 0;
prob = optimproblem('Objective', f*x, 'Constraints', Con);
sol = solve(prob);

[Matt J]

Sorry, to clarify - Is there a way to use the problem-based approach if b varies (right now it's just set to 3)?

Yes, the RHS of the inequalities can be vectors or scalars.

However, I'm unable to reach an answer using the problem-based approach:

You're missing a minus sign in Con.lower. Below, I demonstrate that both approaches give the same solution:

Data = [-150 200 160 0; 0 -20 0 5; 15 0 0 3; 0 0 -8 7; -1 0 0 -1];
NumRows = size(Data,1);
DataList = [(1:NumRows)',Data];
f = DataList(:,5);
A0 = DataList(:,2:4)';
b0 = [3;3;3];
A = [A0;-A0;-f.'];
b = [b0;+b0;0];
lb = [1; zeros(NumRows-1,1)];
ub = [1; 50 .* ones(NumRows-1,1)];
intcon = 1:NumRows;
[x, fval] = intlinprog(f, intcon, A, b, [], [], lb, ub, []);

LP:                Optimal objective value is 181.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer
within tolerance, options.IntegerTolerance = 1e-05 (the default value).

x=round(x)

x = 5×1

1 10 13 20 48

Data = [-150 200 160 0; 0 -20 0 5; 15 0 0 3; 0 0 -8 7; -1 0 0 -1];
NumRows = size(Data,1);
DataList = [(1:NumRows)',Data];
f = DataList(2:end,5).';
P = DataList(2:end,2:4).';
q = DataList(1,2:4).';
x = optimvar('x',[numel(f),1],'LowerBound',0,'UpperBound',50,'type','integer');
Con.upper = P*x+q <= 3;
Con.lower = P*x+q >= -3; %<--- fix missing minus sign
Con.cost = f*x >= 0;
prob = optimproblem('Objective', f*x, 'Constraints', Con);
sol = solve(prob);

Solving problem using intlinprog.
LP:                Optimal objective value is 181.000000.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer
within tolerance, options.IntegerTolerance = 1e-05 (the default value).

x=round(sol.x)

x = 4×1

10 13 20 48

[Derek De Vries]

Last question: With the problem-based approach how do I make those adjustments for varying constraints for each column (instead of just the range of -3 to 3). Does P somehow get adjusted inside of the Con variable? Thanks!

[Matt J]

Put a vector bounds on the right hand side instead of just +/-3.

[Derek De Vries]

As in:

Con.upper = P*x+q <= [5 2 3];
Con.lower = P*x+q <= [-5 -2 -3];

So it would limit Scen #1 from -5 to 5, Scen #2 from -2 to 2, and Scen #3 from -3 to 3. Is that the right way to think of it?

[Matt J]

Yes, but note that since the left hand side is a column vector, you should put column vectors on the right hand side as well.

[Derek De Vries]

Thank you so much for all of the help!