2
$\begingroup$

I have a multi-objective mixed integer nonlinear problem to solve. For this particular problem the objective functions are not defined for fractional values of the integer constrained variables.

From my initial review of the a few textbooks and papers, as well as searches on this forum, The only methods to solve mixed integer nonlinear problems requires the relaxation of the integer constants to fractional values during the search for the solution (eg: branch-and-bound, outer approximation)

Since my objective functions are undefined for fractional values of the integer constrained variables, these relaxation based methods are not appropriate. Are there any known methods (other than a brute force approach) which don't rely on relaxation?

I should mention that my objective functions are non-convex, but I would still be interested in methods for convex objectives.

Thanks in advance

Edit 1: I should have mentioned that my cost function value is only available from simulations, where the simulations are set up using continuous and discrete parameters which are my decision variables. I think this could limit me to pattern search methods, but any input from forum members or confirmation that I'm looking in the right direction would be helpful.

I've also come across Mixed Variable Programming where the decision variables can also include categorical variables (eg: the colours red, yellow and blue), rather than integer and continuous values.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Mixed-Integer Sequential Quadratic Programming, MISQP, fulfills your criteria (leaving aside multi-objective).

http://www.klaus-schittkowski.de/misqp.htm

Purpose: MISQP solves mixed-integer nonlinear programming problems by a modified sequential quadratic programming (SQP) method. It is not assumed that integer variables are relaxable, i.e., problem functions are evaluated only at integer points. The code is applicable also to nonconvex optimization problems.

Numerical Method: The algorithm is stabilized by a trust region method including Yuan's second order corrections. The Hessian of the Lagrangian function is approximated by BFGS updates subject to the continuous and integer variables. Successively, mixed-integer quadratic programs must be solved.

Also see the references listed there. For instance, O. Exler, K. Schittkowksi (2007): "A trust region SQP algorithm for mixed-integer nonlinear programming", Optimization Letters, Vol. 1, 269-280 http://www.klaus-schittkowski.de/misqp0_rep.htm

$\endgroup$
7
  • $\begingroup$ Thanks for directing me to this method and associated papers. I should add that my cost function value is only available through simulation, and the simulation depends on both continuous and integer parameters, which are my decision variables. Since I cannot calculate the gradient of the cost function, the method you suggest isn't going to be helpful. I'll add an edit to my question to include this detail. The more I read, it seems that pattern search methods may be the only way forwards. $\endgroup$ Commented May 3, 2019 at 2:56
  • $\begingroup$ Do you have the source code available for the simulation? If so, you may be able to use an automatic differentiation tool to compute the gradient (for instance by source transformation which produce a program which calculates the gradient (and objective function). If source code is not available, you can compute the gradient by forward or central finite differences. Note that MISQP is intended for integer variables which have a "continuous" effect or meaning, not categorical. If the simulation is stochastic (Monte Carlo) rather than deterministic, there are significant extra complications. $\endgroup$ Commented May 3, 2019 at 9:47
  • $\begingroup$ As to "continuous" effect or meaning, not categorical: For instance, a beam is available only in discrete lengths or thicknesses, which makes it an integer variable, but the meaning or effect of length or thickness is continuous. There is no hard and fast requirement for what constitutes continuous effect, but the closer most of your variables come to achieving it, the better the MISQP is lilikely to work.If you still have a couple of categorical type variables left, one option is to do a separate MISQP for ach value, then picck the best of the solutioins to the MISQP problems. $\endgroup$ Commented May 3, 2019 at 9:52
  • $\begingroup$ The simulation is for the closed loop control of a system using model predictive control (MPC), Due to the nature of MPC, the cost function in my problem (which is the closed loop cost of the simulation) is not differentiable with respect to the decision variables in my problem. Regarding "continuous effect or meaning", my decision variables include both strictly integer values and categorical variables. For example, the prediction horizon length, which must be an integer for the (discrete time) MPC controller used in my simulation to be defined. $\endgroup$ Commented May 4, 2019 at 12:32
  • $\begingroup$ I'm not sue why the cost function would not be differentiable w.r.t the decision variables, at least the continuous variables and the coitinuous "effect" variable. There is a distinction between not differentiable and not having a closed form for the derivative. You perhaps should read up on automatic differentiation. One possible manifestation of that for differential equations is formulating and numerically solving adjoint equations to get the gradient of the objective function. It gets complicated, but then again, so is your problem. $\endgroup$ Commented May 4, 2019 at 13:18

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.