[clemsen]

I would love to get more details on the linear-integer solve methodology, as it sounds impressive. Was the problem formulated to also work as a linear problem where the binary or integer variables were first treated as positive non-integer variables, and then checked using branch-and-cut (That's how I would do it)? Or did you do something differently?

  Fortunately, we found a different plan of attack: one
  which allowed the integer-linear-programming solver to
  explore the problem space more efficiently and find 
  optimal solutions faster. What previously took an hour, 
  now took 0.2 seconds.

[ant6n]

It was simply modelled using a bunch of binary variables. Basically for every segment, we want to find the position of every line. So first we tried the 'traditional' approach of modelling the positions as a set of binary variables that say

    Line_i_at_position_k

It just takes a long time because there are a lot of binary variables, and the penalties derive from the binary variables in an awkward way.

Later we started using a model using variables like

    smaller_i_j

Just denoting whether line i is at a smaller position (index) than line j. You can enforce total ordering using the triangle inequality as a constraint. And the penalties very directly derive from the binary variables, because the penalties are all about things like 'apply penalty if line i is left of line j'.

Another thing to note is that New York-Washington is all connected. But some of the connections have only a single (commuter rail) line. So mathematically speaking, Washington and New York are actually independent. The MILP solver sometimes seemed to have trouble finding those independent components, so it helped providing them as separate models.

[samstave]

totally naive and off the top of my head...

Can your process be applied as a plugin/core function of cad programs for designing buildings/other systems...

Such that I can relatively roughly draft a layout of a floor-plan, and then have your ideas "think" out a layer for piping, electrical, lighting etc...

the idea would be to avoid physical interferences, and then take your logic to say "oh this is a floor plan and the lighting layer-elements should be within the boundary of the walls, and I am to lay them out on an NxN grid, so ill propse this layout and the designer can just adjust as needed - but I am aware of the walls so I know I can only place this many WRT the layout" and "ah, this is a wall, and a ceiling, my electrical conduit must run up/in the wall and along the ceiling, and no conduit can intersect - but I need a junction box every N feet/[condition] and my radius for each turn must be within [spec]"

Basically ML/AI assisted CAD... I think you should explore that - electrical/plumbing conduit designs effectively adhere/require your design logic....

Just a thought.

[samstave]

To reply to my own comment, I know that this already can be ~accomplished with, say, revit, I think there are efficiencies to be gained by what they are dount (autodesk should aquire these MOFOs...)

Basically define an elements requirements;

BusStop; Range = X Schedule = Y Frequency = Z FuelReq = AA

etc..

Then you do something like a fixture:

2X4 Fixture; Power = X T24 = Y

Then you setup a standard and a repo for people to post objects to a lib and let them select those things and just plop them on a drawing and the reqs will get calculated.

Although, I was not able to know how they calculated the cost per year for any of their examples... where does that data come from???

[raverbashing]

Was it GLPK or something else used?

[ant6n]

We used PuLP, which in turn uses cbc (part of the COIN-OR) project. I used to use lp_solve, but cbc turned out to be able to solve more complicated problems more quickly.