Re: [Help-glpk] RE: Help-glpk Digest, Vol 22, Issue 13

[Michael Hennebry]

On Tue, 21 Sep 2004, Rich Wu wrote:

> Thanks for the answer,  I'm aware now that the
> abs(CountryColor[ct1]-CountryColor[ct2])>=1 is a non-linear constraint. My
> goal is to limit the color for adjacent countries to be different,
> CountryColor[ct1]<>CountryColor[ct2], as GLPK solver doesn't allow strict
> inequality, then how should I revise the code to accomplish the goal?

x[r,c] = 1 if region r has color c, else 0
x[r,c] + x[s,c] <= 1  for any color c and any adjacent regions r and s

Though mathematically sufficient, the linear relaxation is rather loose.
At most two colors will be required.

The constraint can be improved:
 SUM x[r,c] <= 1   for any color c and set S of mutually adjacent regions
r in S

Given a planar graph, an S can have up to four regions.

-- 
Mike   address@hidden
"Nothing says it like words if you know how to use them."
                    --  the Professional Organization of English Majors