topic Re: Project schedule via LP with Proc Optmodel in Mathematical Optimization, Discrete-Event Simulation, and OR

Project schedule via LP with Proc Optmodel

ODENWALD — Wed, 11 Nov 2020 15:59:52 GMT

Hi :

Because I need to add further constraints using Proc CPM was not deemed appropriate.

Here https://neos-guide.org/content/project-scheduling-critical-path-method I found an example with GAMS.

Being not literate in GAMS I would want to try with Optmodel.

The GAMS attempt uses precedence constraints where I don't know the equivalents in Optmodel.

I'm looking for a decent model in Optmodel since I need a model roughly 10-20 times larger than the easy example.

Here is some part of the link copied in : Did not work !! Please look up the link.

I think one would map the nodes A to H onto the numbers 1 to 8 ...

Who has good ideas ?

Kind regards, Odenwald.

Re: Project schedule via LP with Proc Optmodel

RobPratt — Wed, 11 Nov 2020 19:34:24 GMT

Here is a translation to OPTMODEL:

proc optmodel;
   set activity = /A B C D E F G/;

   set prec = (/A/ cross /B C/) union (/B E/ cross /F/) union {<'C','D'>,<'D','E'>,<'F','G'>};

   num duration{activity} = [2 3 3 4 8 6 2];

   var time;

   var s{activity} >= 0;

   min objective = time;

   con ctime{i in activity}:
      time >= s[i] + duration[i];

   con ptime{<i,j> in prec}:
      s[i] + duration[i] <= s[j];

   solve;

   print time s;
quit;

time
25

[1]	s
A	0
B	2
C	2
D	5
E	9
F	17
G	23

Re: Project schedule via LP with Proc Optmodel

ODENWALD — Wed, 11 Nov 2020 20:21:39 GMT

Hi Rob : Thanks a lot.

There are two questions :

1. How can I print a set of Optmodel ?

2. Are there alternatives to the cross and union sequences ?

Could I somehow input a linear list of all pairs of type (predecessor , successor) of activity nodes ?

Odenwald

Re: Project schedule via LP with Proc Optmodel

RobPratt — Wed, 11 Nov 2020 20:34:13 GMT

You can use the PUT statement to output a set to the log. Yes, you can define prec as a set of pairs:

   set prec = {<'A','B'>,<'A','C'>,<'B','F'>,<'E','F'>,<'C','D'>,<'D','E'>,<'F','G'>};
   put prec=;

You could also read these pairs from a SAS data set:

data indata;
   input i $ j $;
   datalines;
A B
A C
B F
E F
C D
D E
F G
;

proc optmodel;
   set <str,str> prec;
   read data indata into prec=[i j];

Re: Project schedule via LP with Proc Optmodel

ODENWALD — Thu, 12 Nov 2020 11:34:22 GMT

Hi Rob :

Perfect. The question as posed is totally solved. Thank you again.

Unfortunately the real data which we are not allowed to share are such that you don't see much, but produce <infeasible>.

As we could not find an error, I suspect that these data contain so called positive cycles. These are mentioned some times in the literature but mostly excluded from further discussion (these are the equivalents of negative cycles in shortest path problems).

If such effects ever have crossed your path please feel encouraged to comment or recommend a paper.

There have been suggested different LP models for the task under consideration (Neos/GAMS ; Hillier-Lieberman ; Domschke (German) ; ) Possibly there could exist further ones that allow to handle that cycle problem.

Odenwald

Re: Project schedule via LP with Proc Optmodel

RobPratt — Thu, 12 Nov 2020 14:02:27 GMT

I have several suggestions:

1. You can use the IIS= option in the SOLVE WITH LP statement to identify an irreducible infeasible set. For your problem, this will likely return a cycle, as you suspected.

2. You can use the CYCLE= option in the SOLVE WITH NETWORK statement to find a cycle.

For suggestions 1 and 2, you can report the source of infeasibility to the data preparer to correct. But even after correction, there might be another cycle.

3. You can use the CYCLE= option in the SOLVE WITH NETWORK statement to find all cycles (MAXCYCLES=ALL). Then report them all to the data preparer to correct.

4. You can use the MILP solver to find a minimum set of arcs whose removal will eliminate all cycles. To do this, you could introduce a binary variable IsRemoved[i,j] for each arc <i,j>, do step 3 to find all cycles, impose a "cover" constraint sum {<i,j> in ARCS_cycle[c]} IsRemoved[i,j] >= 1 that forces at least one arc to be removed from each cycle, and minimize sum {<i,j> in prec} IsRemoved[i,j]. Then remove the arcs for which IsRemoved[i,j] > 0.5 (a safe comparison for = 1) and proceed with the LP solve.

5. You can introduce a slack variable to measure constraint violation, minimize the sum of slacks, impose an objective cut, and solve again with the original objective:

   var slack{prec} >= 0;
   min infeasibility = sum {<i,j> in prec} slack[i,j];
   con ptime{<i,j> in prec}:
      s[i] + duration[i] <= s[j] + slack[i,j];

   solve;

   num mininfeasibility;
   mininfeasibility = infeasibility.sol;
   con objectivecut:
      infeasibility <= mininfeasibility;

   solve obj objective;

By the way, a cycle for which all durations are 0 is fine. It just means that those activities must all happen at the same time.