How to specify the variables to be integers in fmincon function.

I need to solve a quadratically constrained program by fmincon with all variables restricted in integers. Is it possible to specify variable types in fmincon? If not, is there another way to solve this problem?

Answer 1

[John D'Errico]

You cannot do so. Period. fmincon does not allow integer constraints. To solve that class of problem, you need a integer programming tool, in this case, a nonlinear one. But NOT fmincon.

I believe the genetic optimization tools can allow integer constraints.

[Walter Roberson]

ga() allows integer constraints, but when you have an integer constraint it does not allow nonlinear constraints.

[Abdolkarim Mohammadi]

When you have integer variables in ga(), you can have linear and/or nonlinear inequality constraints. Integer ga() only prohibits linear and/or nonlinear equality constraints.

Answer 2

[Math Works]

Is there an equivalent integer one that doesn't define f as vectors?

[Torsten]

Not clear what you mean.

[Math Works]

Is there an equivalent drop in replacement for fmincon that doesn't change the input and output, that supports integers?

If not, why MATLAB or the math guys haven't made one yet?

Engineers don't want to fiddle with those low level math stuff.

[Torsten]

What do you mean by "that doesn't change the input and output" ?

For linear integer programming problems, you can use "intlinprog".

For all other optimization cases with integer constraints, only "ga" is available in MATLAB. In this case, linear/nonlinear inequality constraints are permitted whereas linear/nonlinear equality constraints aren't.

[Walter Roberson]

No, there is no integer equivalent to fmincon.

The mathematics of the techniques used by fmincon depend on continuity.

The mathematics of discrete optimization are a really major mathematical challenge to optimize, hugely important, lots and lots of work has been put into it.

https://en.m.wikipedia.org/wiki/P_versus_NP_problem

[Math Works]

setting it up is hard.

if function output is vector, then it won't work. I need scaler.

Basically, what goes in and what comes out must not change in any meaningful way.

I am looking for a drop in replacement, or fmincon should just handle function overloading without user intervention.

There are so many optimization functions in MATLAB optimization toolbox. It should just work with a master function and handle all the cases internally. 9 times out of 10 the optimization package will show you a random error that the user should not have to worry about.

I ended up spending 3 hours writing my own domain specific mixed integer optimization function, and it works great. As an Electrical Engineer, I'm disappointed by the math people. Give us something that just works.

[Math Works]

Then you need function overloading to handle it internally using a different method.

[Torsten]

Everything takes time to get accustomed to.

Maybe this is what you are looking for:

https://de.mathworks.com/help/optim/problem-based-approach.html

No worry about solver interfaces, focus on the problem formulation.

[Walter Roberson]

Then you need function overloading to handle it internally using a different method.

No, you need completely different algorithms, with there being no known feasible solutions for even relatively simple situations. "feasible" meaning "substantially faster than just trying all of the possibilities."

Example: suppose you have a container that can hold 12 L, and you have items that are 1, 2, 5, and 8 L, and the task is to pack a subset of the items into the container, coming as close to filling it up as possible without overflowing. With continuous mathematics you just say, "That's easy, take 1 1/2 of the 8 L items". With discrete mathematics you need to run through most of the combinations to arrive at solutions such as 2 of the 5L and 1 of the 2L. This particular problem is not difficult, but in this class of problems, one of the better algorithms is -- exponential time in the number of items.

Integer optimization problems include topics in Public Key Encryption, discrete logarithms, elliptical curve encryption, proof of Fermat's Last Theorem... very tricky stuff.

[Math Works]

Okay, those are very good commnets that provided some insights. My custom Electrical Engineering domain specific implementation of Mixed Integer Constrained Optimization involves a lot of probability theory and has a very bad time complexity. I think it's approximately big-O(n! * n^m). It can probably be improved but I only spent 3 hours on it.

This, however, is a good Applied Math PhD project...

Even if the time complexity is likely exponential for the general MICO problem, I think it's still worth it to be included in the library.

[Walter Roberson]

@Math Works

See https://www.mathworks.com/matlabcentral/answers/602395-different-number-of-for-loops#answer_502861 for discussion and code on creating what has been called an "odometer" pattern suitable for iterating sequentially through all possible combinations of a set of items. It does not try to pre-calculate all of the items, so it only needs enough memory for the "current" iteration and the list of allowed values for each position. It just proceeds one by one, generating the next combination and giving you a chance to process it. You would test the current combination against any combination constraints, and if it passed you would do whatever evaluation was suitable.

The approach is simple, so given enough time it will generate all of the combinations.

It is optimizing the search over integers, reducing the search space, that takes the hard work.

[Math Works]

Yeah, but this for-chain-loop method is only for integers, not mixed integers. Some variables need to be complex doubles (voltage with phase angle, current with phase angle, and complex power) and real doubles (time, length, radius, capacitor size in uF, etc).

[Walter Roberson]

Yes, you generate a set of integers, and then you treat those as locally constant and optimize over the other values. You get a best result for varying the other variables relative to that particular list of integers, and then you move on to the next list of integers, and repeat, keeping track of the best result as you go.

[Math Works]

Yes, that's exactly what I did.

Basically, every for-chain iteration step treats all the integer variables as constants, then do the local continuous constrained optimization problem. With some global tracker variables and helper functions, this can be implemented with some effort.

I still don't understand why MATLAB can't abstract this process though. Just ask for the boundries for the integer variables. Formulating the problem becomes harder when you need to think about the lower level implementations. At that point, I'm better off doing it in C++ directly.