MATLAB Answers

Cone constraints with mixed integer programming

24 views (last 30 days)
Ben Human
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

  0 Comments

Sign in to comment.

Accepted Answer

Ameer Hamza
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.

  6 Comments

Show 3 older comments
Ameer Hamza
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
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
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.

Sign in to comment.

More Answers (1)

Matt J
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.

  3 Comments

Ben Human
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
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
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.

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!