5 public class LinearProgramming {
7 public final static short FAIL = -1;
9 public final static short NULL = 0;
10 public final static short FALSE = 0;
11 public final static short TRUE = 1;
13 public final static short DEFNUMINV = 50;
15 /* solve status values */
16 public final static short OPTIMAL = 0;
17 public final static short MILP_FAIL = 1;
18 public final static short INFEASIBLE = 2;
19 public final static short UNBOUNDED = 3;
20 public final static short FAILURE = 4;
21 public final static short RUNNING = 5;
23 /* lag_solve extra status values */
24 public final static short FEAS_FOUND = 6;
25 public final static short NO_FEAS_FOUND = 7;
26 public final static short BREAK_BB = 8;
28 public final static short FIRST_NI = 0;
29 public final static short RAND_NI = 1;
31 public final static short LE = 0;
32 public final static short EQ = 1;
33 public final static short GE = 2;
34 public final static short OF = 3;
36 public final static short MAX_WARN_COUNT = 20;
38 public final static float DEF_INFINITE = (float)1e24; /* limit for dynamic range */
39 public final static float DEF_EPSB = (float)5.01e-7; /* for rounding RHS values to 0 determine
40 infeasibility basis */
41 public final static float DEF_EPSEL = (float)1e-8; /* for rounding other values (vectors) to 0 */
42 public final static float DEF_EPSD = (float)1e-6; /* for rounding reduced costs to zero */
43 public final static float DEF_EPSILON = (float)1e-3; /* to determine if a float value is integer */
45 public final static float PREJ = (float)1e-3; /* pivot reject (try others first) */
47 public final static int HASHSIZE = 10007; /* prime number is better, MB */
48 public final static int ETA_START_SIZE = 10000; /* start size of array Eta. Realloced if needed */
49 public final static String STD_ROW_NAME_PREFIX = "r_";
53 public Ref(float v) { value = v; }
56 public static class Simplex {
58 Problem Lp; /* pointer to active problem */
85 float[] Best_solution;
99 int Warn_count; /* used in CHECK version of rounding macro */
101 public void set_mat(Problem lp, int Row, int column, float Value)
103 int elmnr, lastelm, i;
104 // System.err.println("lp.mat.length = " + lp.mat.length);
106 if(Row > lp.rows || Row < 0)
107 System.err.print("Row out of range");
108 if(column > lp.columns || column < 1)
109 System.err.print("column out of range");
110 if(lp.scaling_used != FALSE)
111 Value *= lp.scale[Row] * lp.scale[lp.rows + column];
113 if(true /*abs(Value) > lp.epsilon*/)
115 if (lp.basis[column] == TRUE && Row > 0)
116 lp.basis_valid = FALSE;
117 lp.eta_valid = FALSE;
118 elmnr = lp.col_end[column-1];
119 while((elmnr < lp.col_end[column]) ?
120 (lp.mat[elmnr].row_nr != Row) : false)
123 if((elmnr != lp.col_end[column]) ?
124 (lp.mat[elmnr].row_nr == Row) : false )
125 if (lp.scaling_used != FALSE)
127 if (lp.ch_sign[Row] != FALSE)
128 lp.mat[elmnr].value =
129 -Value * lp.scale[Row] * lp.scale[column];
131 lp.mat[elmnr].value =
132 Value * lp.scale[Row] * lp.scale[column];
136 if (lp.ch_sign[Row] != FALSE)
137 lp.mat[elmnr].value = -Value;
139 lp.mat[elmnr].value = Value;
143 /* check if more space is needed for matrix */
144 if (lp.non_zeros + 1 > lp.mat_alloc) throw new Error("not enough mat space; this should not happen");
146 /* Shift the matrix */
147 lastelm=lp.non_zeros;
148 for(i = lastelm; i > elmnr ; i--)
149 lp.mat[i]=lp.mat[i-1];
150 for(i = column; i <= lp.columns; i++)
153 /* Set new element */
154 lp.mat[elmnr].row_nr=Row;
156 if (lp.scaling_used != FALSE)
158 if (lp.ch_sign[Row] != FALSE)
159 lp.mat[elmnr].value=-Value*lp.scale[Row]*lp.scale[column];
161 lp.mat[elmnr].value=Value*lp.scale[Row]*lp.scale[column];
165 if (lp.ch_sign[Row] != FALSE)
166 lp.mat[elmnr].value=-Value;
168 lp.mat[elmnr].value=Value;
171 lp.row_end_valid=FALSE;
174 if (lp.active != FALSE)
175 Non_zeros=lp.non_zeros;
180 public void set_obj_fn(Problem lp, float[] row)
182 for(int i=row.length-1; i>0; i--) row[i] = row[i-1];
186 for(i = 1; i <= lp.columns; i++)
187 set_mat(lp, 0, i, row[i]);
191 public void add_constraint(Problem lp, float[] row, short constr_type, float rh)
193 for(int i=row.length-1; i>0; i--) row[i] = row[i-1];
202 addtoo = new short[lp.columns + 1];
204 for(i = 1; i <= lp.columns; i++)
213 //newmat = new Matrix[lp.non_zeros];
216 newmat = lp.alternate_mat;
217 for (i = 0; i < newmat.length; i++) { newmat[i].row_nr = 0; newmat[i].value = 0; }
219 if (lp.non_zeros > lp.mat_alloc) throw new Error("not enough mat space; this should not happen");
222 if(lp.rows > lp.rows_alloc)
223 throw new Error("not enough rows; ("+lp.rows+" needed, have "+lp.rows_alloc+") this should never happen");
225 if (lp.scaling_used != FALSE)
228 for(i=lp.sum; i > lp.rows; i--)
229 lp.scale[i]=lp.scale[i-1];
233 if (lp.names_used != FALSE)
234 lp.row_name[lp.rows] = new String("r_" + lp.rows);
236 if(lp.scaling_used != FALSE && lp.columns_scaled != FALSE)
237 for(i = 1; i <= lp.columns; i++)
238 row[i] *= lp.scale[lp.rows+i];
241 lp.ch_sign[lp.rows] = TRUE;
243 lp.ch_sign[lp.rows] = FALSE;
247 for(i = 1; i <= lp.columns; i++)
249 for(j = stcol; j < lp.col_end[i]; j++)
251 newmat[elmnr].row_nr=lp.mat[j].row_nr;
252 newmat[elmnr].value=lp.mat[j].value;
255 if(addtoo[i] != FALSE)
257 if(lp.ch_sign[lp.rows] != FALSE)
258 newmat[elmnr].value = -row[i];
260 newmat[elmnr].value = row[i];
261 newmat[elmnr].row_nr = lp.rows;
268 lp.alternate_mat = lp.mat;
271 for(i=lp.sum ; i > lp.rows; i--)
273 lp.orig_upbo[i]=lp.orig_upbo[i-1];
274 lp.orig_lowbo[i]=lp.orig_lowbo[i-1];
275 lp.basis[i]=lp.basis[i-1];
276 lp.lower[i]=lp.lower[i-1];
279 for(i= 1 ; i <= lp.rows; i++)
280 if(lp.bas[i] >= lp.rows)
283 if(constr_type==LE || constr_type==GE)
285 lp.orig_upbo[lp.rows]=lp.infinite;
287 else if(constr_type==EQ)
289 lp.orig_upbo[lp.rows]=0;
293 System.err.print("Wrong constraint type\n");
297 lp.orig_lowbo[lp.rows]=0;
299 if(constr_type==GE && rh != 0)
300 lp.orig_rh[lp.rows]=-rh;
302 lp.orig_rh[lp.rows]=rh;
304 lp.row_end_valid=FALSE;
306 lp.bas[lp.rows]=lp.rows;
307 lp.basis[lp.rows]=TRUE;
308 lp.lower[lp.rows]=TRUE;
310 if (lp.active != FALSE)
315 public void del_constraint(Problem lp, int del_row)
321 if(del_row < 1 || del_row > lp.rows)
323 System.err.println("There is no constraint nr. " + del_row);
330 for(i = 1; i <= lp.columns; i++)
332 for(j=startcol; j < lp.col_end[i]; j++)
334 if(lp.mat[j].row_nr!=del_row)
336 lp.mat[elmnr]=lp.mat[j];
337 if(lp.mat[elmnr].row_nr > del_row)
338 lp.mat[elmnr].row_nr--;
344 startcol=lp.col_end[i];
347 for(i = del_row; i < lp.rows; i++)
349 lp.orig_rh[i] = lp.orig_rh[i+1];
350 lp.ch_sign[i] = lp.ch_sign[i+1];
351 lp.bas[i] = lp.bas[i+1];
352 if (lp.names_used != FALSE)
353 lp.row_name[i] = lp.row_name[i+1];
355 for(i = 1; i < lp.rows; i++)
356 if(lp.bas[i] > del_row)
359 for(i=del_row; i < lp.sum; i++)
361 lp.lower[i]=lp.lower[i+1];
362 lp.basis[i]=lp.basis[i+1];
363 lp.orig_upbo[i]=lp.orig_upbo[i+1];
364 lp.orig_lowbo[i]=lp.orig_lowbo[i+1];
365 if (lp.scaling_used != FALSE)
366 lp.scale[i]=lp.scale[i+1];
372 lp.row_end_valid=FALSE;
374 if (lp.active != FALSE)
377 lp.basis_valid=FALSE;
381 public void add_column(Problem lp, float[] column)
387 if (lp.columns > lp.columns_alloc) throw new Error("not enough cols; this should never happen");
388 if (lp.non_zeros + lp.rows+1 > lp.mat_alloc) throw new Error("not enough mat space; this should not happen");
390 if (lp.scaling_used != FALSE)
392 for(i = 0; i <= lp.rows; i++)
393 column[i]*=lp.scale[i];
397 elmnr=lp.col_end[lp.columns-1];
398 for(i = 0 ; i <= lp.rows ; i++)
401 lp.mat[elmnr].row_nr=i;
402 if(lp.ch_sign[i] != FALSE)
403 lp.mat[elmnr].value=-column[i];
405 lp.mat[elmnr].value=column[i];
409 lp.col_end[lp.columns]=elmnr;
410 lp.orig_lowbo[lp.sum]=0;
411 lp.orig_upbo[lp.sum]=lp.infinite;
412 lp.lower[lp.sum]=TRUE;
413 lp.basis[lp.sum]=FALSE;
414 if (lp.names_used != FALSE)
415 lp.col_name[lp.columns] = 0;
418 lp.row_end_valid=FALSE;
420 if (lp.active != FALSE)
424 Non_zeros=lp.non_zeros;
428 public void del_column(Problem lp, int column)
430 int i, j, from_elm, to_elm, elm_in_col;
431 if(column > lp.columns || column < 1)
432 System.err.print("column out of range in del_column");
433 for(i = 1; i <= lp.rows; i++)
435 if(lp.bas[i]==lp.rows+column)
436 lp.basis_valid=FALSE;
437 else if(lp.bas[i] > lp.rows+column)
440 for(i = lp.rows+column; i < lp.sum; i++)
442 if (lp.names_used != FALSE)
443 lp.col_name[i-lp.rows] = lp.col_name[i-lp.rows+1];
444 lp.orig_upbo[i]=lp.orig_upbo[i+1];
445 lp.orig_lowbo[i]=lp.orig_lowbo[i+1];
446 lp.upbo[i]=lp.upbo[i+1];
447 lp.lowbo[i]=lp.lowbo[i+1];
448 lp.basis[i]=lp.basis[i+1];
449 lp.lower[i]=lp.lower[i+1];
450 if (lp.scaling_used != FALSE)
451 lp.scale[i]=lp.scale[i+1];
453 for(i = 0; i < lp.nr_lagrange; i++)
454 for(j = column; j <= lp.columns; j++)
455 lp.lag_row[i][j]=lp.lag_row[i][j+1];
456 to_elm=lp.col_end[column-1];
457 from_elm=lp.col_end[column];
458 elm_in_col=from_elm-to_elm;
459 for(i = from_elm; i < lp.non_zeros; i++)
461 lp.mat[to_elm]=lp.mat[i];
464 for(i = column; i < lp.columns; i++)
465 lp.col_end[i]=lp.col_end[i+1]-elm_in_col;
466 lp.non_zeros -= elm_in_col;
467 lp.row_end_valid=FALSE;
472 if (lp.active != FALSE)
476 public void bound_sum(Problem lp, int column1, int column2, float bound, short type, float[] scratch) {
477 for(int i=0; i<scratch.length; i++) scratch[i] = (float)0.0;
478 scratch[column1] = (float)1.0;
479 scratch[column2] = (float)1.0;
480 add_constraint(lp, scratch, type, bound);
481 for(int i=0; i<scratch.length; i++) scratch[i] = (float)0.0;
484 public void bound_difference(Problem lp, int column1, int column2, float bound, short type, float[] scratch) {
485 for(int i=0; i<scratch.length; i++) scratch[i] = (float)0.0;
486 scratch[column1] = (float)1.0;
487 scratch[column2] = (float)-1.0;
488 add_constraint(lp, scratch, type, bound);
489 for(int i=0; i<scratch.length; i++) scratch[i] = (float)0.0;
492 public void set_upbo(Problem lp, int column, float value)
494 if(column > lp.columns || column < 1)
495 System.err.print("column out of range");
496 if (lp.scaling_used != FALSE)
497 value /= lp.scale[lp.rows + column];
498 if(value < lp.orig_lowbo[lp.rows + column])
499 System.err.print("UpperBound must be >= lowerBound");
500 lp.eta_valid = FALSE;
501 lp.orig_upbo[lp.rows+column] = value;
504 public void set_lowbo(Problem lp, int column, float value)
506 if(column > lp.columns || column < 1)
507 System.err.print("column out of range");
508 if (lp.scaling_used != FALSE)
509 value /= lp.scale[lp.rows + column];
510 if(value > lp.orig_upbo[lp.rows + column])
511 System.err.print("UpperBound must be >= lowerBound");
512 lp.eta_valid = FALSE;
513 lp.orig_lowbo[lp.rows+column] = value;
516 public void set_rh(Problem lp, int row, float value)
518 if(row > lp.rows || row < 0)
519 System.err.print("Row out of Range");
520 if(row == 0) /* setting of RHS of OF not meaningful */
522 System.err.println("Warning: attempt to set RHS of objective function, ignored");
525 if (lp.scaling_used != FALSE)
526 if (lp.ch_sign[row] != FALSE)
527 lp.orig_rh[row] = -value * lp.scale[row];
529 lp.orig_rh[row] = value * lp.scale[row];
531 if (lp.ch_sign[row] != FALSE)
532 lp.orig_rh[row] = -value;
534 lp.orig_rh[row] = value;
535 lp.eta_valid = FALSE;
538 public void set_rh_vec(Problem lp, float[] rh)
541 if (lp.scaling_used != FALSE)
542 for(i = 1; i <= lp.rows; i++)
543 if(lp.ch_sign[i] != FALSE)
544 lp.orig_rh[i]=-rh[i]*lp.scale[i];
546 lp.orig_rh[i]=rh[i]*lp.scale[i];
548 for(i=1; i <= lp.rows; i++)
549 if(lp.ch_sign[i] != FALSE)
550 lp.orig_rh[i]=-rh[i];
556 public void set_maxim(Problem lp)
559 if(lp.maximise==FALSE)
561 for(i = 0; i < lp.non_zeros; i++)
562 if(lp.mat[i].row_nr==0)
568 if (lp.active != FALSE)
572 public void set_minim(Problem lp)
575 if(lp.maximise==TRUE)
577 for(i = 0; i < lp.non_zeros; i++)
578 if(lp.mat[i].row_nr==0)
579 lp.mat[i].value = -lp.mat[i].value;
584 if (lp.active != FALSE)
588 public void set_constr_type(Problem lp, int row, short con_type)
591 if(row > lp.rows || row < 1)
592 System.err.print("Row out of Range");
596 lp.basis_valid=FALSE;
597 if (lp.ch_sign[row] != FALSE)
599 for(i = 0; i < lp.non_zeros; i++)
600 if(lp.mat[i].row_nr==row)
603 lp.ch_sign[row]=FALSE;
604 if(lp.orig_rh[row]!=0)
608 else if(con_type==LE)
610 lp.orig_upbo[row]=lp.infinite;
611 lp.basis_valid=FALSE;
612 if (lp.ch_sign[row] != FALSE)
614 for(i = 0; i < lp.non_zeros; i++)
615 if(lp.mat[i].row_nr==row)
618 lp.ch_sign[row]=FALSE;
619 if(lp.orig_rh[row]!=0)
623 else if(con_type==GE)
625 lp.orig_upbo[row]=lp.infinite;
626 lp.basis_valid=FALSE;
627 if(lp.ch_sign[row] == FALSE)
629 for(i = 0; i < lp.non_zeros; i++)
630 if(lp.mat[i].row_nr==row)
633 lp.ch_sign[row]=TRUE;
634 if(lp.orig_rh[row]!=0)
639 System.err.print("Constraint type not (yet) implemented");
642 public float mat_elm(Problem lp, int row, int column)
646 if(row < 0 || row > lp.rows)
647 System.err.print("Row out of range in mat_elm");
648 if(column < 1 || column > lp.columns)
649 System.err.print("column out of range in mat_elm");
651 elmnr=lp.col_end[column-1];
652 while(lp.mat[elmnr].row_nr != row && elmnr < lp.col_end[column])
654 if(elmnr != lp.col_end[column])
656 value = lp.mat[elmnr].value;
657 if (lp.ch_sign[row] != FALSE)
659 if (lp.scaling_used != FALSE)
660 value /= lp.scale[row] * lp.scale[lp.rows + column];
666 public void get_row(Problem lp, int row_nr, float[] row)
670 if(row_nr < 0 || row_nr > lp.rows)
671 System.err.print("Row nr. out of range in get_row");
672 for(i = 1; i <= lp.columns; i++)
675 for(j=lp.col_end[i-1]; j < lp.col_end[i]; j++)
676 if(lp.mat[j].row_nr==row_nr)
677 row[i]=lp.mat[j].value;
678 if (lp.scaling_used != FALSE)
679 row[i] /= lp.scale[lp.rows+i] * lp.scale[row_nr];
681 if(lp.ch_sign[row_nr] != FALSE)
682 for(i=0; i <= lp.columns; i++)
687 public void get_column(Problem lp, int col_nr, float[] column)
691 if(col_nr < 1 || col_nr > lp.columns)
692 System.err.print("Col. nr. out of range in get_column");
693 for(i = 0; i <= lp.rows; i++)
695 for(i = lp.col_end[col_nr-1]; i < lp.col_end[col_nr]; i++)
696 column[lp.mat[i].row_nr]=lp.mat[i].value;
697 for(i = 0; i <= lp.rows; i++)
700 if(lp.ch_sign[i] != FALSE)
702 if (lp.scaling_used != FALSE)
703 column[i]/=(lp.scale[i] * lp.scale[lp.rows+col_nr]);
707 public void get_reduced_costs(Problem lp, float[] rc)
712 if(lp.basis_valid == FALSE)
713 System.err.print("Not a valid basis in get_reduced_costs");
715 if(lp.eta_valid == FALSE)
717 for(i = 1; i <= lp.sum; i++)
721 for(i = 1; i <= lp.columns; i++)
724 if(Basis[varnr] == FALSE)
728 for(j = Col_end[i - 1]; j < Col_end[i]; j++)
729 f += rc[Mat[j].row_nr] * Mat[j].value;
733 for(i = 1; i <= Sum; i++)
734 rc[i] = round(rc[i], Epsd);
737 short is_feasible(Problem lp, float[] values)
743 if (lp.scaling_used != FALSE)
745 for(i = lp.rows+1; i <= lp.sum; i++)
746 if( values[i - lp.rows] < lp.orig_lowbo[i]*lp.scale[i]
747 || values[i - lp.rows] > lp.orig_upbo[i]*lp.scale[i])
752 for(i = lp.rows+1; i <= lp.sum; i++)
753 if( values[i - lp.rows] < lp.orig_lowbo[i]
754 || values[i - lp.rows] > lp.orig_upbo[i])
757 this_rhs = new float[lp.rows+1];
758 for (i = 0; i <= lp.rows; i++)
761 for(i = 1; i <= lp.columns; i++)
762 for(elmnr = lp.col_end[i - 1]; elmnr < lp.col_end[i]; elmnr++)
763 this_rhs[lp.mat[elmnr].row_nr] += lp.mat[elmnr].value * values[i];
764 for(i = 1; i <= lp.rows; i++)
766 dist = lp.orig_rh[i] - this_rhs[i];
767 dist = round(dist, (float)0.001);
768 if((lp.orig_upbo[i] == 0 && dist != 0) || dist < 0)
776 short column_in_lp(Problem lp, float[] testcolumn)
782 if (lp.scaling_used != FALSE)
783 for(i = 1; i <= lp.columns; i++)
787 while(ident != FALSE && (j < lp.col_end[i]))
789 value = lp.mat[j].value;
790 if(lp.ch_sign[lp.mat[j].row_nr] != FALSE)
792 value /= lp.scale[lp.rows+i];
793 value /= lp.scale[lp.mat[j].row_nr];
794 value -= testcolumn[lp.mat[j].row_nr];
795 if(Math.abs(value) > (float)0.001) /* should be some epsilon? MB */
803 for(i = 1; i <= lp.columns; i++)
807 while(ident != FALSE && j < lp.col_end[i])
809 value = lp.mat[j].value;
810 if(lp.ch_sign[lp.mat[j].row_nr] != FALSE)
812 value -= testcolumn[lp.mat[j].row_nr];
813 if( Math.abs(value) > (float)0.001 )
823 private float minmax_to_scale(float min, float max)
827 /* should do something sensible when min or max is 0, MB */
828 if((min == 0) || (max == 0))
831 scale = (float)(1 / Math.pow(Math.E, (Math.log(min) + Math.log(max)) / 2));
835 public void unscale_columns(Problem lp)
840 for(j = 1; j <= lp.columns; j++)
841 for(i = lp.col_end[j - 1]; i < lp.col_end[j]; i++)
842 lp.mat[i].value /= lp.scale[lp.rows + j];
844 /* unscale Bounds as well */
845 for(i = lp.rows + 1; i < lp.sum; i++)
847 if(lp.orig_lowbo[i] != 0)
848 lp.orig_lowbo[i] *= lp.scale[i];
849 if(lp.orig_upbo[i] != lp.infinite)
850 lp.orig_upbo[i] *= lp.scale[i];
853 for(i=lp.rows+1; i<= lp.sum; i++)
855 lp.columns_scaled=FALSE;
859 public void unscale(Problem lp)
863 if (lp.scaling_used != FALSE)
867 for(j = 1; j <= lp.columns; j++)
868 for(i = lp.col_end[j - 1]; i < lp.col_end[j]; i++)
869 lp.mat[i].value /= lp.scale[lp.rows + j];
872 for(i = lp.rows + 1; i < lp.sum; i++)
874 if(lp.orig_lowbo[i] != 0)
875 lp.orig_lowbo[i] *= lp.scale[i];
876 if(lp.orig_upbo[i] != lp.infinite)
877 lp.orig_upbo[i] *= lp.scale[i];
880 /* unscale the matrix */
881 for(j = 1; j <= lp.columns; j++)
882 for(i = lp.col_end[j-1]; i < lp.col_end[j]; i++)
883 lp.mat[i].value /= lp.scale[lp.mat[i].row_nr];
885 /* unscale the rhs! */
886 for(i = 0; i <= lp.rows; i++)
887 lp.orig_rh[i] /= lp.scale[i];
889 lp.scaling_used=FALSE;
895 public void auto_scale(Problem lp)
897 int i, j, row_nr, IntUsed;
898 float row_max[], row_min[], scalechange[], absval;
900 if(lp.scaling_used == 0)
902 lp.scale = new float[lp.sum_alloc + 1];
903 for(i = 0; i <= lp.sum; i++)
907 row_max = new float[lp.rows + 1];
908 row_min = new float[lp.rows + 1];
909 scalechange = new float[lp.sum + 1];
911 /* initialise min and max values */
912 for(i = 0; i <= lp.rows; i++)
915 row_min[i]=lp.infinite;
918 /* calculate min and max absolute values of rows */
919 for(j = 1; j <= lp.columns; j++)
920 for(i = lp.col_end[j - 1]; i < lp.col_end[j]; i++)
922 row_nr = lp.mat[i].row_nr;
923 absval = Math.abs(lp.mat[i].value);
926 row_max[row_nr] = Math.max(row_max[row_nr], absval);
927 row_min[row_nr] = Math.min(row_min[row_nr], absval);
930 /* calculate scale factors for rows */
931 for(i = 0; i <= lp.rows; i++)
933 scalechange[i] = minmax_to_scale(row_min[i], row_max[i]);
934 lp.scale[i] *= scalechange[i];
937 /* now actually scale the matrix */
938 for(j = 1; j <= lp.columns; j++)
939 for(i = lp.col_end[j - 1]; i < lp.col_end[j]; i++)
940 lp.mat[i].value *= scalechange[lp.mat[i].row_nr];
942 /* and scale the rhs! */
943 for(i = 0; i <= lp.rows; i++)
944 lp.orig_rh[i] *= scalechange[i];
948 while(IntUsed == FALSE && i <= lp.sum)
955 float col_max, col_min;
957 /* calculate scales */
958 for(j = 1; j <= lp.columns; j++)
961 col_min = lp.infinite;
962 for(i = lp.col_end[j - 1]; i < lp.col_end[j]; i++)
964 if(lp.mat[i].value!=0)
966 col_max = Math.max(col_max, Math.abs(lp.mat[i].value));
967 col_min = Math.min(col_min, Math.abs(lp.mat[i].value));
970 scalechange[lp.rows + j] = minmax_to_scale(col_min, col_max);
971 lp.scale[lp.rows + j] *= scalechange[lp.rows + j];
975 for(j = 1; j <= lp.columns; j++)
976 for(i = lp.col_end[j - 1]; i < lp.col_end[j]; i++)
977 lp.mat[i].value *= scalechange[lp.rows + j];
979 /* scale Bounds as well */
980 for(i = lp.rows + 1; i < lp.sum; i++)
982 if(lp.orig_lowbo[i] != 0)
983 lp.orig_lowbo[i] /= scalechange[i];
984 if(lp.orig_upbo[i] != lp.infinite)
985 lp.orig_upbo[i] /= scalechange[i];
987 lp.columns_scaled=TRUE;
989 lp.scaling_used=TRUE;
993 public void reset_basis(Problem lp) { lp.basis_valid=FALSE; }
995 /* Globals used by solver */
1002 void set_globals(Problem lp)
1008 columns = lp.columns;
1009 Sum = Rows + columns;
1010 Non_zeros = lp.non_zeros;
1013 Col_end = lp.col_end;
1014 Row_end = lp.row_end;
1017 Orig_rh = lp.orig_rh;
1018 Orig_upbo = lp.orig_upbo;
1019 Orig_lowbo = lp.orig_lowbo;
1025 Eta_alloc = lp.eta_alloc;
1026 Eta_size = lp.eta_size;
1027 Num_inv = lp.num_inv;
1028 Eta_value = lp.eta_value;
1029 Eta_row_nr = lp.eta_row_nr;
1030 Eta_col_end = lp.eta_col_end;
1031 Solution = lp.solution;
1032 Best_solution = lp.best_solution;
1033 Infinite = lp.infinite;
1034 Epsilon = lp.epsilon;
1043 Maximise = lp.maximise;
1044 Floor_first = lp.floor_first;
1047 // System.out.println("Sum = " + Sum);
1048 } // end of set_global
1050 private void ftran(int start,
1057 for(i = start; i <= end; i++)
1059 k = Eta_col_end[i] - 1;
1063 for(j = Eta_col_end[i - 1]; j < k; j++)
1064 pcol[Eta_row_nr[j]] += theta * Eta_value[j]; /* cpu expensive line */
1065 pcol[r] *= Eta_value[k];
1067 /* round small values to zero */
1068 for(i = 0; i <= Rows; i++)
1069 round(pcol[i], Epsel);
1072 private void btran(float[] row)
1077 for(i = Eta_size; i >= 1; i--)
1080 k = Eta_col_end[i] - 1;
1081 for(j = Eta_col_end[i - 1]; j <= k; j++)
1082 f += row[Eta_row_nr[j]] * Eta_value[j];
1083 f = round(f, Epsel);
1084 row[Eta_row_nr[k]] = f;
1089 static short Isvalid(Problem lp)
1091 int i, j, rownum[], colnum[];
1094 if(lp.row_end_valid == FALSE)
1096 num = new int[lp.rows + 1];
1097 rownum = new int[lp.rows + 1];
1098 for(i = 0; i <= lp.rows; i++)
1103 for(i = 0; i < lp.non_zeros; i++)
1104 rownum[lp.mat[i].row_nr]++;
1106 for(i = 1; i <= lp.rows; i++)
1107 lp.row_end[i] = lp.row_end[i - 1] + rownum[i];
1108 for(i = 1; i <= lp.columns; i++)
1109 for(j = lp.col_end[i - 1]; j < lp.col_end[i]; j++)
1111 row_nr = lp.mat[j].row_nr;
1115 lp.col_no[lp.row_end[row_nr - 1] + num[row_nr]] = i;
1118 lp.row_end_valid = TRUE;
1120 if(lp.valid != FALSE)
1122 rownum = new int[lp.rows + 1];
1123 for (i = 0; i <= lp.rows; i++)
1125 colnum = new int[lp.columns + 1];
1126 for (i = 0; i <= lp.columns; i++)
1128 for(i = 1 ; i <= lp.columns; i++)
1129 for(j = lp.col_end[i - 1]; j < lp.col_end[i]; j++)
1132 rownum[lp.mat[j].row_nr]++;
1134 for(i = 1; i <= lp.columns; i++)
1136 if (lp.names_used != FALSE)
1137 System.err.print("Warning: Variable " + lp.col_name[i] +
1138 " not used in any constraints\n");
1140 System.err.print("Warning: Variable " + i + " not used in any constaints\n");
1145 private void resize_eta()
1148 float[] db_ptr = Eta_value;
1149 Eta_value = new float[Eta_alloc];
1150 System.arraycopy(db_ptr, 0, Eta_value, 0, db_ptr.length);
1151 Lp.eta_value = Eta_value;
1153 int[] int_ptr = Eta_row_nr;
1154 Eta_row_nr = new int[Eta_alloc];
1155 System.arraycopy(int_ptr, 0, Eta_row_nr, 0, int_ptr.length);
1156 Lp.eta_row_nr = Eta_row_nr;
1160 private void condensecol(int row_nr,
1165 elnr = Eta_col_end[Eta_size];
1167 if(elnr + Rows + 2 > Eta_alloc) /* maximum local growth of Eta */
1170 for(i = 0; i <= Rows; i++)
1171 if(i != row_nr && pcol[i] != 0)
1173 Eta_row_nr[elnr] = i;
1174 Eta_value[elnr] = pcol[i];
1177 Eta_row_nr[elnr] = row_nr;
1178 Eta_value[elnr] = pcol[row_nr];
1180 Eta_col_end[Eta_size + 1] = elnr;
1184 private void addetacol()
1189 j = Eta_col_end[Eta_size];
1191 k = Eta_col_end[Eta_size];
1192 theta = 1 / (float) Eta_value[k - 1];
1193 Eta_value[k - 1] = theta;
1194 for(i = j; i < k - 1; i++)
1195 Eta_value[i] *= -theta;
1196 JustInverted = FALSE;
1199 private void setpivcol(short lower,
1210 for(i = 0; i <= Rows; i++)
1214 colnr = varin - Rows;
1215 for(i = Col_end[colnr - 1]; i < Col_end[colnr]; i++)
1216 pcol[Mat[i].row_nr] = Mat[i].value * f;
1217 pcol[0] -= Extrad * f;
1224 ftran(1, Eta_size, pcol);
1228 private void minoriteration(int colnr,
1231 int i, j, k, wk, varin, varout, elnr;
1232 float piv = 0, theta;
1234 varin = colnr + Rows;
1235 elnr = Eta_col_end[Eta_size];
1240 Eta_row_nr[elnr] = 0;
1241 Eta_value[elnr] = -Extrad;
1244 for(j = Col_end[colnr - 1] ; j < Col_end[colnr]; j++)
1247 if(k == 0 && Extrad != 0)
1248 Eta_value[Eta_col_end[Eta_size -1]] += Mat[j].value;
1249 else if(k != row_nr)
1251 Eta_row_nr[elnr] = k;
1252 Eta_value[elnr] = Mat[j].value;
1258 Eta_row_nr[elnr] = row_nr;
1259 Eta_value[elnr] = 1 / (float) piv;
1261 theta = Rhs[row_nr] / (float) piv;
1262 Rhs[row_nr] = theta;
1263 for(i = wk; i < elnr - 1; i++)
1264 Rhs[Eta_row_nr[i]] -= theta * Eta_value[i];
1265 varout = Bas[row_nr];
1266 Bas[row_nr] = varin;
1267 Basis[varout] = FALSE;
1268 Basis[varin] = TRUE;
1269 for(i = wk; i < elnr - 1; i++)
1270 Eta_value[i] /= - (float) piv;
1271 Eta_col_end[Eta_size] = elnr;
1272 } /* minoriteration */
1274 private void rhsmincol(float theta,
1278 int i, j, k, varout;
1281 if(row_nr > Rows + 1)
1283 System.err.print("Error: rhsmincol called with row_nr: " +
1284 row_nr + ", rows: " + Rows + "\n");
1285 System.err.print("This indicates numerical instability\n");
1288 j = Eta_col_end[Eta_size];
1289 k = Eta_col_end[Eta_size + 1];
1290 for(i = j; i < k; i++)
1292 f = Rhs[Eta_row_nr[i]] - theta * Eta_value[i];
1294 Rhs[Eta_row_nr[i]] = f;
1296 Rhs[row_nr] = theta;
1297 varout = Bas[row_nr];
1298 Bas[row_nr] = varin;
1299 Basis[varout] = FALSE;
1300 Basis[varin] = TRUE;
1306 int i, j, v, wk, numit, varnr, row_nr, colnr, varin;
1311 int[] rownum, col, row;
1314 rownum = new int[Rows + 1];
1315 for (i = 0; i <= Rows; i++)
1317 col = new int[Rows + 1];
1318 for (i = 0; i <= Rows; i++)
1320 row = new int[Rows + 1];
1321 for (i = 0; i <= Rows; i++)
1323 pcol = new float[Rows + 1];
1324 for (i = 0; i <= Rows; i++)
1326 frow = new short[Rows + 1];
1327 for(i = 0; i <= Rows; i++)
1329 fcol = new short[columns + 1];
1330 for(i = 0; i < columns; i++)
1332 colnum = new int[columns + 1];
1333 for(i = 0; i <= columns; i++)
1336 for(i = 0; i <= Rows; i++)
1338 fcol[Bas[i] - Rows - 1] = TRUE;
1340 frow[Bas[i]] = FALSE;
1342 for(i = 1; i <= Rows; i++)
1343 if(frow[i] != FALSE)
1344 for(j = Row_end[i - 1] + 1; j <= Row_end[i]; j++)
1347 if(fcol[wk - 1] != FALSE)
1353 for(i = 1; i <= Rows; i++)
1355 for(i = 1; i <= Rows; i++)
1357 for(i = 1; i <= columns; i++)
1358 Basis[i + Rows] = FALSE;
1360 for(i = 0; i <= Rows; i++)
1363 for(i = 1; i <= columns; i++)
1366 if(Lower[varnr] == FALSE)
1368 theta = Upbo[varnr];
1369 for(j = Col_end[i - 1]; j < Col_end[i]; j++)
1370 Rhs[Mat[j].row_nr] -= theta * Mat[j].value;
1373 for(i = 1; i <= Rows; i++)
1374 if(Lower[i] == FALSE)
1387 if(rownum[row_nr - 1] == 1)
1388 if(frow[row_nr] != FALSE)
1391 j = Row_end[row_nr - 1] + 1;
1392 while(fcol[Col_no[j] - 1] == FALSE)
1395 fcol[colnr - 1] = FALSE;
1397 for(j = Col_end[colnr - 1]; j < Col_end[colnr]; j++)
1398 if(frow[Mat[j].row_nr] != FALSE)
1399 rownum[Mat[j].row_nr - 1]--;
1400 frow[row_nr] = FALSE;
1401 minoriteration(colnr, row_nr);
1412 if(colnum[colnr] == 1)
1413 if(fcol[colnr - 1] != FALSE)
1416 j = Col_end[colnr - 1] + 1;
1417 while(frow[Mat[j - 1].row_nr] == FALSE)
1419 row_nr = Mat[j - 1].row_nr;
1420 frow[row_nr] = FALSE;
1421 rownum[row_nr - 1] = 0;
1422 for(j = Row_end[row_nr - 1] + 1; j <= Row_end[row_nr]; j++)
1423 if(fcol[Col_no[j] - 1] != FALSE)
1424 colnum[Col_no[j]]--;
1425 fcol[colnr - 1] = FALSE;
1427 col[numit - 1] = colnr;
1428 row[numit - 1] = row_nr;
1431 for(j = 1; j <= columns; j++)
1432 if(fcol[j - 1] != FALSE)
1434 fcol[j - 1] = FALSE;
1435 setpivcol(Lower[Rows + j], j + Rows, pcol);
1437 while((frow[row_nr] == FALSE || pcol[row_nr] == FALSE)
1439 row_nr++; /* this sometimes sets row_nr to Rows + 1 and makes
1440 rhsmincol crash. Solved in 2.0? MB */
1441 if(row_nr == Rows + 1)
1442 System.err.print("Inverting failed");
1443 frow[row_nr] = FALSE;
1444 condensecol(row_nr, pcol);
1445 theta = Rhs[row_nr] / (float) pcol[row_nr];
1446 rhsmincol(theta, row_nr, Rows + j);
1449 for(i = numit - 1; i >= 0; i--)
1453 varin = colnr + Rows;
1454 for(j = 0; j <= Rows; j++)
1456 for(j = Col_end[colnr - 1]; j < Col_end[colnr]; j++)
1457 pcol[Mat[j].row_nr] = Mat[j].value;
1459 condensecol(row_nr, pcol);
1460 theta = Rhs[row_nr] / (float) pcol[row_nr];
1461 rhsmincol(theta, row_nr, varin);
1464 for(i = 1; i <= Rows; i++)
1465 Rhs[i] = round(Rhs[i], Epsb);
1466 JustInverted = TRUE;
1470 private short colprim(Ref colnr,
1481 for(i = 1; i <= Sum; i++)
1485 for(i = 1; i <= columns; i++)
1488 if(Basis[varnr] == FALSE)
1492 for(j = Col_end[i - 1]; j < Col_end[i]; j++)
1493 f += drow[Mat[j].row_nr] * Mat[j].value;
1497 for(i = 1; i <= Sum; i++)
1498 drow[i] = round(drow[i], Epsd);
1501 System.out.println("dpiv = " + dpiv);
1502 System.out.println("drow[] at colprim");
1503 for(i = 1; i <= Sum; i++) // DEBUG
1505 System.out.print(drow[i] + " ");
1507 System.out.println();
1509 for(i = 1; i <= Sum; i++)
1510 if(Basis[i] == FALSE)
1513 if(Lower[i] != FALSE)
1523 if(Lp.trace != FALSE)
1525 System.err.print("col_prim:" + colnr.value + ", reduced cost: " + dpiv + "\n");
1527 System.err.print("col_prim: no negative reduced costs found, optimality!\n");
1528 if(colnr.value == 0)
1534 return(colnr.value > 0 ? (short)1 : (short)0);
1537 private short rowprim(int colnr,
1546 theta.value = Infinite;
1547 for(i = 1; i <= Rows; i++)
1550 if(Math.abs(f) < TREJ)
1554 quot = 2 * Infinite;
1556 quot = Rhs[i] / (float) f;
1558 if(Upbo[Bas[i]] < Infinite)
1559 quot = (Rhs[i] - Upbo[Bas[i]]) / (float) f;
1561 if(quot < theta.value)
1568 if(row_nr.value == 0)
1569 for(i = 1; i <= Rows; i++)
1574 quot = 2 * Infinite;
1576 quot = Rhs[i] / (float) f;
1578 if(Upbo[Bas[i]] < Infinite)
1579 quot = (Rhs[i] - Upbo[Bas[i]]) / (float) f;
1580 quot = round(quot, Epsel);
1581 if(quot < theta.value)
1591 System.err.println("Warning: Numerical instability, qout = " + theta.value);
1592 System.err.println("pcol[" + row_nr.value + "] = " + f + ", rhs[" +
1593 row_nr.value + "] = " + Rhs[(int)row_nr.value] +
1594 " , upbo = " + Upbo[Bas[(int)row_nr.value]]);
1596 if(row_nr.value == 0)
1598 if(Upbo[colnr] == Infinite)
1607 while(pcol[i] >= 0 && i <= Rows)
1609 if(i > Rows) /* empty column with upperBound! */
1611 Lower[colnr] = FALSE;
1612 Rhs[0] += Upbo[colnr]*pcol[0];
1622 if(row_nr.value > 0)
1624 if(Lp.trace != FALSE)
1625 System.out.println("row_prim:" + row_nr.value + ", pivot element:" +
1626 pcol[(int)row_nr.value]);
1628 return((row_nr.value > 0) ? (short)1 : (short)0);
1631 private short rowdual(Ref row_nr)
1641 while(i < Rows && artifs == FALSE)
1645 if(f == 0 && (Rhs[i] != 0))
1652 if(Rhs[i] < f - Rhs[i])
1664 if(Lp.trace != FALSE)
1666 if(row_nr.value > 0)
1668 System.out.println("row_dual:" + row_nr.value +
1669 ", rhs of selected row: "
1670 + Rhs[(int)row_nr.value]);
1671 if(Upbo[Bas[(int)row_nr.value]] < Infinite)
1672 System.out.println(" upper Bound of basis variable: " +
1673 Upbo[Bas[(int)row_nr.value]]);
1676 System.out.print("row_dual: no infeasibilities found\n");
1679 return(row_nr.value > 0 ? (short)1 : (short)0);
1682 private short coldual(int row_nr,
1689 float theta, quot, pivot, d, f, g;
1694 for(i = 0; i <= Rows; i++)
1701 for(i = Eta_size; i >= 1; i--)
1705 r = Eta_row_nr[Eta_col_end[i] - 1];
1706 for(j = Eta_col_end[i - 1]; j < Eta_col_end[i]; j++)
1708 /* this is where the program consumes most cpu time */
1709 f += prow[Eta_row_nr[j]] * Eta_value[j];
1710 d += drow[Eta_row_nr[j]] * Eta_value[j];
1712 f = round(f, Epsel);
1714 d = round(d, Epsel);
1717 for(i = 1; i <= columns; i++)
1720 if(Basis[varnr] == FALSE)
1722 d = - Extrad * drow[0];
1724 for(j = Col_end[i - 1]; j < Col_end[i]; j++)
1726 d = d + drow[Mat[j].row_nr] * Mat[j].value;
1727 f = f + prow[Mat[j].row_nr] * Mat[j].value;
1733 for(i = 0; i <= Sum; i++)
1735 prow[i] = round(prow[i], Epsel);
1736 drow[i] = round(drow[i], Epsd);
1739 if(Rhs[row_nr] > Upbo[Bas[row_nr]])
1746 for(i = 1; i <= Sum; i++)
1748 if(Lower[i] != FALSE)
1752 if((d < 0) && (Basis[i] == FALSE) && (Upbo[i] > 0))
1754 if(Lower[i] == FALSE)
1755 quot = -drow[i] / (float) d;
1757 quot = drow[i] / (float) d;
1764 else if((quot == theta) && (Math.abs(d) > Math.abs(pivot)))
1771 if(Lp.trace != FALSE)
1772 System.out.println("col_dual:" + colnr.value + ", pivot element: " +
1773 prow[(int)colnr.value]);
1778 return(colnr.value > 0 ? (short)1 : (short)0);
1781 private void iteration(int row_nr,
1795 minit.value = theta.value > (up + Epsb) ? 1 : 0;
1796 if(minit.value != 0)
1799 low.value = low.value == 0 ? 1 : 0;
1801 k = Eta_col_end[Eta_size + 1];
1802 pivot = Eta_value[k - 1];
1803 for(i = Eta_col_end[Eta_size]; i < k; i++)
1805 f = Rhs[Eta_row_nr[i]] - theta.value * Eta_value[i];
1807 Rhs[Eta_row_nr[i]] = f;
1809 if(minit.value == 0)
1811 Rhs[row_nr] = theta.value;
1812 varout = Bas[row_nr];
1813 Bas[row_nr] = varin;
1814 Basis[varout] = FALSE;
1815 Basis[varin] = TRUE;
1816 if(primal != FALSE && pivot < 0)
1817 Lower[varout] = FALSE;
1818 if(low.value == 0 && up < Infinite)
1821 Rhs[row_nr] = up - Rhs[row_nr];
1822 for(i = Eta_col_end[Eta_size]; i < k; i++)
1823 Eta_value[i] = -Eta_value[i];
1828 if(Lp.trace != FALSE)
1830 System.out.print("Theta = " + theta.value + " ");
1831 if(minit.value != 0)
1833 if(Lower[varin] == FALSE)
1834 System.out.print("Iteration:" + Lp.iter +
1835 ", variable" + varin + " changed from 0 to its upper Bound of "
1836 + Upbo[varin] + "\n");
1838 System.out.print("Iteration:" + Lp.iter + ", variable" + varin +
1839 " changed its upper Bound of " + Upbo[varin] + " to 0\n");
1842 System.out.print("Iteration:" + Lp.iter + ", variable" + varin +
1843 " entered basis at:" + Rhs[row_nr] + "\n");
1847 for(i = 1; i <= Rows; i++)
1851 if(Rhs[i] > Upbo[Bas[i]])
1852 f += Rhs[i] - Upbo[Bas[i]];
1853 System.out.println("feasibility gap of this basis:" + (float)f);
1856 System.out.println("objective function value of this feasible basis: " + Rhs[0]);
1861 private int solvelp()
1864 float f = 0, theta = 0;
1866 float[] drow, prow, Pcol;
1872 Ref ref1, ref2, ref3;
1877 drow = new float[Sum + 1];
1878 prow = new float[Sum + 1];
1879 Pcol = new float[Rows + 1];
1880 for (i = 0; i <= Sum; i++) {
1884 for (i = 0; i <= Rows; i++)
1895 while(i != Rows && primal != FALSE)
1898 primal = (Rhs[i] >= 0 && Rhs[i] <= Upbo[Bas[i]]) ?
1901 if(Lp.trace != FALSE)
1904 System.out.print("Start at feasible basis\n");
1906 System.out.print("Start at infeasible basis\n");
1911 for(i = 1; i <= Rows; i++)
1914 for(i = 1; i <= columns; i++)
1918 for(j = Col_end[i - 1]; j < Col_end[i]; j++)
1919 if(drow[Mat[j].row_nr] != 0)
1920 drow[varnr] += drow[Mat[j].row_nr] * Mat[j].value;
1921 if(drow[varnr] < Extrad)
1922 Extrad = drow[varnr];
1927 if(Lp.trace != FALSE)
1928 System.out.println("Extrad = " + Extrad);
1931 while(Status == RUNNING)
1936 construct_solution(Solution);
1940 flag = colprim(ref1, minit, drow);
1941 colnr = (int)ref1.value;
1944 setpivcol(Lower[colnr], colnr, Pcol);
1945 ref1.value = row_nr;
1947 flag = rowprim(colnr, ref1, ref2, Pcol);
1948 row_nr = (int)ref1.value;
1951 condensecol(row_nr, Pcol);
1955 else /* not primal */
1957 if(minit == FALSE) {
1958 ref1.value = row_nr;
1959 flag = rowdual(ref1);
1960 row_nr = (int)ref1.value;
1965 flag = coldual(row_nr, ref1, minit, prow, drow);
1966 colnr = (int)ref1.value;
1969 setpivcol(Lower[colnr], colnr, Pcol);
1970 /* getting div by zero here ... MB */
1971 if(Pcol[row_nr] == 0)
1973 System.err.println("An attempt was made to divide by zero (Pcol[" +
1975 System.err.println("This indicates numerical instability");
1977 if(JustInverted == FALSE)
1979 System.out.println("Reinverting Eta");
1984 System.out.println("Can't reinvert, failure");
1990 condensecol(row_nr, Pcol);
1991 f = Rhs[row_nr] - Upbo[Bas[row_nr]];
1994 theta = f / (float) Pcol[row_nr];
1995 if(theta <= Upbo[colnr])
1996 Lower[Bas[row_nr]] =
1997 (Lower[Bas[row_nr]] == FALSE)?
2001 theta = Rhs[row_nr] / (float) Pcol[row_nr];
2005 Status = INFEASIBLE;
2015 if(Doiter != FALSE) {
2018 ref3.value = Lower[colnr];
2019 iteration(row_nr, colnr, ref1, Upbo[colnr], ref2, ref3, primal, Pcol);
2021 minit = (short)ref2.value;
2022 Lower[colnr] = (short)ref3.value;
2024 if(Num_inv >= Lp.max_num_inv)
2026 if(DoInvert != FALSE)
2032 Lp.total_iter += Lp.iter;
2038 private short is_int(float value)
2042 tmp = (float)(value - Math.floor(value));
2045 if(tmp > (1 - Epsilon))
2050 private void construct_solution(float[] sol)
2055 /* zero all results of rows */
2056 for (i = 0; i <= Rows; i++)
2059 if (Lp.scaling_used != FALSE)
2061 for(i = Rows + 1; i <= Sum; i++)
2062 sol[i] = Lowbo[i] * Lp.scale[i];
2063 for(i = 1; i <= Rows; i++)
2067 sol[basi] += Rhs[i] * Lp.scale[basi];
2069 for(i = Rows + 1; i <= Sum; i++)
2070 if(Basis[i] == FALSE && Lower[i] == FALSE)
2071 sol[i] += Upbo[i] * Lp.scale[i];
2073 for(j = 1; j <= columns; j++)
2077 for(i = Col_end[j - 1]; i < Col_end[j]; i++)
2078 sol[Mat[i].row_nr] += (f / Lp.scale[Rows+j])
2079 * (Mat[i].value / Lp.scale[Mat[i].row_nr]);
2082 for(i = 0; i <= Rows; i++)
2084 if(Math.abs(sol[i]) < Epsb)
2087 if(Lp.ch_sign[i] != FALSE)
2093 for(i = Rows + 1; i <= Sum; i++)
2095 for(i = 1; i <= Rows; i++)
2099 sol[basi] += Rhs[i];
2101 for(i = Rows + 1; i <= Sum; i++)
2102 if(Basis[i] == FALSE && Lower[i] == FALSE)
2104 for(j = 1; j <= columns; j++)
2108 for(i = Col_end[j - 1]; i < Col_end[j]; i++)
2109 sol[Mat[i].row_nr] += f * Mat[i].value;
2112 for(i = 0; i <= Rows; i++)
2114 if(Math.abs(sol[i]) < Epsb)
2117 if(Lp.ch_sign[i] != FALSE)
2121 } /* construct_solution */
2123 private void calculate_duals()
2128 for(i = 1; i <= Rows; i++)
2132 if (Lp.scaling_used != FALSE)
2133 for(i = 1; i <= Rows; i++)
2134 Lp.duals[i] *= Lp.scale[i]/Lp.scale[0];
2136 /* the dual values are the reduced costs of the slacks */
2137 /* When the slack is at its upper Bound, change the sign. Can this happen? */
2138 for(i = 1; i <= Rows; i++)
2140 if(Lp.basis[i] != FALSE)
2142 else if( Lp.ch_sign[0] == Lp.ch_sign[i])
2143 Lp.duals[i] = -Lp.duals[i];
2147 private int milpsolve(float[] upbo,
2153 int i, j, failure, notint, is_worse;
2154 float theta, tmpfloat;
2155 Random rdm = new Random();
2158 if(Break_bb != FALSE)
2162 if(Level > Lp.max_level)
2163 Lp.max_level = Level;
2164 /* make fresh copies of upbo, lowbo, rh as solving changes them */
2165 System.arraycopy(upbo, 0, Upbo, 0, Sum + 1);
2166 System.arraycopy(lowbo, 0, Lowbo, 0, Sum + 1);
2167 System.arraycopy(sbasis, 0, Basis, 0, Sum + 1);
2168 System.arraycopy(slower, 0, Lower, 0, Sum + 1);
2169 System.arraycopy(sbas, 0, Bas, 0, Rows + 1);
2170 System.arraycopy(Orig_rh, 0, Rh, 0, Rows + 1);
2172 if(Lp.anti_degen != FALSE)
2174 for(i = 1; i <= columns; i++)
2176 tmpfloat = rdm.nextFloat()*(float)0.001;
2178 Lowbo[i + Rows] -= tmpfloat;
2179 tmpfloat = rdm.nextFloat()*(float)0.001;
2181 Upbo[i + Rows] += tmpfloat;
2183 Lp.eta_valid = FALSE;
2186 if(Lp.eta_valid == FALSE)
2188 for(i = 1; i <= columns; i++)
2189 if(Lowbo[Rows + i] != 0)
2191 theta = Lowbo[ Rows + i];
2192 if(Upbo[Rows + i]<Infinite)
2193 Upbo[Rows + i] -= theta;
2194 for(j = Col_end[i - 1]; j < Col_end[i]; j++)
2195 Rh[Mat[j].row_nr] -= theta * Mat[j].value;
2198 Lp.eta_valid = TRUE;
2201 failure = solvelp();
2203 if(Lp.anti_degen != FALSE)
2205 System.arraycopy(upbo, 0, Upbo, 0, Sum + 1);
2206 System.arraycopy(lowbo, 0, Lowbo, 0, Sum + 1);
2207 System.arraycopy(Orig_rh, 0, Rh, 0, Rows + 1);
2209 for(i = 1; i <= columns; i++)
2210 if(Lowbo[Rows + i] != 0)
2212 theta = Lowbo[ Rows + i];
2213 if(Upbo[Rows + i]<Infinite)
2214 Upbo[Rows + i] -= theta;
2215 for(j = Col_end[i - 1]; j < Col_end[i]; j++)
2216 Rh[Mat[j].row_nr] -= theta * Mat[j].value;
2219 Lp.eta_valid = TRUE;
2220 failure = solvelp();
2223 if(failure == INFEASIBLE && Lp.verbose != FALSE)
2224 System.out.print("level" + Level + " INF\n");
2226 if(failure == OPTIMAL) /* there is a solution */
2228 construct_solution(Solution);
2230 /* if this solution is worse than the best sofar, this branch must die */
2231 if(Maximise != FALSE)
2232 is_worse = (Solution[0] <= Best_solution[0]) ? 1:0;
2233 else /* minimising! */
2234 is_worse = (Solution[0] >= Best_solution[0]) ? 1:0;
2236 if(is_worse != FALSE)
2238 if(Lp.verbose != FALSE)
2239 System.out.println("level" + Level + " OPT NOB value " + Solution[0] +
2240 " Bound " + Best_solution[0]);
2245 /* check if solution contains enough ints */
2246 if(Lp.bb_rule == FIRST_NI)
2250 while(i <= Sum && notint == 0)
2255 if(Lp.bb_rule == RAND_NI)
2257 int nr_not_int, select_not_int;
2259 for(i = Rows + 1; i <= Sum; i++)
2264 select_not_int=(rdm.nextInt() % nr_not_int) + 1;
2266 while(select_not_int > 0)
2274 if(Lp.verbose == TRUE)
2276 System.out.println("level " + Level + " OPT value " + Solution[0]);
2278 System.out.println("level " + Level + " OPT INT value " + Solution[0]);
2280 if(notint != FALSE) /* there is at least one value not yet int */
2282 /* set up two new problems */
2283 float[] new_upbo, new_lowbo;
2285 short[] new_lower, new_basis;
2289 /* allocate room for them */
2290 new_upbo = new float[Sum + 1];
2291 new_lowbo = new float[Sum + 1];
2292 new_lower = new short[Sum + 1];
2293 new_basis = new short[Sum + 1];
2294 new_bas = new int[Rows + 1];
2295 System.arraycopy(upbo, 0, new_upbo, 0, Sum + 1);
2296 System.arraycopy(lowbo, 0, new_lowbo, 0, Sum + 1);
2297 System.arraycopy(Lower, 0, new_lower, 0, Sum + 1);
2298 System.arraycopy(Basis, 0, new_basis, 0, Sum + 1);
2299 System.arraycopy(Bas, 0, new_bas, 0, Rows +1);
2301 if(Floor_first != FALSE)
2303 new_bound = (float)(Math.ceil(Solution[notint]) - 1);
2304 /* this Bound might conflict */
2305 if(new_bound < lowbo[notint])
2309 else /* Bound feasible */
2311 new_upbo[notint] = new_bound;
2312 Lp.eta_valid = FALSE;
2313 resone = milpsolve(new_upbo, lowbo, new_basis, new_lower,
2315 Lp.eta_valid = FALSE;
2318 if(new_bound > upbo[notint])
2322 else /* Bound feasible */
2324 new_lowbo[notint] = new_bound;
2325 Lp.eta_valid = FALSE;
2326 restwo = milpsolve(upbo, new_lowbo, new_basis, new_lower,
2328 Lp.eta_valid = FALSE;
2331 else /* take ceiling first */
2333 new_bound = (float)Math.ceil(Solution[notint]);
2334 /* this Bound might conflict */
2335 if(new_bound > upbo[notint])
2339 else /* Bound feasible */
2341 new_lowbo[notint] = new_bound;
2342 Lp.eta_valid = FALSE;
2343 resone = milpsolve(upbo, new_lowbo, new_basis, new_lower,
2345 Lp.eta_valid = FALSE;
2348 if(new_bound < lowbo[notint])
2352 else /* Bound feasible */
2354 new_upbo[notint] = new_bound;
2355 Lp.eta_valid = FALSE;
2356 restwo = milpsolve(new_upbo, lowbo, new_basis, new_lower,
2358 Lp.eta_valid = FALSE;
2361 if(resone != FALSE && restwo != FALSE)
2362 /* both failed and must have been infeasible */
2363 failure = INFEASIBLE;
2368 else /* all required values are int */
2370 if(Maximise != FALSE)
2371 is_worse = (Solution[0] < Best_solution[0]) ? 1:0;
2373 is_worse = (Solution[0] > Best_solution[0]) ? 1:0;
2375 if(is_worse == FALSE) /* Current solution better */
2377 System.arraycopy(Solution, 0, Best_solution, 0, Sum + 1);
2379 if(Lp.break_at_int != FALSE)
2381 if(Maximise != FALSE && (Best_solution[0] > Lp.break_value))
2383 if(Maximise == FALSE && (Best_solution[0] < Lp.break_value))
2390 /* failure can have the values OPTIMAL, UNBOUNDED and INFEASIBLE. */
2395 public int solve(Problem lp)
2399 if(lp.active == FALSE)
2406 if(Isvalid(lp) != FALSE)
2408 if(Maximise != FALSE && lp.obj_bound == Infinite)
2409 Best_solution[0]=-Infinite;
2410 else if(Maximise == FALSE && lp.obj_bound==-Infinite)
2411 Best_solution[0] = Infinite;
2413 Best_solution[0] = lp.obj_bound;
2417 if(lp.basis_valid == FALSE)
2419 for(i = 0; i <= lp.rows; i++)
2424 for(i = lp.rows+1; i <= lp.sum; i++)
2425 lp.basis[i] = FALSE;
2426 for(i = 0; i <= lp.sum; i++)
2428 lp.basis_valid = TRUE;
2431 lp.eta_valid = FALSE;
2433 result = milpsolve(Orig_upbo, Orig_lowbo, Basis, Lower, Bas);
2434 lp.eta_size = Eta_size;
2435 lp.eta_alloc = Eta_alloc;
2436 lp.num_inv = Num_inv;
2441 /* if we get here, Isvalid(lp) failed. I suggest we return FAILURE */
2445 public int lag_solve(Problem lp, float start_bound, int num_iter, short verbose)
2447 int i, j, result, citer;
2448 short status, OrigFeas, AnyFeas, same_basis;
2449 float[] OrigObj, ModObj, SubGrad, BestFeasSol;
2450 float Zub, Zlb, Ztmp, pie;
2451 float rhsmod, Step, SqrsumSubGrad;
2456 OrigObj = new float[lp.columns + 1];
2457 ModObj = new float[lp.columns + 1];
2458 for (i = 0; i <= lp.columns; i++)
2460 SubGrad = new float[lp.nr_lagrange];
2461 for (i = 0; i < lp.nr_lagrange; i++)
2463 BestFeasSol = new float[lp.sum + 1];
2464 for (i = 0; i <= lp.sum; i++)
2466 old_bas = new int[lp.rows + 1];
2467 System.arraycopy(lp.bas, 0, old_bas, 0, lp.rows + 1);
2468 old_lower = new short[lp.sum + 1];
2469 System.arraycopy(lp.lower, 0, old_lower, 0, lp.sum + 1);
2471 get_row(lp, 0, OrigObj);
2475 if(lp.maximise != FALSE)
2482 Zlb = -DEF_INFINITE;
2491 for(i = 0 ; i < lp.nr_lagrange; i++)
2494 while(status == RUNNING)
2498 for(i = 1; i <= lp.columns; i++)
2500 ModObj[i] = OrigObj[i];
2501 for(j = 0; j < lp.nr_lagrange; j++)
2503 if(lp.maximise != FALSE)
2504 ModObj[i] -= lp.lambda[j] * lp.lag_row[j][i];
2506 ModObj[i] += lp.lambda[j] * lp.lag_row[j][i];
2509 for(i = 1; i <= lp.columns; i++)
2511 set_mat(lp, 0, i, ModObj[i]);
2512 /* fSystem.out.print(stderr, "%f ", ModObj[i]); */
2515 for(i = 0; i < lp.nr_lagrange; i++)
2516 if(lp.maximise != FALSE)
2517 rhsmod += lp.lambda[i] * lp.lag_rhs[i];
2519 rhsmod -= lp.lambda[i] * lp.lag_rhs[i];
2521 if(verbose != FALSE)
2523 System.out.println("Zub: " + Zub + " Zlb: " + Zlb + " Step: " + Step +
2524 " pie: " + pie + " Feas " + OrigFeas);
2525 for(i = 0; i < lp.nr_lagrange; i++)
2526 System.out.println(i + " SubGrad " + SubGrad[i] + " lambda " + lp.lambda[i]);
2534 while(same_basis != FALSE && i < lp.rows)
2536 same_basis = (old_bas[i] == lp.bas[i])? (short)1: (short)0;
2540 while(same_basis != FALSE && i < lp.sum)
2542 same_basis=(old_lower[i] == lp.lower[i])? (short)1:(short)0;
2545 if(same_basis == FALSE)
2547 System.arraycopy(lp.lower, 0, old_lower, 0, lp.sum+1);
2548 System.arraycopy(lp.bas, 0, old_bas, 0, lp.rows+1);
2552 if(verbose != FALSE)
2553 System.out.println("result: " + result + " same basis: " + same_basis);
2555 if(result == UNBOUNDED)
2557 for(i = 1; i <= lp.columns; i++)
2558 System.out.print(ModObj[i] + " ");
2562 if(result == FAILURE)
2565 if(result == INFEASIBLE)
2566 status = INFEASIBLE;
2569 for(i = 0; i < lp.nr_lagrange; i++)
2571 SubGrad[i]= -lp.lag_rhs[i];
2572 for(j = 1; j <= lp.columns; j++)
2573 SubGrad[i] += lp.best_solution[lp.rows + j] * lp.lag_row[i][j];
2574 SqrsumSubGrad += SubGrad[i] * SubGrad[i];
2578 for(i = 0; i < lp.nr_lagrange; i++)
2579 if(lp.lag_con_type[i] != FALSE)
2581 if(Math.abs(SubGrad[i]) > lp.epsb)
2584 else if(SubGrad[i] > lp.epsb)
2587 if(OrigFeas != FALSE)
2591 for(i = 1; i <= lp.columns; i++)
2592 Ztmp += lp.best_solution[lp.rows + i] * OrigObj[i];
2593 if((lp.maximise != FALSE) && (Ztmp > Zlb))
2596 for(i = 1; i <= lp.sum; i++)
2597 BestFeasSol[i] = lp.best_solution[i];
2598 BestFeasSol[0] = Zlb;
2599 if(verbose != FALSE)
2600 System.out.println("Best feasible solution: " + Zlb);
2605 for(i = 1; i <= lp.sum; i++)
2606 BestFeasSol[i] = lp.best_solution[i];
2607 BestFeasSol[0] = Zub;
2608 if(verbose != FALSE)
2609 System.out.println("Best feasible solution: " + Zub);
2613 if(lp.maximise != FALSE)
2614 Zub = Math.min(Zub, rhsmod + lp.best_solution[0]);
2616 Zlb = Math.max(Zlb, rhsmod + lp.best_solution[0]);
2618 if(Math.abs(Zub-Zlb) < (float)0.001)
2622 Step = (float)(pie * ((1.05*Zub) - Zlb) / SqrsumSubGrad);
2624 for(i = 0; i < lp.nr_lagrange; i++)
2626 lp.lambda[i] += Step * SubGrad[i];
2627 if(lp.lag_con_type[i] == FALSE && lp.lambda[i] < 0)
2631 if(citer == num_iter && status==RUNNING)
2632 if(AnyFeas != FALSE)
2633 status = FEAS_FOUND;
2635 status = NO_FEAS_FOUND;
2638 for(i = 0; i <= lp.sum; i++)
2639 lp.best_solution[i] = BestFeasSol[i];
2641 for(i = 1; i <= lp.columns; i++)
2642 set_mat(lp, 0, i, OrigObj[i]);
2644 if(lp.maximise != FALSE)
2651 } // end of class solve
2654 public static class Matrix {
2657 public Matrix(int r, float v) { row_nr = r; value = v; }
2661 public static class Problem {
2662 String lp_name; /* the name of the lp */
2664 public short active; /*TRUE if the globals point to this structure*/
2665 public short verbose; /* ## Verbose flag */
2666 public short debug; /* ## Print B&B information */
2667 public short trace; /* ## Print information on pivot selection */
2668 public short anti_degen; /* ## Do perturbations */
2670 public int rows; /* Nr of constraint rows in the problem */
2671 int rows_alloc; /* The allocated memory for Rows sized data */
2672 int columns; /* The number of columns (= variables) */
2674 int sum; /* The size of the variables + the slacks */
2677 short names_used; /* Flag to indecate if names for rows and
2679 String[] row_name; /* rows_alloc+1 */
2680 int[] col_name; /* columns_alloc+1 */
2682 /* Row[0] of the sparce matrix is the objective function */
2684 int non_zeros; /* The number of elements in the sparce matrix*/
2685 int mat_alloc; /* The allocated size for matrix sized
2687 Matrix[] mat; /* mat_alloc :The sparse matrix */
2688 Matrix[] alternate_mat; /* mat_alloc :The sparse matrix */
2689 int[] col_end; /* columns_alloc+1 :Cend[i] is the index of the
2690 first element after column i.
2691 column[i] is stored in elements
2692 col_end[i-1] to col_end[i]-1 */
2693 int[] col_no; /* mat_alloc :From Row 1 on, col_no contains the
2695 nonzero elements, row by row */
2696 short row_end_valid; /* true if row_end & col_no are valid */
2697 int[] row_end; /* rows_alloc+1 :row_end[i] is the index of the
2698 first element in Colno after row i */
2699 float[] orig_rh; /* rows_alloc+1 :The RHS after scaling & sign
2700 changing, but before `Bound transformation' */
2701 float[] rh; /* rows_alloc+1 :As orig_rh, but after Bound
2703 float[] rhs; /* rows_alloc+1 :The RHS of the curent simplex
2705 float[] orig_upbo; /* sum_alloc+1 :Bound before transformations */
2706 float[] orig_lowbo; /* " " */
2707 float[] upbo; /* " " :Upper bound after transformation
2709 float[] lowbo; /* " " :Lower bound after transformation
2712 short basis_valid; /* TRUE is the basis is still valid */
2713 int[] bas; /* rows_alloc+1 :The basis column list */
2714 short[] basis; /* sum_alloc+1 : basis[i] is TRUE if the column
2716 short[] lower; /* " " :TRUE is the variable is at its
2717 lower bound (or in the basis), it is FALSE
2718 if the variable is at its upper bound */
2720 short eta_valid; /* TRUE if current Eta structures are valid */
2721 int eta_alloc; /* The allocated memory for Eta */
2722 int eta_size; /* The number of Eta columns */
2723 int num_inv; /* The number of float pivots */
2724 int max_num_inv; /* ## The number of float pivots between
2726 float[] eta_value; /* eta_alloc :The Structure containing the
2728 int[] eta_row_nr; /* " " :The Structure containing the Row
2730 int[] eta_col_end; /* rows_alloc + MaxNumInv : eta_col_end[i] is
2731 the start index of the next Eta column */
2733 short bb_rule; /* what rule for selecting B&B variables */
2735 short break_at_int; /* TRUE if stop at first integer better than
2739 float obj_bound; /* ## Objective function bound for speedup of
2741 int iter; /* The number of iterations in the simplex
2743 int total_iter; /* The total number of iterations (B&B) (ILP)*/
2744 int max_level; /* The Deepest B&B level of the last solution */
2745 int total_nodes; /* total number of nodes processed in b&b */
2746 public float[] solution; /* sum_alloc+1 :The Solution of the last LP,
2747 0 = The Optimal Value,
2749 rows+1..sum The Variables */
2750 public float[] best_solution; /* " " :The Best 'Integer' Solution */
2751 float[] duals; /* rows_alloc+1 :The dual variables of the
2754 short maximise; /* TRUE if the goal is to maximise the
2755 objective function */
2756 short floor_first; /* TRUE if B&B does floor bound first */
2757 short[] ch_sign; /* rows_alloc+1 :TRUE if the Row in the matrix
2759 (a`x > b, x>=0) is translated to
2760 s + -a`x = -b with x>=0, s>=0) */
2762 short scaling_used; /* TRUE if scaling is used */
2763 short columns_scaled; /* TRUE is the columns are scaled too, Only use
2764 if all variables are non-integer */
2765 float[] scale; /* sum_alloc+1 :0..Rows the scaling of the Rows,
2766 Rows+1..Sum the scaling of the columns */
2768 int nr_lagrange; /* Nr. of Langrangian relaxation constraints */
2769 float[][]lag_row; /* NumLagrange, columns+1:Pointer to pointer of
2771 float[] lag_rhs; /* NumLagrange :Pointer to pointer of Rhs */
2772 float[] lambda; /* NumLagrange :Lambda Values */
2773 short[] lag_con_type; /* NumLagrange :TRUE if constraint type EQ */
2774 float lag_bound; /* the lagrangian lower bound */
2776 short valid; /* Has this lp pased the 'test' */
2777 float infinite; /* ## numercal stuff */
2778 float epsilon; /* ## */
2779 float epsb; /* ## */
2780 float epsd; /* ## */
2781 float epsel; /* ## */
2784 public Problem (int nrows, int ncolumns, int matalloc) {
2786 nsum=nrows+ncolumns;
2791 columns_alloc=columns;
2795 max_num_inv=DEFNUMINV;
2796 col_no = new int[mat_alloc];
2797 col_end = new int[columns + 1];
2798 row_end = new int[rows + 1];
2799 orig_rh = new float[rows + 1];
2800 rh = new float[rows + 1];
2801 rhs = new float[rows + 1];
2802 orig_upbo = new float[sum + 1];
2803 upbo = new float[sum + 1];
2804 orig_lowbo = new float[sum + 1];
2805 lowbo = new float[sum + 1];
2806 bas = new int[rows+1];
2807 basis = new short[sum + 1];
2808 lower = new short[sum + 1];
2809 eta_value = new float[eta_alloc];
2810 eta_row_nr = new int[eta_alloc];
2811 eta_col_end = new int[rows_alloc + max_num_inv];
2812 solution = new float[sum + 1];
2813 best_solution = new float[sum + 1];
2814 duals = new float[rows + 1];
2815 ch_sign = new short[rows + 1];
2816 mat = new Matrix[mat_alloc];
2817 for(int j=0; j<mat.length; j++) mat[j] = new Matrix(0, 0);
2818 alternate_mat = new Matrix[mat_alloc];
2819 for(int j=0; j<alternate_mat.length; j++) alternate_mat[j] = new Matrix(0, 0);
2822 public void init(int nrows, int ncolumns) {
2824 nsum=nrows+ncolumns;
2825 lp_name = new String("unnamed");
2834 obj_bound=DEF_INFINITE;
2835 infinite=DEF_INFINITE;
2836 epsilon=DEF_EPSILON;
2842 for (i = 0; i < mat_alloc; i++) { mat[i].row_nr = 0; mat[i].value = 0; }
2843 for (i = 0; i < mat_alloc; i++) col_no[i] = 0;
2844 for (i = 0; i < columns + 1; i++) col_end[i] = 0;
2845 for (i = 0; i < rows + 1; i++) row_end[i] = 0;
2846 for (i = 0; i < rows + 1; i++) orig_rh[i] = 0;
2847 for (i = 0; i < rows + 1; i++) rh[i] = 0;
2848 for (i = 0; i < rows + 1; i++) rhs[i] = 0;
2849 for (i = 0; i <= sum; i++) orig_upbo[i]=infinite;
2850 for (i = 0; i < sum + 1; i++) upbo[i] = 0;
2851 for (i = 0; i < sum + 1; i++) orig_lowbo[i] = 0;
2852 for (i = 0; i < sum + 1; i++) lowbo[i] = 0;
2853 for (i = 0; i <= rows; i++) bas[i] = 0;
2854 for (i = 0; i <= sum; i++) basis[i] = 0;
2855 for (i = 0; i <= rows; i++) { bas[i]=i; basis[i]=TRUE; }
2856 for (i = rows + 1; i <= sum; i++) basis[i]=FALSE;
2857 for (i = 0 ; i <= sum; i++) lower[i]=TRUE;
2858 for (i = 0; i < eta_alloc; i++) eta_value[i] = 0;
2859 for (i = 0; i < eta_alloc; i++) eta_row_nr[i] = 0;
2860 for (i = 0; i < rows_alloc + max_num_inv; i++) eta_col_end[i] = 0;
2861 for (i = 0; i <= sum; i++) solution[i] = 0;
2862 for (i = 0; i <= sum; i++) best_solution[i] = 0;
2863 for (i = 0; i <= rows; i++) duals[i] = 0;
2864 for (i = 0; i <= rows; i++) ch_sign[i] = FALSE;
2866 row_end_valid=FALSE;
2878 scaling_used = FALSE;
2879 columns_scaled = FALSE;
2885 private final static float round( float val, float eps) { return (Math.abs(val) < eps) ? 0 : val; }