Hi,
I'm interested in solving a nonconvex optimization problem that contains continuous variables and categorical variables (e.g. materials) available from a catalog.
What are the classical approaches? I've read about:
- metaheuristics: random trial and error ;
- dimensionality reduction: https://www.researchgate.net/publication/322292981 ;
- branch and bound: https://www.researchgate.net/publication/321589074.
Are you aware of other systematic approaches?
Thank you,
Charlie
Hi, if I understand well you are dealing with a Mixed Integer Nonlinear Programming Problem (MINLP). You may have a look to the following page that gives some existing solvers:
http://plato.asu.edu/sub/discrete.html
Best
Hi Richard,
Thank you for your answer.
MINLP refers to continuous and discrete (numerical) variables, however my problem has categorical variables (for example, different types of materials). In this context, relaxing discrete variables (like MINLP do) unfortunately does not apply.
Best,
Charlie
Hi, I missed perhaps Something but categorical variables and integer variables. You can Simply assign an integer value to each material no? Best
I don't know if my answer was clear. In case you have for example 10 materials you can simply refer to them by numbrer 1 to 10.
This wouldn't bring anything: MINLP solvers relax the integrity constraint, which turns the integer variable into a continuous variable with range [1, 10], and there's nothing you can do with this variable.
Hi Charlie, MINLP solvers do not relax integer variables, different techniques exist such as the Branch & Bound method for example but in all cases, integer variables remain integer.
I'm familiar with B&B algorithms: solvers indeed branch on integer variables in a specific manner ([1, 10] is split into [1, 5] and [6, 10] for example). However, to avoid a complete enumeration of the combinations (if you have 20 integer variables with range [1, 10], you have 10^20 combinations), solvers compute lower bounds of the problem for each subspace of the search space. To do this, they relax the integrity constraints and solve the corresponding continuous problem.
Same for branch and cut.
Hi, what is the size of your problem? I suppose that in your case you have a few number of materials (e.g. 10). In this case you should have only one integer variable with possible values from 1 to 10 no? Perhaps I Don't understand well your problem. Best
My first intuition in order to solve this kind of problems would be to add binary variables per material possibility (representing the selection of this material), add a (linear constraint) that the sum of these variables equals 1. Add as many variable as you have material characteristics with equaility constraints to make them equal to the scalar product of material catacteristic and their binary variable vector (and use the selected material's characteristics where needed in the model). Then any MINLP solver should work
In a B&B these binary variables would only lead to as many branches as you have materials types (since only one of them can be selected).Not sure how it compares with methods dealing specifically with categorical variables (continuous relaxation and corresponding cuts may not be efficient), but my guess is that if you catalog of material is not too large, it should work fine.
Z. Nedelkov\'a, C.\ Cromvik, P.\ Lindroth, M.\ Patriksson, \and A.-B.\ Str\"omberg}, {\em A splitting algorithm for simulation-based optimization problems with categorical variables}, {\sf Engineering Optimization}, vol.~51 (2019), pp.~815--831.
It might help!
You can also take a look at the following:
http://homepages.cae.wisc.edu/~linderot/papers/Abhishek-Leyffer-Linderoth-07.pdf
Michael Patriksson thanks for the link, I'll have a look.
Cenk Çalışkan thanks! Funnily enough, I had a Zoom chat with Sven this afternoon and he sent me this paper ;)
Hello, I recommend you to use the following optimization algorithm and it meets the characteristics you need, as well as it is possible to adapt to the optimization of variables taken from a list.
https://www.researchgate.net/publication/336656183_Symmetric-Approximation_Energy-Based_Estimation_of_Distribution_SEED_A_Continuous_Optimization_Algorithm
https://www.researchgate.net/publication/341601126_pySEED_a_Python-based_implementation_of_the_Symmetric-Approximation_Energy-Based_Estimation_of_Distribution_SEED_algorithm_A_Continuous_Optimization_Algorithm
For solving such kind of problems it is needed to make evolve solutions codes, by the reason for formulating such problems codes are needed. I have worked over such kind of problems solving by example optimization desing tasks where are needed to determine categorical variables values. In my profile you could find such kind of formulations and solutions outline for designing punching and cutting dies, air conditionning nets, aquedute nets and others.
Thank you all for your answers! I will try to get an overview of the domain and try to see if my ideas can be implemented.
Dear all,
I summarized my ideas in this new preprint: Preprint A global method for mixed categorical optimization with catalogs
I describe a spatial branch and bound method that performs constraint propagation and catalog lookup. I'm interested in your feedback!
Best,
Charlie
Update: I have just published my simple idea for globally solving mixed-categorical problems in the Journal of Global Optimization.
https://www.researchgate.net/publication/377588712
- Badges
- Science topic
- Similar topics
- Political Science
- International History and Politics
- Globalization