2
$\begingroup$

I don't know the terminology, so the title can be confusing. Let me explain here.

  1. We would like to find the optimal solution in $S$. Suppose some external theory suggests that there must be an optimal solution in $T\subset S$. Since there may be multiple optimal solutions, there may also be an optimal solution in $S \setminus T$, but if what we only care is to achieve the maximum, then failing to find all the optimal solutions is not a problem. So we can search only in $T$. Is there a name for this simplification method?

or

  1. The optimal solution is contingent. That is, the optimal solution depends on a condition that we don't know ex-ante. But some external theory suggests that whenever $a$ is the optimal solution, $b$ is also the optimal solution. Then an algorithm is that ignoring $a$, after knowing the condition, calculate the payoff of $b$ and other options, then select the optimal one among them.

In sum, in either case, we rule out some options in the feasible set, knowing at least one optimal solution is still in the remaining set and only search within the remaining set.

I am a layman for operations research. So the description may be messy. Let me know if you need more clarification.

$\endgroup$
1
  • $\begingroup$ Another related concept is that of "breaking symmetry", which applies more generally than to optimal solutions. If you know that, given a solution $x$, there is an entire neighbourhood of solutions $N(x) \subset S$ which all have the same objective value as $x$, you might try to add constraints so that only one of the solutions of the neighbourhood is in your feasible set. $\endgroup$ Mar 15 at 7:40

2 Answers 2

2
$\begingroup$

I think the phrase you are looking for is "without loss of optimality." In the branch-and-bound algorithm for mixed integer linear programming, this idea arises when you prune by bound. If the LP bound is strictly worse than the incumbent value, you can always prune by bound. If the LP bound is the same as the incumbent value and you don't care about finding more than one optimal solution, you can still prune by bound.

$\endgroup$
1
  • $\begingroup$ Since the LP bound and incumbent value are floating numbers, should the solver prune the nodes whose bound is strictly $\le$ to the incumbent value, or also prune the nodes whose bound is slightly better than the incumbent value? If it is the latter case, the $\epsilon$ here should be smaller than the total tolerance, right? $\endgroup$
    – xd y
    Mar 13 at 9:58
1
$\begingroup$

You do need to be careful of applying this "we can disregard" idea more than once.

Suppose S contains two subsets, T and U. By some argument, typically symmetry, you might be able to argue that

a) if there is a solution in U, there must also be a solution in S-U.

b) if there is a solution in T, there must also be a solution in S-T.

You can then disregard either T or U, but not both. Discarding both may discard all optimal solutions. There is a literature on Symmetry in Integer Programming which may be of help.

$\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.