I am solving a placement problem, i.e. map $integers\ i\ from\ 0\ to\ 6$ to $(x_i,y_i)\ st\ 1 \le x_i,y_i\le 3$ such that :
$ \sum\limits_{i=0}^6 \sum\limits_{j=0}^6 Cost(i,j)*(|x_i - x_j | + | y_i - y_j|)$ is minimised.
The constraints for the LP problem are:
$ \forall i\ 1 \le x_i\le 3 \ \ \ (1) \\ \forall i\ 1 \le y_i\le 3 \ \ \ (2) \\ \forall i\ne j \ |x_i - x_j | + | y_i - y_j| >= 1 \ \ \ (3) \\ $
Since you cannot have absolute values in the objective, I introduced new variables and the problem was modified to the following:
Minimize : $ \sum\limits_{i=0}^6 \sum\limits_{j=0}^6 Cost(i,j)*(x_{ij} + y_{ij})$
with constraints:
$ \forall i\quad 1 \le x_i\le 3 \ \ \ (1) \\ \forall i\quad 1 \le y_i\le 3 \ \ \ (2) \\ \forall i\ne j \quad |x_i - x_j | + | y_i - y_j| >= 1 \ \ \ (3) \\ \forall i,j \quad x_{ij} \ge x_i +x_j \ \ \ (4) \\ \forall i,j \quad x_{ij} \ge -(x_i +x_j) \ \ \ (5) \\ \forall i,j \quad y_{ij} \ge y_i +y_j \ \ \ (6) \\ \forall i,j \quad y_{ij} \ge -(y_i +y_j) \ \ \ (7) \\ $
Now, since Constrant (3) is also not allowed in Linear Programming,one approach is to use binary variables to break it up into 4 sets of linear constraints. But that takes TOO long to solve. Is there some way to get a sub-optimal solution to this LP problem?
Please help!
Constraint $(3)$ is non convex being of the form $|| p_i - p_j||_1\geq 1$, with $p_i=(x_i,y_i)$. There is no way, as far as I know, to convert it in a convex problem, and therefore not even in an LP.
You can either use the binary variable, or just try to solve it with some global optimization algorithm.
Since you are introducing binary variables, your solver is automatically running a B&B that seems to have an hard time solving the problem. That' way it takes TOO long.