Is it possible to find the nearest solution to optimal for a mixed-integer problem? For example I would want the simplified problem below:
f = [1;1;1];
intcon = 1:3;
Aeq = [0.99,0.97,0.15];
beq = 0.16;
lb = zeros(3,1);
ub = [1;1;1];
x = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub)
to return x=[0;0;1]
as this is the nearest integer solution to the objective value of 0.16
. Instead currently it returns
Intlinprog stopped because no point satisfies the constraints.
Does not necessarily have to run intlinprog
. Would ideally need to also work if beq
is low, for example 0.14
.
You can introduce some slack variables to allow some constraint violation when needed as follows:
largeValue = 100; % choose some large value to penalise the constraint violation
f_ = [f; largeValue; largeValue]; % penalise both slack variables
Aeq_ = [Aeq, 1, -1]; % add a positive and negative slack variable to the constraint
beq_ = beq;
lb_ = [lb; 0; 0]; % limit the constraint to a positive number
ub_ = [ub; inf; inf];
x_ = intlinprog(f_,intcon,[],[],Aeq_,beq_,lb_,ub_); % solve the adapted problem
x = x_(1:3) % extract the solution of the original problem
Remarks
I added two (positive) slack variables, one for a positive constraint violation and another one for a negative constraint violation.
You should penalise the slack variables with a large value, otherwise it is beneficial to violate your constraints more than strictly necessary. A more general approach would be to determine a good penalisation value based on the values in f
and Aeq
, for example
largeValue = 2*max(abs(f))/min(abs(Aeq(Aeq ~= 0)))