2
$\begingroup$

I have a optimization problem in which the optimal objective value occurs at multiple point in the feasible space. If I run my problem in LINGO software then it gives me the optimal objective value at a point in the feasible space but how to get the all points in which optimal solution occurs.

$\endgroup$
  • $\begingroup$ Why did you tag matlab? Is LINGO a package written in MATLAB? $\endgroup$ – Memming Feb 21 '17 at 12:36
  • 1
    $\begingroup$ You haven't told us whether your problem is linear or nonlinear and whether it involves only continuous variables or also has integer variables. For linear and mixed integer linear programming problems there are some ways to answer this question which aren't applicable in the nonlinear case. $\endgroup$ – Brian Borchers Feb 22 '17 at 5:50
  • $\begingroup$ my problem is linear problem in which variables are binary type. But I wanted a solution for the general case in which more than one global optimal solution may occur. $\endgroup$ – Suman Das Feb 22 '17 at 13:10
3
$\begingroup$

In general this is difficult, however, usually you can get a decent solution by initializing at different locations and collecting the solutions. This can be quite time consuming (computationally), and suboptimal (piggybacking on an optimizer), but easy to try.

To choose different locations, you can do either by (1) predefining a grid-like structure, or (2) sampling randomly from a distribution. Prior knowledge such as the smoothness of the objective function, or expected regions where optima are located will help you determine your strategy.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I was thinking about re-initialization at different points as well, but one of the possible disadvantages could be that you end up picking up a number of local extrema that are not, as OP stated, equal to the global extrema. I'm not sure how you could pick up all possibilities of the global solution without having a really good idea of where to look $\endgroup$ – cbcoutinho Feb 21 '17 at 12:47
  • $\begingroup$ @cbcoutinho True. I'm sure my answer here is just a reasonable approximate approach. I'm eager to see a better answer. :) $\endgroup$ – Memming Feb 21 '17 at 13:47
  • 1
    $\begingroup$ @Memming Without prior knowledge of the cost surface and when just using a blackbox solver, I feel this approximate approach is probably the best you're going to get. Perhaps there are specialized codes for this sort of problem, but I am unsure. $\endgroup$ – spektr Feb 21 '17 at 14:28
1
$\begingroup$

Your comment on the question indicates that you're in the special case of a binary integer linear programming problem. For these problems, a standard approach is to find an optimal solution, add a constraint to eliminate that particular solution, and then reoptimize to find another optimal solution.

For example, if your first optimal solution has binary variables with values $x_{1}=1$, $x_{2}=0$, $x_{3}=1$, then you can add the constraint

$(1-x_{1}) + x_{2} + (1-x_{3}) \geq 1$

to eliminate the solution $x_{1}=1$, $x_{2}=0$, $x_{3}=1$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Depends on the type of problem you are dealing with. For non convex see the other answer about multistart. For convex problems, iteratively adding previous solutions as constraints will return alternative optima. Any convex combination of optimal solutions is optimal as well, so in something like an LP there might be variables that can take a range of values at the optimum. For problems with integral variables, again, iteratively add solutions as constraints (these are referred to as integer cuts)

Regarding non convex problems there are methods that fully explore the solution space (spatial branch and bound). These may be capable of finding alternative optima in the rare (at least for problems that only have continuous variables) instance of them existing.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.