4
$\begingroup$

Local search, as the name suggests, takes a local angle to the optimization problem. In deep learning, an adjacent field, the "local minima" problem is frequently mitigated by increasing the number of dimensions, potentially inflating the count by orders of magnitude. At first, this may seems counter-intuitive, as a problem with many more variables may "feel" more complex than a variant of the same problem with much fewer variables.

I would like to know if there are known results on such a line of thoughts - aka inflating the number of decision variables - for local search.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ In integer programming, it is well-known that the "dimensionality" (say the number of discrete variables) is not a good measure for how easy the model can be solved. Unfortunately, many reformulations are very problem-dependent (maybe less so in deep learning). $\endgroup$
    – Erwin Kalvelagen
    Jul 15, 2021 at 8:59
  • $\begingroup$ Not really on the number of decision variables, but it is common to allow searching the infeasible space. It might seem counter-intuitive, since enlarging the search space with worse solutions could make the good ones harder to find, but in practice they might help jumping from one feasible solution to a better one $\endgroup$
    – fontanf
    Jul 16, 2021 at 20:30
  • $\begingroup$ I don't think this is a good argument for MIP solvers. I assumed your local search was to be used in the framework of a branch-and-bound solver. $\endgroup$
    – Erwin Kalvelagen
    Jul 16, 2021 at 21:18
  • $\begingroup$ Yes, sorry, I was referring to local search algorithms $\endgroup$
    – fontanf
    Jul 16, 2021 at 21:22
  • $\begingroup$ So was I. LS is a well-known approach for difficult MIP models. Some MIP solvers even have LS algorithms built-in (e.g. the Relaxation Induced Neighborhood Search (RINS) heuristic). In other cases we do it ourselves, mostly by fixing/unfixing variables. $\endgroup$
    – Erwin Kalvelagen
    Jul 18, 2021 at 8:51

2 Answers 2

Reset to default
4
$\begingroup$

Redefining the solution space is a way to make local search heuristics perform better. This is useful for tightly constrained problems where moving from one feasible solution to another is difficult.

Reformulating the problem, in particular redefining the set of decision variables, is a way to proceed. Such reformulations are well known in integer programming. They are called "extended formulations", thus leading to a considerable (possibly exponential) increase in the number of variables. For example, have a look at the paper by Sadykov and Vanderbeck for an introduction to this method.

For example, consider a machine scheduling problem where many complex constraints are defined to rule the way tasks can be performed together on each machine. In such a context, basic local search approaches perform poorly. Indeed, moving from one feasible schedule to another feasible schedule by exploring basic, local neighborhoods (that is, using basic moves and exchanges of tasks) is very hard. In that case, an extended reformulation consists of generating sets of feasible schedules for each machine (possibly heuristically) and then deciding the schedule for each machine (possibly heuristically). The second step can be viewed as solving a set partitioning problem, which can be done by using integer linear programming techniques, but also by using local search methods (moving and exchanging schedules, instead of tasks).

Improve this answer
$\endgroup$
1
$\begingroup$

In general, increasing the dimension of the neighbourhood of a local search can improve the final results, because a local optimum for a neighbourhood is not necessarily a local optimum for a different one, but you need to find a smart way of evaluating the much larger set of solutions. The extent to which this is possible depends on the problem, the neighbourhood used, and possibly other factors such as the solution representation.

The use of neighbourhoods of increasing size is the idea underlying Variable Neighbourhood Descent (VND, see e.g. this book chapter). Large/Very Large Neighbourhood Search, (some) matheuristics, Dynasearch use efficient methods (mathematical programming, dynamic programming, etc) to explore large neighbourhoods.

Which neighbourhood will work well for a problem, for the computational effort you're willing to invest, in general you won't know until you try.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, but I am referring to the inflation / increase of the decision variables themselves, obviously introducing redundancies. Controlling the neighborhood size is very important, but I am pointing a slightly different angle here. $\endgroup$
    – Joannes Vermorel
    Jul 15, 2021 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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