5

I am looking for a list of solution methodologies that solves a discrete optimization problem, except that the objective function evaluated at any feasible point can only be obtained by performing a simulation. In other words, for any $(\bar{x}, \bar{y})$ that satisfies constraints \eqref{1}-\eqref{3}, we can only obtain $F(\bar{x}, \bar{y})$ by performing a simulation. We may assume that $F(\cdot)$ is a deterministic function bounded over the feasible region, $X, Y$ are convex sets. \begin{align} \underset{x \in \lbrace{0,1 \rbrace}^n, y \in \mathbb{R}^m }{\mathrm{min}}& \quad F(x, y)\\ \text{s.t.}& \quad Ax + By \leq c \tag1\label1\\ & \quad x \in X \tag2\label2\\ & \quad y \in Y \tag3\label3\\ \end{align} I am looking to get an awareness to the different solution methodologies designed for such problems. Some papers that I thought could be useful to this problem are:

[1] "Combining Optimization and Simulation Using Logic Based Benders Decomposition", Forbes et al.

[2] "Optimizing over an Ensemble of Trained Neural Networks", Wang et al.

It would be great if people will be kind enough to comment with a brief description of why the paper may be useful. For example, I think [2] can be relevant, if we are somehow able to build a surrogate function for the optimization objective in terms of a Neural network (NN) with ReLu activations.

batwing
  • 1,458
  • 6
  • 15
  • 1
    So the objective function is evaluated by deterministic simulation, and with "no" or at least very small error? Can you evaluate derivatives, for instance by automatic differentiation of the simulation, or by using an "adjoint" simulation? Given that y is continuous, this is a (binary) mixed integer nonlinear programming problem with black (or grey) box objective function evaluation. – Mark L. Stone Mar 28 '23 at 00:29
  • @MarkL.Stone: Yes, we can assume no simulation error. Could you point me to some good references on automatic differentiation. – batwing Mar 28 '23 at 00:38
  • Are you only interested in these two papers, or in how to solve these kinds of problems in general? – fontanf Mar 28 '23 at 05:47
  • Is evaluating $F(\cdot)$ slow/expensive, or does the simulation run reasonably quickly? – Nelewout Mar 28 '23 at 07:20
  • LocalSolver provides a blackbox solver. Other options include NOMAD (free). – Kuifje Mar 28 '23 at 12:25
  • @batwing You can look at https://www.mathworks.com/help/optim/ug/autodiff-background.html , among other things.I'm not sure there is an in depth easily accessible and understandable reference. Basically, automatic differentiation "diffeentiates" a computer program, producing a computer program which produces the derivative (or gradient) if the original program. – Mark L. Stone Mar 28 '23 at 14:30
  • @fontanf : I am interested in all the different solution approaches available for this problem, so not limited to the 2 papers mentioned. – batwing Mar 28 '23 at 17:48

2 Answers2

4

A 2008 paper by Jack Kleijnen discusses a version of response surface methodology for optimization of one (response) variable in a simulation given constraints on other variables in the simulation. Response surface methodology involves estimating (via interpolation, regression estimation or something similar) the functional relationship between the response variable and the controllable variables (i.e., estimating your $F$). I don't recall what sorts of constraints Kleijnen discussed, but he does say in the introduction that his focus is on simulation models that are expensive to run.

Full reference: Jack P.C. Kleijnen, "Response surface methodology for constrained simulation optimization: An overview", Simulation Modelling Practice and Theory, Volume 16, Issue 1, 2008, pp. 50-64. ISSN 1569-190X, https://doi.org/10.1016/j.simpat.2007.10.001.

prubin
  • 39,078
  • 3
  • 37
  • 104
4

Optimization via Simulation (or Surrogated Optimization or Simulation-based optimization) is an umbrella term for all optimization algorithms that rely on a simulation to evaluate objective functions and/or constraints. It includes direct usage of simulation (like the Kleinen's paper suggested by Prubin), indirect use of simulation (like it is explained in this review) and hybrid schemas (like this).

A good approach to solve those kinds of problems is to use metaheuristics in an Optimization via Simulation scheme (as an example, see this paper).

Regarding discrete optimization problem, here is a good review.

Enrique Gabriel Baquela
  • 636
  • 1
  • 7