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
采纳的回答
Ameer Hamza
2020-10-20
1 个投票
ga(): https://in.mathworks.com/help/gads/ga.html from global optimization toolbox supports integer variables and nonlinear constraints.
6 个评论
Ben Human
2020-10-20
Ameer Hamza
2020-10-20
But MATLAB does not have a mixed-integer programming solver. Only ga() supports integer variables.
Ben Human
2020-10-23
Ameer Hamza
2020-10-23
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
2020-10-23
编辑：John D'Errico
2020-10-23
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
2020-10-23
更多回答（1 个）
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 个评论
Ben Human
2020-10-23
John D'Errico
2020-10-23
编辑：John D'Errico
2020-10-23
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
2020-10-23
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.
类别
在 帮助中心 和 File Exchange 中查找有关 Linear Programming and Mixed-Integer Linear Programming 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
