[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] modeling variable "chains"

From: Yaron Kretchmer
Subject: [Help-glpk] modeling variable "chains"
Date: Thu, 13 Aug 2009 14:00:26 -0700

Hi All.

I'm working on a chip routing problem using LP, where you have
*) Some resources you need to connect
*) Some desirable combinations of resources (a.k.a paths) you want to achieve.
There is an X/Y array of locations for the resources.

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?

Any help would be most welcome :)


reply via email to

[Prev in Thread] Current Thread [Next in Thread]