Cone constraints with mixed integer programming

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

Answer 1

[Ameer Hamza]

ga(): https://in.mathworks.com/help/gads/ga.html from global optimization toolbox supports integer variables and nonlinear constraints.

[Ben Human]

Thanks Ameer, it does but the problem should be solvable using mixed integer programming rather than a heuristic approach.

Many thanks

Ben

[Ameer Hamza]

But MATLAB does not have a mixed-integer programming solver. Only ga() supports integer variables.

[Ben Human]

MATLAB does have a mixed-integer solver:

https://uk.mathworks.com/help/optim/ug/intlinprog.html

but what I am looking for is the ability to add a cone constraint described below:

https://uk.mathworks.com/help/optim/ug/coneprog.html

[Ameer Hamza]

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]

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]

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.

Answer 2

[Matt J]

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]

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]

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]

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.