Re: [Help-glpk] modeling variable "chains"

[Michael Hennebry]

On Thu, 13 Aug 2009, Yaron Kretchmer wrote:

> I've modeled the resources, and created an array of binary variables which
> describe whether a certain resource exists in a certain X/Y location.
> I'm having difficulties modeling the "paths". My difficulty is this:
> - Each path maps to a pattern of resources (for instance R1->R2->R2->R1). I
> can successfully describe the path contents (i.e. the fact that it contains
> 2 R1's, and 2 R2's), but how can I describe the order i.e. how do I capture
> the fact the pattern has to contain adjacent resources (i.e. you don't want
> a path to include disjoint resources that are spread around your chip, you
> want resources that are in adjanct X/Y coordinates.
>
> So my question:
> *) How do I model the constraint that the resources mapping to a path need
> to have consecutive X or Y coordinates?

This is a lot like finding a path in a sparse graph.
Try having binary variables for the arcs instead of the nodes.

--
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."