![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dag_simplex.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / dag|
Return to dag_simplex.c CVS log | Up to [Research Unix] / researchv10no / cmd / dag |
1.1 root 1: #include "draw_dag.h"
2:
3: #include <sys/types.h>
4: #include <sys/times.h>
5: #define TIC 60
6:
7: /*
8: simplex algorithm to solve LP
9: */
10:
11: static int Rows, Cols;
12: static long *Auxf, *Objf, **Arrp;
13:
14:
15: static void readresults(int n_elts, int *array)
16: {
17: for (int i = 0; i < n_elts; i++)
18: {
19: int row = -1;
20: for(int j = 0; j < Rows; j++)
21: {
22: long val = Arrp[j][i];
23: if(val != 0)
24: {
25: if(row >= 0)
26: {
27: row = -1;
28: break;
29: }
30: else if(val != 1)
31: break;
32: else row = j;
33: }
34: }
35: array[i] = (row >= 0 ? Arrp[row][Cols-1] : 0);
36: }
37: }
38:
39:
40:
41: static int FindRow (int col)
42: {
43: long quot;
44: int minrow = -1;
45: long minval = Maxint;
46: register int maxcol = Cols-1;
47:
48: for (register int i = 0; i < Rows; i++)
49: {
50: if (Arrp[i][col] <= 0)
51: continue;
52: quot = Arrp[i][maxcol];
53: if (quot < minval)
54: {
55: minrow = i;
56: minval = quot;
57: }
58: }
59: return (minrow);
60: }
61:
62: static int FindCol()
63: {
64: long minval = Maxint;
65: int mincol = -1;
66: register int maxcol = Cols-1;
67:
68: for (register int i = 0; i < maxcol; i++)
69: {
70: if (Auxf[i] < minval)
71: {
72: mincol = i;
73: minval = Auxf[i];
74: }
75: }
76: return (mincol);
77: }
78:
79: static void MergeRows (register long *row1, register long *row2, int col)
80: {
81: register long fact, *maxrow1 = row1+Cols;
82:
83: switch (fact = row1[col])
84: {
85: case 0 :
86: break;
87: case 1 :
88: while(row1 < maxrow1)
89: *row1++ -= *row2++;
90: break;
91: case -1 :
92: while(row1 < maxrow1)
93: *row1++ += *row2++;
94: break;
95: default :
96: while(row1 < maxrow1)
97: *row1++ -= (*row2++)*fact;
98: break;
99: }
100: }
101:
102: void dag_simplex(int rows, int cols,
103: long **arrp, long *auxf, long *objf, int n_elts, int *array)
104: {
105: struct tms begtm, endtm;
106: int col, row;
107: long val;
108:
109: Rows = rows;
110: Cols = cols;
111: Arrp = arrp;
112: Auxf = auxf;
113: Objf = objf;
114:
115: if(Verbose)
116: {
117: fprintf(stderr,"In simplex: rows = %d, Columns = %d\n",Rows,Cols-1);
118: times(&begtm);
119: }
120:
121: register int maxcol = Cols-1;
122: for(int cnt = 0;; cnt++)
123: {
124: /* Find least coeff. in auxf. */
125: col = FindCol();
126: val = Auxf[col];
127: if (val >= 0)
128: {
129: if (!Objf)
130: {
131: if (Verbose)
132: fprintf (stderr, "Passes = %d\n",cnt);
133: break;
134: }
135: Auxf = Objf;
136: Objf = NULL;
137: continue;
138: }
139:
140: row = FindRow(col);
141: val = Arrp[row][col];
142: if (val != 1)
143: panic("non-unit pivot");
144: for(register int i = 0; i < Rows; i++)
145: if(i != row)
146: MergeRows(Arrp[i], Arrp[row], col);
147: if(Objf != NULL)
148: MergeRows(Objf, Arrp[row], col);
149: MergeRows(Auxf, Arrp[row], col);
150: for(i = 0; i < Rows; i++)
151: if (Arrp[i][maxcol] < 0)
152: panic("Non-canonical form\n");
153: }
154:
155: readresults(n_elts,array);
156:
157: if(Verbose)
158: {
159: times(&endtm);
160: int total = (endtm.tms_utime-begtm.tms_utime) +
161: (endtm.tms_stime-begtm.tms_stime);
162: int percent = (total - (total/TIC)*TIC)*100/TIC;
163: fprintf(stderr,"Time in simplex: %d.%02ds\n",
164: total/TIC, percent);
165: }
166: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.