Better way to formulate non overlapping constraints

[Ashutosh]

Hi,

I am working on a problem which involves placing a number of blocks on a straight line, without any overlap.  I tried solving it in Gurobi and CPLEX and in both cases, after the first 2-3 second (when the Gap reduces from say 20% to 17%), the solution does not improve at all for several hours.  I am wondering if the problem is the formulation.

Let the left X coordinate and the width of block i be represented by Li and Wi.  Wi is fixed, Li is variable.  For block i and block j to be non overlapping, I am introducing a binary variable Zij which is 1 if block i is on right of block j and 0 if block i is on left of block j.  To model this, I am writing the following two constraints for each pair of blocks i and j

  Li - Lj - Wi * Zij - M * Zij <= -Wi

  Li - Lj - Wj * Zij - M * Zij >= -M

Where M is a large number (I am putting it equal to the sum of width of all blocks, as that is the maximum distance between Li and Lj).  So, for a total of N blocks, there are N^2 binary variables and 2*N^2 constraints.  I understand that this may be too much, but in my application, the number of blocks will always be less than 80 (thus, no more than 6K binary variables and 12K constraints.

Is there a better way to write this problem which hopefully will lead to solving this to closer to optimality?  I know the initial feasible solution to the problem, and did try with and without passing this solution as an mst file.  This did not effect the observed behavior where the solution does not improve after first few second, for several hours.

regards,

Ashutosh

[Greg Glockner]

Models with disjunctive constraints tend to be very slow to solve, especially because the LP relaxation tends to smear the results, placing items on top of each other. In my past experience, other model formulations tend to be more effective.

[qiong jia]

I tried the model about facility layout formulation by gurobi by
chance. Please refer to the paper:
Heragu, S. S. and A. Kusiak (1991). "Efficient Models for the Facility
Layout Problem." European Journal of Operational Research 53(1): 1-13.
There is the math method to transform the non-linear constraints to be
linear. And you can solve the linear model by Gurobi or cplex
directly. If the problem is small, you can get the optimal solution
directly.

On 8月1日, 下午4时55分, Ashutosh <ashutosh.chakrabo...@gmail.com> wrote:
> Hi,
>
> I am working on a problem which involves placing a number of blocks on a
> straight line, without any overlap.  I tried solving it in Gurobi and CPLEX
> and in both cases, after the first 2-3 second (when the Gap reduces from say
> 20% to 17%), the solution does not improve at all for several hours.  I am
> wondering if the problem is the formulation.
>
> Let the left X coordinate and the width of block i be represented by Li and

> Wi.  *Wi is fixed*, Li is variable.  For block i and block j to be non

[Sergio Bruno]

Check professor's Ignacio Grossmann work about disjunctive
constraints. He has some specialized algorithms.

[Ashutosh]

Much thanks Greg, Qiong, and Sergio.

I read through the papers referred and they are interesting.  If I implement any of them and get good results, will come back and post its results.

For now, I am solving it sub optimally by solving it similar to linear assignment problem (but using LP instead of Hungarian - due to unequal sizes of my blocks).  This wrongly estimates the cost of any connections among the movable objects.  In my data, most of the connectivity is due to connection to fixed objects, thus the wrong estimation does not seem to affect quality that much - at least on smaller benchmarks where I could do exhaustive enumeration.

regards,
Ashutosh