Mixed-Integer Nearest Optimal Solution in Matlab

Question

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.

Answer 1

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)))