1

I was reading about solving optimization problems using meta heuristic techniques. In most of the cases, constrained related problems are converted to unconstrained using penalty functions. I was trying to understand as why constrained problems are hard to solve? Suitable example will be of great help

gari
  • 11
  • 1

2 Answers2

0

Well, it depends on what sort of metaheuristic and what types of constraint. One key properties that I look out for is how do I ensure that the final solution is feasible.

There are meta heuristic that approach the constrained problem directly such as $2$-opt and $3$-opt in traveling salesman problem. However, in general, this need not be the case and we even come out with the notation of projections to ensure feasibility in the end.

Also, sometimes we have a fast solver for the unconstrained problem such as Ising model and QUBO (quadratic unconstrained optimization problem) and there are no ways to incorporate the constrained directly into the solver. It is known that if we penalize the constrained with a large penalty coefficient, then the unconstrained version of the problem is equivalent to the constrained problem.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
0

They are as hard as parameterizing the constraints edge ($C(x)= 0$) with unconstrained variables:

  • if parameterizing of $C(x)= 0$ is hard, solving the optimization problem for various parameterized objective function would give you a parameterization for $C(x)= 0$.
  • if parameterizing of $C(x)= 0$ is not hard, then change the variable and solve unconstrained optimization.
Giorgio Venturi
  • 16
  • I require some more clarity. Let us say we have a single objective function like x^2+y^2 , which has to be minimized subject to constraint that x+2y >6. Now what will be difficulty to solve this problem. May be this example is too simple , but I wanted to understand the essence. – gari Jun 10 '21 at 11:18