Re: [Help-glpk] implementation of graphs and networks in glpk

[xypron]

Hello Andrew,
>>I plan to include in the next release of glpk some new api data
>>structures and routines to deal with graphs and flow networks.

when scheduling jobs typically two variables are used that specify the
relative sequence.

If it is known which variables are used for sequencing special contraints
could be created automatically like:
- tsp cuts
- comb cuts

Furthermore with such a structure specialized branching rules based on a
relaxation to
the linear assignment problem could be used.
cf Marcel Turkensteen, "Advanced Analysis of Branch and Bound Algorithms"
http://dissertations.ub.rug.nl/faculties/eco/2007/m.turkensteen

One description of such a scheduling problem is a disjunctive network.
- conjunctive arks have a fixed sequence (no binaries)
- disjunctive arks allow one node to be either before or after the other
(binaries assigned)

A minimum makespan solution is the one with the shortest maximum length of a
linear path obtained by
fixing all disjunctive arks to be conjunctive.

A description on an ark should allow to specify up to two constraints:
tj - ti < tij OR ti - tj < tji for disjunctive constraints
tj - ti < tij  for conjunctive constraints

Typically additional constraints concerning the time ti, tj will be given
concerning e.g. release
and due dates.

My idea that only a special flag for a constraint is needed to mark it as a
disjunctive constraint.

Here is such a constraint from one of my models. t are the times, x are the
binaries, d is the
fixed duration of an order.

# strengthened Miller-Tucker-Zemlin subtour elimination constraints
s.t. mtz {(i,j) in V} :
     t[j] - t[i] - d[j] 
  + (1 - if (i,j) in I then 0 else x[i,j]) * M 
  - if (j,i) in I then 0 else x[j,i] * ( M - M_[j,i]-d[j])
  >= 0;

It might be sufficient to expand the syntax with a flag "ark":
s.t. mtz {(i,j) in V}, ark :
     t[j] - t[i] - d[j] 
  + (1 - if (i,j) in I then 0 else x[i,j]) * M 
  - if (j,i) in I then 0 else x[j,i] * ( M - M_[j,i]-d[j]) 
  >= 0;

Best regards

Xypron

-- 
View this message in context: 
http://www.nabble.com/implementation-of-graphs-and-networks-in-glpk-tp21131081p21133489.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.