# Cone constraints with mixed integer programming

24 views (last 30 days)
Ben Human on 20 Oct 2020
Commented: John D'Errico on 23 Oct 2020
Hi,
I am trying to optimise a set of 11 variables where x(1:10) are integer variables which have a lower bound of 1 and an upper bound of 3, and x(11) is continuous and can have a value between -inf and inf. The objective function f is linear however there is a second order cone constraint which is required to minimise another objective function. The SOC constraint works with continuous variables using coneprog, however this doesnt seem to allow me to specify integer variables. Is there any way I can solve this problem using the optimisation toolbox?
Many thanks
Ben

Ameer Hamza on 20 Oct 2020
ga(): https://in.mathworks.com/help/gads/ga.html from global optimization toolbox supports integer variables and nonlinear constraints.

Ameer Hamza on 23 Oct 2020
Yes, I meant a general-purpose mixed-integer programming solver that works for nonlinear problems. Only ga() can do that. There is also surrogate optimizer https://www.mathworks.com/help/gads/surrogateopt.html, but it is also limited as compared to ga().
John D'Errico on 23 Oct 2020
You have a nonlinear constraint. intLINprog (caps inserted to make it clear) is a purely linear programmling tool, that solves integer variable problems.
In MATLAB, this is solved using mainly GA for the general case.
Ben Human on 23 Oct 2020
Thanks John, it's a non linear constraint but the objective function is linear hence it should still be solveable and I believe other third party packages can. GA is not part of the optimisation toolbox and it also doesnt guarantee an optimal or unique solution.

Matt J on 23 Oct 2020
Edited: Matt J on 23 Oct 2020
My approach would be to reduce this to a 1-variable minimization over x(11) and solve that with fminsearch,
[Combinations{1:10}]=ndgrid(1:3);
Combinations=reshape(cat(11,Combinations{:}),[],10).';
x11=fminsearch(@(x11)innerProblem(x11,Combinations,f,SOCVariables),x11_guess)
function [fmin,xmin]=innerProblem(x11,Combinations,f,SOCvariables)
....
end
The objective function, which I call innerProblem here, simply does a combinatoric search for the minimum of the conic program over the integer variables subject to a fixed known input value for the eleventh variable x11. Because your integer variables only range from 1 to 3, there aren't that many combinations to search through. All the combinations can be easily pre-computed as columns of the 10x59049 matrix Combinations. Also, the operations needed to evaluate all the combinations are highly vectorizable - no for-loops involved.

Ben Human on 23 Oct 2020
Thanks Matt, appreciate your help. While this would definitely work I'm not sure how scalable it is if the number of variables were to increase especially as there aren't any linear constraints. I was hoping that given the objective function is linear, there would be a dedicated solver that could do it rather than using a heuristic or combinatory approach.
Many thanks
Ben
John D'Errico on 23 Oct 2020
This MAY be the correct solution, in that there are only 3^10 combinations of variables. That makes an exhaustive solution in the linear set a viable problem to solve.
3^10
ans =
59049
That is not a large set at all. Essentially, conditional on the value of x(11), you find the optimal set for the other 10 unknowns. When you find the best value for x(11), you should be done, MAYBE.
The problem I see here is that the solution chosen from the integer set of variables may vary considerably. And that may essentially create an objective function that is discontinuous. In turn, that can easily blow fminsearch out of the water, causing it to converge to a poor solution.
So while Matt's idea may work out, I would look at the results very carefully. For example, if you start from a different point for x(11), how much will the solution vary?
In turn, that suggests a possible extension of Matt's idea: to use a multi-start method. Thus, start fminsearch at various points in the domain of x(11). Save the solution you find from each start point in the set, as well as the function value arrived at there. Then take the best solution arrived at from the various start points. The size of the starting set you try will improve your chances at finding the globally optimal solution.
John D'Errico on 23 Oct 2020
Ben - there IS a solver - GA. That the objective is linear is not sufficient. You have a nonlinear constraint, which makes it a problem that is not solved using the linear programming solvers in MATLAB. So use GA.