// Decompiled by Jad v1.5.7. Copyright 1997-99 Pavel Kouznetsov. // Jad home page: http://www.geocities.com/SiliconValley/Bridge/8617/jad.html // Decompiler options: packimports(3) // Source File Name: solve.java package lp; import java.io.PrintStream; import java.util.Random; import java.util.StringTokenizer; // Referenced classes of package lp: // constraint_name, column, Ref, rside, // constant, bound, Util, hashelem, // lprec, tmp_store_struct, matrec public class solve implements constant { void inc_mat_space(lprec lp, int maxextra) { if(lp.non_zeros + maxextra > lp.mat_alloc) { lp.mat_alloc = lp.non_zeros + maxextra; matrec old_mat[] = lp.mat; lp.mat = new matrec[lp.mat_alloc]; for(int i = old_mat.length; i < lp.mat.length; i++) lp.mat[i] = new matrec(0, 0.0D); System.arraycopy(old_mat, 0, lp.mat, 0, old_mat.length); int old_col_no[] = lp.col_no; lp.col_no = new int[lp.mat_alloc]; System.arraycopy(old_col_no, 0, lp.col_no, 0, old_col_no.length); if(lp.active != 0) { Mat = lp.mat; Col_no = lp.col_no; } } } void inc_row_space(lprec lp) { if(lp.rows > lp.rows_alloc) { lp.rows_alloc = lp.rows + 10; lp.sum_alloc = lp.rows_alloc + lp.columns_alloc; double db_ptr[] = lp.orig_rh; lp.orig_rh = new double[lp.rows_alloc + 1]; System.arraycopy(db_ptr, 0, lp.orig_rh, 0, db_ptr.length); db_ptr = lp.rh; lp.rh = new double[lp.rows_alloc + 1]; System.arraycopy(db_ptr, 0, lp.rh, 0, db_ptr.length); db_ptr = lp.rhs; lp.rhs = new double[lp.rows_alloc + 1]; System.arraycopy(db_ptr, 0, lp.rhs, 0, db_ptr.length); db_ptr = lp.orig_upbo; lp.orig_upbo = new double[lp.sum_alloc + 1]; System.arraycopy(db_ptr, 0, lp.orig_upbo, 0, db_ptr.length); db_ptr = lp.upbo; lp.upbo = new double[lp.sum_alloc + 1]; System.arraycopy(db_ptr, 0, lp.upbo, 0, db_ptr.length); db_ptr = lp.orig_lowbo; lp.orig_lowbo = new double[lp.sum_alloc + 1]; System.arraycopy(db_ptr, 0, lp.orig_lowbo, 0, db_ptr.length); db_ptr = lp.lowbo; lp.lowbo = new double[lp.sum_alloc + 1]; System.arraycopy(db_ptr, 0, lp.lowbo, 0, db_ptr.length); db_ptr = lp.solution; lp.solution = new double[lp.sum_alloc + 1]; System.arraycopy(db_ptr, 0, lp.solution, 0, db_ptr.length); db_ptr = lp.best_solution; lp.best_solution = new double[lp.sum_alloc + 1]; System.arraycopy(db_ptr, 0, lp.best_solution, 0, db_ptr.length); int int_ptr[] = lp.row_end; lp.row_end = new int[lp.rows_alloc + 1]; System.arraycopy(int_ptr, 0, lp.row_end, 0, int_ptr.length); short short_ptr[] = lp.basis; lp.basis = new short[lp.sum_alloc + 1]; System.arraycopy(short_ptr, 0, lp.basis, 0, short_ptr.length); short_ptr = lp.lower; lp.lower = new short[lp.sum_alloc + 1]; System.arraycopy(short_ptr, 0, lp.lower, 0, short_ptr.length); short_ptr = lp.must_be_int; lp.must_be_int = new short[lp.sum_alloc + 1]; System.arraycopy(short_ptr, 0, lp.must_be_int, 0, short_ptr.length); int_ptr = lp.bas; lp.bas = new int[lp.rows_alloc + 1]; System.arraycopy(int_ptr, 0, lp.bas, 0, int_ptr.length); db_ptr = lp.duals; lp.duals = new double[lp.rows_alloc + 1]; System.arraycopy(db_ptr, 0, lp.duals, 0, db_ptr.length); short_ptr = lp.ch_sign; lp.ch_sign = new short[lp.rows_alloc + 1]; System.arraycopy(short_ptr, 0, lp.ch_sign, 0, short_ptr.length); int_ptr = lp.eta_col_end; lp.eta_col_end = new int[lp.rows_alloc + lp.max_num_inv]; System.arraycopy(int_ptr, 0, lp.eta_col_end, 0, int_ptr.length); if(lp.names_used != 0) { String str_ptr[] = lp.row_name; lp.row_name = new String[lp.rows_alloc + 1]; System.arraycopy(str_ptr, 0, lp.row_name, 0, str_ptr.length); } if(lp.scaling_used != 0) { db_ptr = lp.scale; lp.scale = new double[lp.sum_alloc + 1]; System.arraycopy(db_ptr, 0, lp.scale, 0, db_ptr.length); } if(lp.active != 0) set_globals(lp); } } void inc_col_space(lprec lp) { if(lp.columns >= lp.columns_alloc) { lp.columns_alloc = lp.columns + 10; lp.sum_alloc = lp.rows_alloc + lp.columns_alloc; short short_ptr[] = lp.must_be_int; lp.must_be_int = new short[lp.sum_alloc + 1]; System.arraycopy(short_ptr, 0, lp.must_be_int, 0, short_ptr.length); double double_ptr[] = lp.orig_upbo; lp.orig_upbo = new double[lp.sum_alloc + 1]; System.arraycopy(double_ptr, 0, lp.orig_upbo, 0, double_ptr.length); double_ptr = lp.upbo; lp.upbo = new double[lp.sum_alloc + 1]; System.arraycopy(double_ptr, 0, lp.upbo, 0, double_ptr.length); double_ptr = lp.orig_lowbo; lp.orig_lowbo = new double[lp.sum_alloc + 1]; System.arraycopy(double_ptr, 0, lp.orig_lowbo, 0, double_ptr.length); double_ptr = lp.lowbo; lp.lowbo = new double[lp.sum_alloc + 1]; System.arraycopy(double_ptr, 0, lp.lowbo, 0, double_ptr.length); double_ptr = lp.solution; lp.solution = new double[lp.sum_alloc + 1]; System.arraycopy(double_ptr, 0, lp.solution, 0, double_ptr.length); double_ptr = lp.best_solution; lp.best_solution = new double[lp.sum_alloc + 1]; System.arraycopy(double_ptr, 0, lp.best_solution, 0, double_ptr.length); short_ptr = lp.basis; lp.basis = new short[lp.sum_alloc + 1]; System.arraycopy(short_ptr, 0, lp.basis, 0, short_ptr.length); short_ptr = lp.lower; lp.lower = new short[lp.sum_alloc + 1]; System.arraycopy(short_ptr, 0, lp.lower, 0, short_ptr.length); if(lp.names_used != 0) { String str_ptr[] = lp.col_name; lp.col_name = new String[lp.columns_alloc + 1]; System.arraycopy(str_ptr, 0, lp.col_name, 0, str_ptr.length); } if(lp.scaling_used != 0) { double_ptr = lp.scale; lp.scale = new double[lp.sum_alloc + 1]; System.arraycopy(double_ptr, 0, lp.scale, 0, double_ptr.length); } int int_ptr[] = lp.col_end; lp.col_end = new int[lp.columns_alloc + 1]; System.arraycopy(int_ptr, 0, lp.col_end, 0, int_ptr.length); if(lp.active != 0) set_globals(lp); } } public void set_mat(lprec lp, int Row, int Column, double Value) { if(Row > lp.rows || Row < 0) System.err.print("Row out of range"); if(Column > lp.columns || Column < 1) System.err.print("Column out of range"); if(lp.scaling_used != 0) Value *= lp.scale[Row] * lp.scale[lp.rows + Column]; if(lp.basis[Column] == 1 && Row > 0) lp.basis_valid = 0; lp.eta_valid = 0; int elmnr; for(elmnr = lp.col_end[Column - 1]; elmnr < lp.col_end[Column] && (lp.mat[elmnr].row_nr != Row || false); elmnr++); if(elmnr != lp.col_end[Column] && (lp.mat[elmnr].row_nr == Row || false)) { if(lp.scaling_used != 0) if(lp.ch_sign[Row] != 0) { lp.mat[elmnr].value = -Value * lp.scale[Row] * lp.scale[Column]; return; } else { lp.mat[elmnr].value = Value * lp.scale[Row] * lp.scale[Column]; return; } if(lp.ch_sign[Row] != 0) { lp.mat[elmnr].value = -Value; return; } else { lp.mat[elmnr].value = Value; return; } } inc_mat_space(lp, 1); int lastelm = lp.non_zeros; for(int i = lastelm; i > elmnr; i--) lp.mat[i] = lp.mat[i - 1]; for(int i = Column; i <= lp.columns; i++) lp.col_end[i]++; lp.mat[elmnr].row_nr = Row; if(lp.scaling_used != 0) { if(lp.ch_sign[Row] != 0) lp.mat[elmnr].value = -Value * lp.scale[Row] * lp.scale[Column]; else lp.mat[elmnr].value = Value * lp.scale[Row] * lp.scale[Column]; } else if(lp.ch_sign[Row] != 0) lp.mat[elmnr].value = -Value; else lp.mat[elmnr].value = Value; lp.row_end_valid = 0; lp.non_zeros++; if(lp.active != 0) Non_zeros = lp.non_zeros; } public void set_obj_fn(lprec lp, double row[]) { for(int i = 1; i <= lp.columns; i++) set_mat(lp, 0, i, row[i]); } public void str_set_obj_fn(lprec lp, String row) { double arow[] = new double[lp.columns + 1]; int i = 0; for(StringTokenizer stk = new StringTokenizer(row); stk.hasMoreTokens() && i < lp.columns;) { i++; arow[i] = Double.valueOf(stk.nextToken()).doubleValue(); } if(i < lp.columns) { System.err.println("Not enough numbers in the string in str_set_obj_fn"); System.exit(-1); } set_obj_fn(lp, arow); } public void add_constraint(lprec lp, double row[], short constr_type, double rh) { short addtoo[] = new short[lp.columns + 1]; for(int i = 1; i <= lp.columns; i++) if(row[i] != 0.0D) { addtoo[i] = 1; lp.non_zeros++; } else { addtoo[i] = 0; } matrec newmat[] = new matrec[lp.non_zeros]; for(int i = 0; i < newmat.length; i++) newmat[i] = new matrec(0, 0.0D); inc_mat_space(lp, 0); lp.rows++; lp.sum++; inc_row_space(lp); if(lp.scaling_used != 0) { for(int i = lp.sum; i > lp.rows; i--) lp.scale[i] = lp.scale[i - 1]; lp.scale[lp.rows] = 1.0D; } if(lp.names_used != 0) lp.row_name[lp.rows] = new String("r_" + lp.rows); if(lp.scaling_used != 0 && lp.columns_scaled != 0) { for(int i = 1; i <= lp.columns; i++) row[i] *= lp.scale[lp.rows + i]; } if(constr_type == 2) lp.ch_sign[lp.rows] = 1; else lp.ch_sign[lp.rows] = 0; int elmnr = 0; int stcol = 0; for(int i = 1; i <= lp.columns; i++) { for(int j = stcol; j < lp.col_end[i]; j++) { newmat[elmnr].row_nr = lp.mat[j].row_nr; newmat[elmnr].value = lp.mat[j].value; elmnr++; } if(addtoo[i] != 0) { if(lp.ch_sign[lp.rows] != 0) newmat[elmnr].value = -row[i]; else newmat[elmnr].value = row[i]; newmat[elmnr].row_nr = lp.rows; elmnr++; } stcol = lp.col_end[i]; lp.col_end[i] = elmnr; } lp.mat = newmat; for(int i = lp.sum; i > lp.rows; i--) { lp.orig_upbo[i] = lp.orig_upbo[i - 1]; lp.orig_lowbo[i] = lp.orig_lowbo[i - 1]; lp.basis[i] = lp.basis[i - 1]; lp.lower[i] = lp.lower[i - 1]; lp.must_be_int[i] = lp.must_be_int[i - 1]; } for(int i = 1; i <= lp.rows; i++) if(lp.bas[i] >= lp.rows) lp.bas[i]++; if(constr_type == 0 || constr_type == 2) lp.orig_upbo[lp.rows] = lp.infinite; //virsutnei ribai nera apribojimu else if(constr_type == 1) { lp.orig_upbo[lp.rows] = 0.0D; } else { System.err.print("Wrong constraint type\n"); System.exit(-1); } lp.orig_lowbo[lp.rows] = 0.0D; if(constr_type == 2 && rh != 0.0D) lp.orig_rh[lp.rows] = -rh; else lp.orig_rh[lp.rows] = rh; lp.row_end_valid = 0; lp.bas[lp.rows] = lp.rows; lp.basis[lp.rows] = 1; lp.lower[lp.rows] = 1; if(lp.active != 0) set_globals(lp); lp.eta_valid = 0; } public void str_add_constraint(lprec lp, String row_string, short constr_type, double rh) { int i = 0; double aRow[] = new double[lp.columns + 1]; for(StringTokenizer stk = new StringTokenizer(row_string); stk.hasMoreTokens() && i < lp.columns;) { i++; aRow[i] = Double.valueOf(stk.nextToken()).doubleValue(); } add_constraint(lp, aRow, constr_type, rh); } public void del_constraint(lprec lp, int del_row) { if(del_row < 1 || del_row > lp.rows) { System.err.println("There is no constraint nr. " + del_row); System.exit(-1); } int elmnr = 0; int startcol = 0; for(int i = 1; i <= lp.columns; i++) { for(int j = startcol; j < lp.col_end[i]; j++) if(lp.mat[j].row_nr != del_row) { lp.mat[elmnr] = lp.mat[j]; if(lp.mat[elmnr].row_nr > del_row) lp.mat[elmnr].row_nr--; elmnr++; } else { lp.non_zeros--; } startcol = lp.col_end[i]; lp.col_end[i] = elmnr; } for(int i = del_row; i < lp.rows; i++) { lp.orig_rh[i] = lp.orig_rh[i + 1]; lp.ch_sign[i] = lp.ch_sign[i + 1]; lp.bas[i] = lp.bas[i + 1]; if(lp.names_used != 0) lp.row_name[i] = lp.row_name[i + 1]; } for(int i = 1; i < lp.rows; i++) if(lp.bas[i] > del_row) lp.bas[i]--; for(int i = del_row; i < lp.sum; i++) { lp.lower[i] = lp.lower[i + 1]; lp.basis[i] = lp.basis[i + 1]; lp.orig_upbo[i] = lp.orig_upbo[i + 1]; lp.orig_lowbo[i] = lp.orig_lowbo[i + 1]; lp.must_be_int[i] = lp.must_be_int[i + 1]; if(lp.scaling_used != 0) lp.scale[i] = lp.scale[i + 1]; } lp.rows--; lp.sum--; lp.row_end_valid = 0; if(lp.active != 0) set_globals(lp); lp.eta_valid = 0; lp.basis_valid = 0; } public void add_lag_con(lprec lp, double row[], short con_type, double rhs) { double sign = 0.0D; if(con_type == 0 || con_type == 1) sign = 1.0D; else if(con_type == 2) sign = -1D; else System.err.print("con_type not implemented\n"); lp.nr_lagrange++; if(lp.nr_lagrange == 1) { lp.lag_row = new double[lp.nr_lagrange][]; lp.lag_rhs = new double[lp.nr_lagrange]; lp.lambda = new double[lp.nr_lagrange]; lp.lag_con_type = new short[lp.nr_lagrange]; for(int i = 0; i < lp.nr_lagrange; i++) { lp.lag_rhs[i] = 0.0D; lp.lambda[i] = 0.0D; lp.lag_con_type[i] = 0; } } else { double db2_ptr[][] = lp.lag_row; lp.lag_row = new double[lp.nr_lagrange][]; System.arraycopy(db2_ptr, 0, lp.lag_row, 0, db2_ptr.length); double db_ptr[] = lp.lag_rhs; lp.lag_rhs = new double[lp.nr_lagrange]; System.arraycopy(db_ptr, 0, lp.lag_rhs, 0, db_ptr.length); db_ptr = lp.lambda; lp.lambda = new double[lp.nr_lagrange]; System.arraycopy(db_ptr, 0, lp.lambda, 0, db_ptr.length); short short_ptr[] = lp.lag_con_type; lp.lag_con_type = new short[lp.nr_lagrange]; System.arraycopy(short_ptr, 0, lp.lag_con_type, 0, short_ptr.length); } lp.lag_row[lp.nr_lagrange - 1] = new double[lp.columns + 1]; lp.lag_rhs[lp.nr_lagrange - 1] = rhs * sign; for(int i = 1; i <= lp.columns; i++) lp.lag_row[lp.nr_lagrange - 1][i] = row[i] * sign; lp.lambda[lp.nr_lagrange - 1] = 0.0D; lp.lag_con_type[lp.nr_lagrange - 1] = (short)(con_type != 1 ? 0 : 1); } public void str_add_lag_con(lprec lp, String row, short con_type, double rhs) { int i = 0; double a_row[] = new double[lp.columns + 1]; for(StringTokenizer stk = new StringTokenizer(row); stk.hasMoreTokens() && i < lp.columns;) { i++; a_row[i] = Double.valueOf(stk.nextToken()).doubleValue(); } if(i < lp.columns) { System.err.println("not enough value for str_add_lag_con"); System.exit(-1); } add_lag_con(lp, a_row, con_type, rhs); } public void add_column(lprec lp, double column[]) { lp.columns++; lp.sum++; inc_col_space(lp); inc_mat_space(lp, lp.rows + 1); if(lp.scaling_used != 0) { for(int i = 0; i <= lp.rows; i++) column[i] *= lp.scale[i]; lp.scale[lp.sum] = 1.0D; } int elmnr = lp.col_end[lp.columns - 1]; for(int i = 0; i <= lp.rows; i++) if(column[i] != 0.0D) { lp.mat[elmnr].row_nr = i; if(lp.ch_sign[i] != 0) lp.mat[elmnr].value = -column[i]; else lp.mat[elmnr].value = column[i]; lp.non_zeros++; elmnr++; } lp.col_end[lp.columns] = elmnr; lp.orig_lowbo[lp.sum] = 0.0D; lp.orig_upbo[lp.sum] = lp.infinite; lp.lower[lp.sum] = 1; lp.basis[lp.sum] = 0; lp.must_be_int[lp.sum] = 0; if(lp.names_used != 0) lp.col_name[lp.columns] = new String("var_" + lp.columns); lp.row_end_valid = 0; if(lp.active != 0) { Sum = lp.sum; Columns = lp.columns; Non_zeros = lp.non_zeros; } } public void str_add_column(lprec lp, String col_string) { int i = 0; double aCol[] = new double[lp.rows + 1]; for(StringTokenizer stk = new StringTokenizer(col_string); stk.hasMoreTokens() && i < lp.rows;) { i++; aCol[i] = Double.valueOf(stk.nextToken()).doubleValue(); } if(i < lp.rows) { System.err.println("Bad String in str_add_column"); System.exit(-1); } add_column(lp, aCol); } public void del_column(lprec lp, int column) { if(column > lp.columns || column < 1) System.err.print("Column out of range in del_column"); for(int i = 1; i <= lp.rows; i++) if(lp.bas[i] == lp.rows + column) lp.basis_valid = 0; else if(lp.bas[i] > lp.rows + column) lp.bas[i]--; for(int i = lp.rows + column; i < lp.sum; i++) { if(lp.names_used != 0) lp.col_name[i - lp.rows] = lp.col_name[(i - lp.rows) + 1]; lp.must_be_int[i] = lp.must_be_int[i + 1]; lp.orig_upbo[i] = lp.orig_upbo[i + 1]; lp.orig_lowbo[i] = lp.orig_lowbo[i + 1]; lp.upbo[i] = lp.upbo[i + 1]; lp.lowbo[i] = lp.lowbo[i + 1]; lp.basis[i] = lp.basis[i + 1]; lp.lower[i] = lp.lower[i + 1]; if(lp.scaling_used != 0) lp.scale[i] = lp.scale[i + 1]; } for(int i = 0; i < lp.nr_lagrange; i++) { for(int j = column; j <= lp.columns; j++) lp.lag_row[i][j] = lp.lag_row[i][j + 1]; } int to_elm = lp.col_end[column - 1]; int from_elm = lp.col_end[column]; int elm_in_col = from_elm - to_elm; for(int i = from_elm; i < lp.non_zeros; i++) { lp.mat[to_elm] = lp.mat[i]; to_elm++; } for(int i = column; i < lp.columns; i++) lp.col_end[i] = lp.col_end[i + 1] - elm_in_col; lp.non_zeros -= elm_in_col; lp.row_end_valid = 0; lp.eta_valid = 0; lp.sum--; lp.columns--; if(lp.active != 0) set_globals(lp); } public void set_upbo(lprec lp, int column, double value) { if(column > lp.columns || column < 1) System.err.print("Column out of range"); if(lp.scaling_used != 0) value /= lp.scale[lp.rows + column]; if(value < lp.orig_lowbo[lp.rows + column]) System.err.print("Upperbound must be >= lowerbound"); lp.eta_valid = 0; lp.orig_upbo[lp.rows + column] = value; } public void set_lowbo(lprec lp, int column, double value) { if(column > lp.columns || column < 1) System.err.print("Column out of range"); if(lp.scaling_used != 0) value /= lp.scale[lp.rows + column]; if(value > lp.orig_upbo[lp.rows + column]) System.err.print("Upperbound must be >= lowerbound"); lp.eta_valid = 0; lp.orig_lowbo[lp.rows + column] = value; } public void set_int(lprec lp, int column, short must_be_int) { if(column > lp.columns || column < 1) System.err.print("Column out of range"); lp.must_be_int[lp.rows + column] = must_be_int; if(must_be_int == 1 && lp.columns_scaled != 0) unscale_columns(lp); } public void set_rh(lprec lp, int row, double value) { if(row > lp.rows || row < 0) System.err.print("Row out of Range"); if(row == 0) { System.err.println("Warning: attempt to set RHS of objective function, ignored"); return; } if(lp.scaling_used != 0) { if(lp.ch_sign[row] != 0) lp.orig_rh[row] = -value * lp.scale[row]; else lp.orig_rh[row] = value * lp.scale[row]; } else if(lp.ch_sign[row] != 0) lp.orig_rh[row] = -value; else lp.orig_rh[row] = value; lp.eta_valid = 0; } public void set_rh_vec(lprec lp, double rh[]) { if(lp.scaling_used != 0) { for(int i = 1; i <= lp.rows; i++) if(lp.ch_sign[i] != 0) lp.orig_rh[i] = -rh[i] * lp.scale[i]; else lp.orig_rh[i] = rh[i] * lp.scale[i]; } else { for(int i = 1; i <= lp.rows; i++) if(lp.ch_sign[i] != 0) lp.orig_rh[i] = -rh[i]; else lp.orig_rh[i] = rh[i]; } lp.eta_valid = 0; } public void str_set_rh_vec(lprec lp, String rh_string) { int i = 0; double newrh[] = new double[lp.rows + 1]; for(StringTokenizer stk = new StringTokenizer(rh_string); stk.hasMoreTokens() && i < lp.rows;) { i++; newrh[i] = Double.valueOf(stk.nextToken()).doubleValue(); } set_rh_vec(lp, newrh); } public void set_maxim(lprec lp) { if(lp.maximise == 0) { for(int i = 0; i < lp.non_zeros; i++) if(lp.mat[i].row_nr == 0) lp.mat[i].value *= -1D; lp.eta_valid = 0; } lp.maximise = 1; lp.ch_sign[0] = 1; if(lp.active != 0) Maximise = 1; } public void set_minim(lprec lp) { if(lp.maximise == 1) { for(int i = 0; i < lp.non_zeros; i++) if(lp.mat[i].row_nr == 0) lp.mat[i].value = -lp.mat[i].value; lp.eta_valid = 0; } lp.maximise = 0; lp.ch_sign[0] = 0; if(lp.active != 0) Maximise = 0; } public void set_constr_type(lprec lp, int row, short con_type) { if(row > lp.rows || row < 1) System.err.print("Row out of Range"); if(con_type == 1) { lp.orig_upbo[row] = 0.0D; lp.basis_valid = 0; if(lp.ch_sign[row] != 0) { for(int i = 0; i < lp.non_zeros; i++) if(lp.mat[i].row_nr == row) lp.mat[i].value *= -1D; lp.eta_valid = 0; lp.ch_sign[row] = 0; if(lp.orig_rh[row] != 0.0D) { lp.orig_rh[row] *= -1D; return; } } } else if(con_type == 0) { lp.orig_upbo[row] = lp.infinite; lp.basis_valid = 0; if(lp.ch_sign[row] != 0) { for(int i = 0; i < lp.non_zeros; i++) if(lp.mat[i].row_nr == row) lp.mat[i].value *= -1D; lp.eta_valid = 0; lp.ch_sign[row] = 0; if(lp.orig_rh[row] != 0.0D) { lp.orig_rh[row] *= -1D; return; } } } else if(con_type == 2) { lp.orig_upbo[row] = lp.infinite; lp.basis_valid = 0; if(lp.ch_sign[row] == 0) { for(int i = 0; i < lp.non_zeros; i++) if(lp.mat[i].row_nr == row) lp.mat[i].value *= -1D; lp.eta_valid = 0; lp.ch_sign[row] = 1; if(lp.orig_rh[row] != 0.0D) { lp.orig_rh[row] *= -1D; return; } } } else { System.err.print("Constraint type not (yet) implemented"); } } public double mat_elm(lprec lp, int row, int column) { if(row < 0 || row > lp.rows) System.err.print("Row out of range in mat_elm"); if(column < 1 || column > lp.columns) System.err.print("Column out of range in mat_elm"); double value = 0.0D; int elmnr; for(elmnr = lp.col_end[column - 1]; lp.mat[elmnr].row_nr != row && elmnr < lp.col_end[column]; elmnr++); if(elmnr != lp.col_end[column]) { value = lp.mat[elmnr].value; if(lp.ch_sign[row] != 0) value = -value; if(lp.scaling_used != 0) value /= lp.scale[row] * lp.scale[lp.rows + column]; } return value; } public void get_row(lprec lp, int row_nr, double row[]) { if(row_nr < 0 || row_nr > lp.rows) System.err.print("Row nr. out of range in get_row"); for(int i = 1; i <= lp.columns; i++) { row[i] = 0.0D; for(int j = lp.col_end[i - 1]; j < lp.col_end[i]; j++) if(lp.mat[j].row_nr == row_nr) row[i] = lp.mat[j].value; if(lp.scaling_used != 0) row[i] /= lp.scale[lp.rows + i] * lp.scale[row_nr]; } if(lp.ch_sign[row_nr] != 0) { for(int i = 0; i <= lp.columns; i++) if(row[i] != 0.0D) row[i] = -row[i]; } } public void get_column(lprec lp, int col_nr, double column[]) { if(col_nr < 1 || col_nr > lp.columns) System.err.print("Col. nr. out of range in get_column"); for(int i = 0; i <= lp.rows; i++) column[i] = 0.0D; for(int i = lp.col_end[col_nr - 1]; i < lp.col_end[col_nr]; i++) column[lp.mat[i].row_nr] = lp.mat[i].value; for(int i = 0; i <= lp.rows; i++) if(column[i] != 0.0D) { if(lp.ch_sign[i] != 0) column[i] *= -1D; if(lp.scaling_used != 0) column[i] /= lp.scale[i] * lp.scale[lp.rows + col_nr]; } } public void get_reduced_costs(lprec lp, double rc[]) { if(lp.basis_valid == 0) System.err.print("Not a valid basis in get_reduced_costs"); set_globals(lp); if(lp.eta_valid == 0) invert(); for(int i = 1; i <= lp.sum; i++) rc[i] = 0.0D; rc[0] = 1.0D; btran(rc); for(int i = 1; i <= lp.columns; i++) { int varnr = lp.rows + i; if(Basis[varnr] == 0 && Upbo[varnr] > 0.0D) { double f = 0.0D; for(int j = Col_end[i - 1]; j < Col_end[i]; j++) f += rc[Mat[j].row_nr] * Mat[j].value; rc[varnr] = f; } } for(int i = 1; i <= Sum; i++) rc[i] = Util.round(rc[i], Epsd); } short is_feasible(lprec lp, double values[]) { if(lp.scaling_used != 0) { for(int i = lp.rows + 1; i <= lp.sum; i++) if(values[i - lp.rows] < lp.orig_lowbo[i] * lp.scale[i] || values[i - lp.rows] > lp.orig_upbo[i] * lp.scale[i]) return 0; } else { for(int i = lp.rows + 1; i <= lp.sum; i++) if(values[i - lp.rows] < lp.orig_lowbo[i] || values[i - lp.rows] > lp.orig_upbo[i]) return 0; } double this_rhs[] = new double[lp.rows + 1]; for(int i = 0; i <= lp.rows; i++) this_rhs[i] = 0.0D; for(int i = 1; i <= lp.columns; i++) { for(int elmnr = lp.col_end[i - 1]; elmnr < lp.col_end[i]; elmnr++) this_rhs[lp.mat[elmnr].row_nr] += lp.mat[elmnr].value * values[i]; } for(int i = 1; i <= lp.rows; i++) { double dist = lp.orig_rh[i] - this_rhs[i]; dist = Util.round(dist, 0.001D); if(lp.orig_upbo[i] == 0.0D && dist != 0.0D || dist < 0.0D) return 0; } return 1; } short column_in_lp(lprec lp, double testcolumn[]) { if(lp.scaling_used != 0) { for(int i = 1; i <= lp.columns; i++) { short ident = 1; for(int j = lp.col_end[i - 1]; ident != 0 && j < lp.col_end[i]; j++) { double value = lp.mat[j].value; if(lp.ch_sign[lp.mat[j].row_nr] != 0) value = -value; value /= lp.scale[lp.rows + i]; value /= lp.scale[lp.mat[j].row_nr]; value -= testcolumn[lp.mat[j].row_nr]; if(Math.abs(value) > 0.001D) ident = 0; } if(ident != 0) return 1; } } else { for(int i = 1; i <= lp.columns; i++) { short ident = 1; for(int j = lp.col_end[i - 1]; ident != 0 && j < lp.col_end[i]; j++) { double value = lp.mat[j].value; if(lp.ch_sign[lp.mat[j].row_nr] != 0) value *= -1D; value -= testcolumn[lp.mat[j].row_nr]; if(Math.abs(value) > 0.001D) ident = 0; } if(ident != 0) return 1; } } return 0; } public void print_lp(lprec lp) { double fatmat[] = new double[(lp.rows + 1) * lp.columns]; for(int i = 0; i < fatmat.length; i++) fatmat[i] = 0.0D; for(int i = 1; i <= lp.columns; i++) { for(int j = lp.col_end[i - 1]; j < lp.col_end[i]; j++) fatmat[(i - 1) * (lp.rows + 1) + lp.mat[j].row_nr] = lp.mat[j].value; } System.out.println("problem name: " + lp.lp_name); System.out.print(" "); for(int j = 1; j <= lp.columns; j++) if(lp.names_used != 0) System.out.print(lp.col_name[j]); else System.out.print("Var[" + j + "] "); if(lp.maximise != 0) { System.out.print("\nMaximise "); for(int j = 0; j < lp.columns; j++) System.out.print(" " + -fatmat[j * (lp.rows + 1)] + " "); } else { System.out.print("\nMinimize "); for(int j = 0; j < lp.columns; j++) System.out.print(" " + fatmat[j * (lp.rows + 1)] + " "); } System.out.print("\n"); for(int i = 1; i <= lp.rows; i++) { if(lp.names_used != 0) System.out.print(lp.row_name[i]); else System.out.print("Row[" + i + "] "); for(int j = 0; j < lp.columns; j++) if(lp.ch_sign[i] != 0 && fatmat[j * (lp.rows + 1) + i] != 0.0D) System.out.print(-fatmat[j * (lp.rows + 1) + i] + " "); else System.out.print(fatmat[j * (lp.rows + 1) + i] + " "); if(lp.orig_upbo[i] == lp.infinite) { if(lp.ch_sign[i] != 0) System.out.print(">= "); else System.out.print("<= "); } else { System.out.print(" = "); } if(lp.ch_sign[i] != 0) System.out.println(-lp.orig_rh[i]); else System.out.println(lp.orig_rh[i]); } System.out.print("Type "); for(int i = 1; i <= lp.columns; i++) if(lp.must_be_int[lp.rows + i] == 1) System.out.print(" Int "); else System.out.print(" double "); System.out.print("\nupbo "); for(int i = 1; i <= lp.columns; i++) if(lp.orig_upbo[lp.rows + i] == lp.infinite) System.out.print(" Inf "); else System.out.print(lp.orig_upbo[lp.rows + i] + " "); System.out.print("\nlowbo "); for(int i = 1; i <= lp.columns; i++) System.out.print(lp.orig_lowbo[lp.rows + i] + " "); System.out.print("\n"); for(int i = 0; i < lp.nr_lagrange; i++) { System.out.print("lag[" + i + "] "); for(int j = 1; j <= lp.columns; j++) System.out.print(lp.lag_row[i][j] + " "); if(lp.orig_upbo[i] == lp.infinite) if(lp.lag_con_type[i] == 2) System.out.print(">= "); else if(lp.lag_con_type[i] == 0) System.out.print("<= "); else if(lp.lag_con_type[i] == 1) System.out.print(" = "); System.out.println(lp.lag_rhs[i]); } } public void set_row_name(lprec lp, int row, String new_name) { if(lp.names_used == 0) { lp.row_name = new String[lp.rows_alloc + 1]; lp.col_name = new String[lp.columns_alloc + 1]; lp.names_used = 1; for(int i = 0; i <= lp.rows; i++) lp.row_name[i] = new String("r_" + i); for(int i = 1; i <= lp.columns; i++) lp.col_name[i] = new String("var_" + i); } lp.row_name[row] = new_name; } public void set_col_name(lprec lp, int column, String new_name) { if(lp.names_used == 0) { lp.row_name = new String[lp.rows_alloc + 1]; lp.col_name = new String[lp.columns_alloc + 1]; lp.names_used = 1; for(int i = 0; i <= lp.rows; i++) lp.row_name[i] = new String("r_" + i); for(int i = 1; i <= lp.columns; i++) lp.col_name[i] = new String("var_" + i); } lp.col_name[column] = new_name; } private double minmax_to_scale(double min, double max) { if(min == 0.0D || max == 0.0D) { return 1.0D; } else { double scale = 1.0D / Math.pow(2.7182818284590451D, (Math.log(min) + Math.log(max)) / 2D); return scale; } } public void unscale_columns(lprec lp) { for(int j = 1; j <= lp.columns; j++) { for(int i = lp.col_end[j - 1]; i < lp.col_end[j]; i++) lp.mat[i].value /= lp.scale[lp.rows + j]; } for(int i = lp.rows + 1; i < lp.sum; i++) { if(lp.orig_lowbo[i] != 0.0D) lp.orig_lowbo[i] *= lp.scale[i]; if(lp.orig_upbo[i] != lp.infinite) lp.orig_upbo[i] *= lp.scale[i]; } for(int i = lp.rows + 1; i <= lp.sum; i++) lp.scale[i] = 1.0D; lp.columns_scaled = 0; lp.eta_valid = 0; } public void unscale(lprec lp) { if(lp.scaling_used != 0) { for(int j = 1; j <= lp.columns; j++) { for(int i = lp.col_end[j - 1]; i < lp.col_end[j]; i++) lp.mat[i].value /= lp.scale[lp.rows + j]; } for(int i = lp.rows + 1; i < lp.sum; i++) { if(lp.orig_lowbo[i] != 0.0D) lp.orig_lowbo[i] *= lp.scale[i]; if(lp.orig_upbo[i] != lp.infinite) lp.orig_upbo[i] *= lp.scale[i]; } for(int j = 1; j <= lp.columns; j++) { for(int i = lp.col_end[j - 1]; i < lp.col_end[j]; i++) lp.mat[i].value /= lp.scale[lp.mat[i].row_nr]; } for(int i = 0; i <= lp.rows; i++) lp.orig_rh[i] /= lp.scale[i]; lp.scaling_used = 0; lp.eta_valid = 0; } } public void auto_scale(lprec lp) { if(lp.scaling_used == 0) { lp.scale = new double[lp.sum_alloc + 1]; for(int i = 0; i <= lp.sum; i++) lp.scale[i] = 1.0D; } double row_max[] = new double[lp.rows + 1]; double row_min[] = new double[lp.rows + 1]; double scalechange[] = new double[lp.sum + 1]; for(int i = 0; i <= lp.rows; i++) { row_max[i] = 0.0D; row_min[i] = lp.infinite; } for(int j = 1; j <= lp.columns; j++) { for(int i = lp.col_end[j - 1]; i < lp.col_end[j]; i++) { int row_nr = lp.mat[i].row_nr; double absval = Math.abs(lp.mat[i].value); if(absval != 0.0D) { row_max[row_nr] = Math.max(row_max[row_nr], absval); row_min[row_nr] = Math.min(row_min[row_nr], absval); } } } for(int i = 0; i <= lp.rows; i++) { scalechange[i] = minmax_to_scale(row_min[i], row_max[i]); lp.scale[i] *= scalechange[i]; } for(int j = 1; j <= lp.columns; j++) { for(int i = lp.col_end[j - 1]; i < lp.col_end[j]; i++) lp.mat[i].value *= scalechange[lp.mat[i].row_nr]; } for(int i = 0; i <= lp.rows; i++) lp.orig_rh[i] *= scalechange[i]; int IntUsed = 0; for(int i = lp.rows + 1; IntUsed == 0 && i <= lp.sum; i++) IntUsed = lp.must_be_int[i]; if(IntUsed == 0) { for(int j = 1; j <= lp.columns; j++) { double col_max = 0.0D; double col_min = lp.infinite; for(int i = lp.col_end[j - 1]; i < lp.col_end[j]; i++) if(lp.mat[i].value != 0.0D) { col_max = Math.max(col_max, Math.abs(lp.mat[i].value)); col_min = Math.min(col_min, Math.abs(lp.mat[i].value)); } scalechange[lp.rows + j] = minmax_to_scale(col_min, col_max); lp.scale[lp.rows + j] *= scalechange[lp.rows + j]; } for(int j = 1; j <= lp.columns; j++) { for(int i = lp.col_end[j - 1]; i < lp.col_end[j]; i++) lp.mat[i].value *= scalechange[lp.rows + j]; } for(int i = lp.rows + 1; i < lp.sum; i++) { if(lp.orig_lowbo[i] != 0.0D) lp.orig_lowbo[i] /= scalechange[i]; if(lp.orig_upbo[i] != lp.infinite) lp.orig_upbo[i] /= scalechange[i]; } lp.columns_scaled = 1; } lp.scaling_used = 1; lp.eta_valid = 0; } public void reset_basis(lprec lp) { lp.basis_valid = 0; } public int get_lpcolumns(lprec lp) { return lp.columns; } public int get_lprows(lprec lp) { return lp.rows; } public double get_lpsolution(lprec lp, int index) { return lp.best_solution[index]; } public void print_solution(lprec lp) { System.out.println("Value of objective function: " + lp.best_solution[0]); for(int i = 1; i <= lp.columns; i++) if(lp.names_used != 0) System.out.println(lp.col_name[i] + " " + lp.best_solution[lp.rows + i]); else System.out.println("Var [" + i + "] " + lp.best_solution[lp.rows + i]); if(lp.verbose != 0) { System.out.print("\nActual values of the constraints:\n"); for(int i = 1; i <= lp.rows; i++) if(lp.names_used != 0) System.out.println(lp.row_name[i] + " " + lp.best_solution[i]); else System.out.println("Row [" + i + "] " + " " + lp.best_solution[i]); } if(lp.verbose != 0 || lp.print_duals != 0) { if(lp.max_level != 1) System.out.print("These are the duals from the node that gave the optimal solution.\n"); else System.out.print("\nDual values:\n"); for(int i = 1; i <= lp.rows; i++) if(lp.names_used != 0) System.out.println(lp.row_name[i] + " " + lp.duals[i]); else System.out.println("Row [" + i + "] " + lp.duals[i]); } } public void write_LP(lprec lp, PrintStream output) { double row[] = new double[lp.columns + 1]; if(lp.maximise != 0) output.print("max:"); else output.print("min:"); get_row(lp, 0, row); int i; for(i = 1; i <= lp.columns; i++) if(row[i] != 0.0D) { if(row[i] == -1D) output.print(" -"); else if(row[i] == 1.0D) output.print(" +"); else output.print(row[i]); if(lp.names_used != 0) output.print(lp.col_name[i]); else output.print("x" + i); } output.print(";\n"); for(int j = 1; j <= lp.rows; j++) { if(lp.names_used != 0) output.print(lp.row_name[j]); get_row(lp, j, row); for(i = 1; i <= lp.columns; i++) if(row[i] != 0.0D) { if(row[i] == -1D) output.print(" -"); else if(row[i] == 1.0D) output.print(" +"); else output.print(" " + row[i] + " "); if(lp.names_used != 0) output.print(lp.col_name[i]); else output.print("x" + i); } if(lp.orig_upbo[j] == 0.0D) output.print(" ="); else if(lp.ch_sign[j] != 0) output.print(" >"); else output.print(" <"); if(lp.ch_sign[j] != 0) output.println(" " + -lp.orig_rh[j]); else output.println(" " + lp.orig_rh[j]); } for(i = lp.rows + 1; i <= lp.sum; i++) { if(lp.orig_lowbo[i] != 0.0D) if(lp.names_used != 0) output.println(lp.col_name[i - lp.rows] + ">" + lp.orig_lowbo[i] + ";"); else output.print("x" + (i - lp.rows) + " > " + lp.orig_lowbo[i] + ";"); if(lp.orig_upbo[i] != lp.infinite) if(lp.names_used != 0) output.println(lp.col_name[i - lp.rows] + " < " + lp.orig_upbo[i] + ";"); else output.println("x" + (i - lp.rows) + " < " + lp.orig_upbo[i] + ";"); } for(i = 1; lp.must_be_int[lp.rows + i] == 0 && i <= lp.columns; i++); if(i <= lp.columns) { if(lp.names_used != 0) output.print("\nint " + lp.col_name[i]); else output.print("\nint x" + i); for(i++; i <= lp.columns; i++) if(lp.must_be_int[lp.rows + i] != 0) if(lp.names_used != 0) output.print("," + lp.col_name[i]); else output.print(", x" + i); output.print(";\n"); } } public void print_duals(lprec lp) { for(int i = 1; i <= lp.rows; i++) if(lp.names_used != 0) System.out.println(lp.row_name[i] + " [" + i + "] " + lp.duals[i]); else System.out.println("Dual [" + i + "] " + lp.duals[i]); } public void print_scales(lprec lp) { if(lp.scaling_used != 0) { for(int i = 0; i <= lp.rows; i++) System.out.println("Row[" + i + "] scaled at " + lp.scale[i]); for(int i = 1; i <= lp.columns; i++) System.out.println("Column[" + i + "] scaled at " + lp.scale[lp.rows + i]); } } private void print_indent() { System.out.print(Level); if(Level < 50) { for(int i = Level; i > 0; i--) System.out.print("--"); } else { System.out.print(" *** too deep ***"); } System.out.print("> "); } public void debug_print_solution() { if(Lp.debug != 0) { for(int i = Rows + 1; i <= Sum; i++) { print_indent(); if(Lp.names_used != 0) System.out.println(Lp.col_name[i - Rows] + " " + Solution[i]); else System.out.println("Var[" + (i - Rows) + "] " + Solution[i]); } } } public void debug_print_bounds(double upbo[], double lowbo[]) { if(Lp.debug != 0) { for(int i = Rows + 1; i <= Sum; i++) { if(lowbo[i] != 0.0D) { print_indent(); if(Lp.names_used != 0) System.out.println(Lp.col_name[i - Rows] + " > " + lowbo[i]); else System.out.print("Var[" + (i - Rows) + "] > " + lowbo[i]); } if(upbo[i] != Infinite) { print_indent(); if(Lp.names_used != 0) System.out.println(Lp.col_name[i - Rows] + " < " + upbo[i]); else System.out.println("Var[" + (i - Rows) + "] < " + upbo[i]); } } } } public void debug_print(String format) { if(Lp.debug != 0) { print_indent(); System.out.print(format); } } void set_globals(lprec lp) { if(Lp != null) Lp.active = 0; Lp = lp; Rows = lp.rows; Columns = lp.columns; Sum = Rows + Columns; Non_zeros = lp.non_zeros; Mat = lp.mat; Col_no = lp.col_no; Col_end = lp.col_end; Row_end = lp.row_end; Rh = lp.rh; Rhs = lp.rhs; Orig_rh = lp.orig_rh; Must_be_int = lp.must_be_int; Orig_upbo = lp.orig_upbo; Orig_lowbo = lp.orig_lowbo; Upbo = lp.upbo; Lowbo = lp.lowbo; Bas = lp.bas; Basis = lp.basis; Lower = lp.lower; Eta_alloc = lp.eta_alloc; Eta_size = lp.eta_size; Num_inv = lp.num_inv; Eta_value = lp.eta_value; Eta_row_nr = lp.eta_row_nr; Eta_col_end = lp.eta_col_end; Solution = lp.solution; Best_solution = lp.best_solution; Infinite = lp.infinite; Epsilon = lp.epsilon; Epsb = lp.epsb; Epsd = lp.epsd; Epsel = lp.epsel; TREJ = TREJ; TINV = TINV; Maximise = lp.maximise; Floor_first = lp.floor_first; lp.active = 1; } private void ftran(int start, int end, double pcol[]) { for(int i = start; i <= end; i++) { int k = Eta_col_end[i] - 1; int r = Eta_row_nr[k]; double theta = pcol[r]; if(theta != 0.0D) { for(int j = Eta_col_end[i - 1]; j < k; j++) pcol[Eta_row_nr[j]] += theta * Eta_value[j]; } pcol[r] *= Eta_value[k]; } for(int i = 0; i <= Rows; i++) Util.round(pcol[i], Epsel); } private void btran(double row[]) { for(int i = Eta_size; i >= 1; i--) { double f = 0.0D; int k = Eta_col_end[i] - 1; for(int j = Eta_col_end[i - 1]; j <= k; j++) f += row[Eta_row_nr[j]] * Eta_value[j]; f = Util.round(f, Epsel); row[Eta_row_nr[k]] = f; } } static short Isvalid(lprec lp) { int rownum[]; if(lp.row_end_valid == 0) { int num[] = new int[lp.rows + 1]; rownum = new int[lp.rows + 1]; for(int i = 0; i <= lp.rows; i++) { num[i] = 0; rownum[i] = 0; } for(int i = 0; i < lp.non_zeros; i++) rownum[lp.mat[i].row_nr]++; lp.row_end[0] = 0; for(int i = 1; i <= lp.rows; i++) lp.row_end[i] = lp.row_end[i - 1] + rownum[i]; for(int i = 1; i <= lp.columns; i++) { for(int j = lp.col_end[i - 1]; j < lp.col_end[i]; j++) { int row_nr = lp.mat[j].row_nr; if(row_nr != 0) { num[row_nr]++; lp.col_no[lp.row_end[row_nr - 1] + num[row_nr]] = i; } } } lp.row_end_valid = 1; } if(lp.valid != 0) return 1; rownum = new int[lp.rows + 1]; for(int i = 0; i <= lp.rows; i++) rownum[i] = 0; int colnum[] = new int[lp.columns + 1]; for(int i = 0; i <= lp.columns; i++) colnum[i] = 0; for(int i = 1; i <= lp.columns; i++) { for(int j = lp.col_end[i - 1]; j < lp.col_end[i]; j++) { colnum[i]++; rownum[lp.mat[j].row_nr]++; } } for(int i = 1; i <= lp.columns; i++) if(colnum[i] == 0) if(lp.names_used != 0) System.err.print("Warning: Variable " + lp.col_name[i] + " not used in any constraints\n"); else System.err.print("Warning: Variable " + i + " not used in any constaints\n"); lp.valid = 1; return 1; } private void resize_eta() { Eta_alloc *= 2; double db_ptr[] = Eta_value; Eta_value = new double[Eta_alloc]; System.arraycopy(db_ptr, 0, Eta_value, 0, db_ptr.length); Lp.eta_value = Eta_value; int int_ptr[] = Eta_row_nr; Eta_row_nr = new int[Eta_alloc]; System.arraycopy(int_ptr, 0, Eta_row_nr, 0, int_ptr.length); Lp.eta_row_nr = Eta_row_nr; } private void condensecol(int row_nr, double pcol[]) { int elnr = Eta_col_end[Eta_size]; if(elnr + Rows + 2 > Eta_alloc) resize_eta(); for(int i = 0; i <= Rows; i++) if(i != row_nr && pcol[i] != 0.0D) { Eta_row_nr[elnr] = i; Eta_value[elnr] = pcol[i]; elnr++; } Eta_row_nr[elnr] = row_nr; Eta_value[elnr] = pcol[row_nr]; elnr++; Eta_col_end[Eta_size + 1] = elnr; } private void addetacol() { int j = Eta_col_end[Eta_size]; Eta_size++; int k = Eta_col_end[Eta_size]; double theta = 1.0D / Eta_value[k - 1]; Eta_value[k - 1] = theta; for(int i = j; i < k - 1; i++) Eta_value[i] *= -theta; JustInverted = 0; } private void setpivcol(short lower, int varin, double pcol[]) { double f; if(lower != 0) f = 1.0D; else f = -1D; for(int i = 0; i <= Rows; i++) pcol[i] = 0.0D; if(varin > Rows) { int colnr = varin - Rows; for(int i = Col_end[colnr - 1]; i < Col_end[colnr]; i++) pcol[Mat[i].row_nr] = Mat[i].value * f; pcol[0] -= Extrad * f; } else if(lower != 0) pcol[varin] = 1.0D; else pcol[varin] = -1D; ftran(1, Eta_size, pcol); } private void minoriteration(int colnr, int row_nr) { double piv = 0.0D; int varin = colnr + Rows; int elnr = Eta_col_end[Eta_size]; int wk = elnr; Eta_size++; if(Extrad != 0.0D) { Eta_row_nr[elnr] = 0; Eta_value[elnr] = -Extrad; elnr++; } for(int j = Col_end[colnr - 1]; j < Col_end[colnr]; j++) { int k = Mat[j].row_nr; if(k == 0 && Extrad != 0.0D) Eta_value[Eta_col_end[Eta_size - 1]] += Mat[j].value; else if(k != row_nr) { Eta_row_nr[elnr] = k; Eta_value[elnr] = Mat[j].value; elnr++; } else { piv = Mat[j].value; } } Eta_row_nr[elnr] = row_nr; Eta_value[elnr] = 1.0D / piv; elnr++; double theta = Rhs[row_nr] / piv; Rhs[row_nr] = theta; for(int i = wk; i < elnr - 1; i++) Rhs[Eta_row_nr[i]] -= theta * Eta_value[i]; int varout = Bas[row_nr]; Bas[row_nr] = varin; Basis[varout] = 0; Basis[varin] = 1; for(int i = wk; i < elnr - 1; i++) Eta_value[i] /= -piv; Eta_col_end[Eta_size] = elnr; } private void rhsmincol(double theta, int row_nr, int varin) { if(row_nr > Rows + 1) { System.err.print("Error: rhsmincol called with row_nr: " + row_nr + ", rows: " + Rows + "\n"); System.err.print("This indicates numerical instability\n"); System.exit(-1); } int j = Eta_col_end[Eta_size]; int k = Eta_col_end[Eta_size + 1]; for(int i = j; i < k; i++) { double f = Rhs[Eta_row_nr[i]] - theta * Eta_value[i]; f = Util.round(f, Epsb); Rhs[Eta_row_nr[i]] = f; } Rhs[row_nr] = theta; int varout = Bas[row_nr]; Bas[row_nr] = varin; Basis[varout] = 0; Basis[varin] = 1; } void invert() { if(Lp.print_at_invert != 0) System.out.print("Start Invert iter " + Lp.iter + " eta_size " + Eta_size + " rhs[0] " + -Rhs[0] + " \n"); int rownum[] = new int[Rows + 1]; for(int i = 0; i <= Rows; i++) rownum[i] = 0; int col[] = new int[Rows + 1]; for(int i = 0; i <= Rows; i++) col[i] = 0; int row[] = new int[Rows + 1]; for(int i = 0; i <= Rows; i++) row[i] = 0; double pcol[] = new double[Rows + 1]; for(int i = 0; i <= Rows; i++) pcol[i] = 0.0D; short frow[] = new short[Rows + 1]; for(int i = 0; i <= Rows; i++) frow[i] = 1; short fcol[] = new short[Columns + 1]; for(int i = 0; i < Columns; i++) fcol[i] = 0; int colnum[] = new int[Columns + 1]; for(int i = 0; i <= Columns; i++) colnum[i] = 0; for(int i = 0; i <= Rows; i++) if(Bas[i] > Rows) fcol[Bas[i] - Rows - 1] = 1; else frow[Bas[i]] = 0; for(int i = 1; i <= Rows; i++) if(frow[i] != 0) { for(int j = Row_end[i - 1] + 1; j <= Row_end[i]; j++) { int wk = Col_no[j]; if(fcol[wk - 1] != 0) { colnum[wk]++; rownum[i - 1]++; } } } for(int i = 1; i <= Rows; i++) Bas[i] = i; for(int i = 1; i <= Rows; i++) Basis[i] = 1; for(int i = 1; i <= Columns; i++) Basis[i + Rows] = 0; for(int i = 0; i <= Rows; i++) Rhs[i] = Rh[i]; for(int i = 1; i <= Columns; i++) { int varnr = Rows + i; if(Lower[varnr] == 0) { double theta = Upbo[varnr]; for(int j = Col_end[i - 1]; j < Col_end[i]; j++) Rhs[Mat[j].row_nr] -= theta * Mat[j].value; } } for(int i = 1; i <= Rows; i++) if(Lower[i] == 0) Rhs[i] -= Upbo[i]; Eta_size = 0; int v = 0; int row_nr = 0; Num_inv = 0; int numit = 0; int colnr; while(v < Rows) { if(++row_nr > Rows) row_nr = 1; v++; if(rownum[row_nr - 1] == 1 && frow[row_nr] != 0) { v = 0; int j; for(j = Row_end[row_nr - 1] + 1; fcol[Col_no[j] - 1] == 0; j++); colnr = Col_no[j]; fcol[colnr - 1] = 0; colnum[colnr] = 0; for(j = Col_end[colnr - 1]; j < Col_end[colnr]; j++) if(frow[Mat[j].row_nr] != 0) rownum[Mat[j].row_nr - 1]--; frow[row_nr] = 0; minoriteration(colnr, row_nr); } } v = 0; colnr = 0; while(v < Columns) { if(++colnr > Columns) colnr = 1; v++; if(colnum[colnr] == 1 && fcol[colnr - 1] != 0) { v = 0; int j; for(j = Col_end[colnr - 1] + 1; frow[Mat[j - 1].row_nr] == 0; j++); row_nr = Mat[j - 1].row_nr; frow[row_nr] = 0; rownum[row_nr - 1] = 0; for(j = Row_end[row_nr - 1] + 1; j <= Row_end[row_nr]; j++) if(fcol[Col_no[j] - 1] != 0) colnum[Col_no[j]]--; fcol[colnr - 1] = 0; numit++; col[numit - 1] = colnr; row[numit - 1] = row_nr; } } for(int j = 1; j <= Columns; j++) if(fcol[j - 1] != 0) { fcol[j - 1] = 0; setpivcol(Lower[Rows + j], j + Rows, pcol); //TODO fixed bug. row_nr <= Rows must be checked before using it to get value from array //old line //for(row_nr = 1; (frow[row_nr] == 0 || pcol[row_nr] == 0.0D) && row_nr <= Rows; row_nr++); for(row_nr = 1; row_nr <= Rows && (frow[row_nr] == 0 || pcol[row_nr] == 0.0D) ; row_nr++); if(row_nr == Rows + 1){ //row_nr--; if row_nr > Rows... should work now. System.err.print("Inverting failed"); } else { frow[row_nr] = 0; condensecol(row_nr, pcol); double theta = Rhs[row_nr] / pcol[row_nr]; rhsmincol(theta, row_nr, Rows + j); addetacol(); } } for(int i = numit - 1; i >= 0; i--) { colnr = col[i]; row_nr = row[i]; int varin = colnr + Rows; for(int j = 0; j <= Rows; j++) pcol[j] = 0.0D; for(int j = Col_end[colnr - 1]; j < Col_end[colnr]; j++) pcol[Mat[j].row_nr] = Mat[j].value; pcol[0] -= Extrad; condensecol(row_nr, pcol); double theta = Rhs[row_nr] / pcol[row_nr]; rhsmincol(theta, row_nr, varin); addetacol(); } for(int i = 1; i <= Rows; i++) Rhs[i] = Util.round(Rhs[i], Epsb); if(Lp.print_at_invert != 0) System.out.print("End Invert eta_size " + Eta_size + " rhs[0] " + -Rhs[0] + "\n"); JustInverted = 1; DoInvert = 0; } private short colprim(Ref colnr, short minit, double drow[]) { double dpiv = -Epsd; colnr.value = 0.0D; if(minit == 0) { for(int i = 1; i <= Sum; i++) drow[i] = 0.0D; drow[0] = 1.0D; btran(drow); for(int i = 1; i <= Columns; i++) { int varnr = Rows + i; if(Basis[varnr] == 0 && Upbo[varnr] > 0.0D) { double f = 0.0D; for(int j = Col_end[i - 1]; j < Col_end[i]; j++) f += drow[Mat[j].row_nr] * Mat[j].value; drow[varnr] = f; } } for(int i = 1; i <= Sum; i++) drow[i] = Util.round(drow[i], Epsd); } for(int i = 1; i <= Sum; i++) if(Basis[i] == 0 && Upbo[i] > 0.0D) { double f; if(Lower[i] != 0) f = drow[i]; else f = -drow[i]; if(f < dpiv) { dpiv = f; colnr.value = i; } } if(Lp.trace != 0) if(colnr.value > 0.0D) System.err.print("col_prim:" + colnr.value + ", reduced cost: " + dpiv + "\n"); else System.err.print("col_prim: no negative reduced costs found, optimality!\n"); if(colnr.value == 0.0D) { Doiter = 0; DoInvert = 0; Status = 0; } return (short)(colnr.value <= 0.0D ? 0 : 1); } private short rowprim(int colnr, Ref row_nr, Ref theta, double pcol[]) { double f = 0.0D; row_nr.value = 0.0D; theta.value = Infinite; for(int i = 1; i <= Rows; i++) { f = pcol[i]; if(Math.abs(f) < TREJ) f = 0.0D; if(f != 0.0D) { double quot = 2D * Infinite; if(f > 0.0D) quot = Rhs[i] / f; else if(Upbo[Bas[i]] < Infinite) quot = (Rhs[i] - Upbo[Bas[i]]) / f; Util.round(quot, Epsel); if(quot < theta.value) { theta.value = quot; row_nr.value = i; } } } if(row_nr.value == 0.0D) { for(int i = 1; i <= Rows; i++) { f = pcol[i]; if(f != 0.0D) { double quot = 2D * Infinite; if(f > 0.0D) quot = Rhs[i] / f; else if(Upbo[Bas[i]] < Infinite) quot = (Rhs[i] - Upbo[Bas[i]]) / f; quot = Util.round(quot, Epsel); if(quot < theta.value) { theta.value = quot; row_nr.value = i; } } } } if(theta.value < 0.0D) { System.err.println("Warning: Numerical instability, qout = " + theta.value); System.err.println("pcol[" + row_nr.value + "] = " + f + ", rhs[" + row_nr.value + "] = " + Rhs[(int)row_nr.value] + " , upbo = " + Upbo[Bas[(int)row_nr.value]]); } if(row_nr.value == 0.0D) if(Upbo[colnr] == Infinite) { Doiter = 0; DoInvert = 0; Status = 3; } else { int i; for(i = 1; pcol[i] >= 0.0D && i <= Rows; i++); if(i > Rows) { Lower[colnr] = 0; Rhs[0] += Upbo[colnr] * pcol[0]; Doiter = 0; DoInvert = 0; } else if(pcol[i] < 0.0D) row_nr.value = i; } if(row_nr.value > 0.0D) Doiter = 1; if(Lp.trace != 0) System.out.println("row_prim:" + row_nr.value + ", pivot element:" + pcol[(int)row_nr.value]); return (short)(row_nr.value <= 0.0D ? 0 : 1); } private short rowdual(Ref row_nr) { row_nr.value = 0.0D; double minrhs = -Epsb; int i = 0; for(short artifs = 0; i < Rows && artifs == 0;) { i++; double f = Upbo[Bas[i]]; if(f == 0.0D && Rhs[i] != 0.0D) { artifs = 1; row_nr.value = i; } else { double g; if(Rhs[i] < f - Rhs[i]) g = Rhs[i]; else g = f - Rhs[i]; if(g < minrhs) { minrhs = g; row_nr.value = i; } } } if(Lp.trace != 0) if(row_nr.value > 0.0D) { System.out.println("row_dual:" + row_nr.value + ", rhs of selected row: " + Rhs[(int)row_nr.value]); if(Upbo[Bas[(int)row_nr.value]] < Infinite) System.out.println(" upper bound of basis variable: " + Upbo[Bas[(int)row_nr.value]]); } else { System.out.print("row_dual: no infeasibilities found\n"); } return (short)(row_nr.value <= 0.0D ? 0 : 1); } private short coldual(int row_nr, Ref colnr, short minit, double prow[], double drow[]) { Doiter = 0; if(minit == 0) { for(int i = 0; i <= Rows; i++) { prow[i] = 0.0D; drow[i] = 0.0D; } drow[0] = 1.0D; prow[row_nr] = 1.0D; for(int i = Eta_size; i >= 1; i--) { double d = 0.0D; double f = 0.0D; int r = Eta_row_nr[Eta_col_end[i] - 1]; for(int j = Eta_col_end[i - 1]; j < Eta_col_end[i]; j++) { f += prow[Eta_row_nr[j]] * Eta_value[j]; d += drow[Eta_row_nr[j]] * Eta_value[j]; } f = Util.round(f, Epsel); prow[r] = f; d = Util.round(d, Epsel); drow[r] = d; } for(int i = 1; i <= Columns; i++) { int varnr = Rows + i; if(Basis[varnr] == 0) { double d = -Extrad * drow[0]; double f = 0.0D; for(int j = Col_end[i - 1]; j < Col_end[i]; j++) { d += drow[Mat[j].row_nr] * Mat[j].value; f += prow[Mat[j].row_nr] * Mat[j].value; } drow[varnr] = d; prow[varnr] = f; } } for(int i = 0; i <= Sum; i++) { prow[i] = Util.round(prow[i], Epsel); drow[i] = Util.round(drow[i], Epsd); } } double g; if(Rhs[row_nr] > Upbo[Bas[row_nr]]) g = -1D; else g = 1.0D; double pivot = 0.0D; colnr.value = 0.0D; double theta = Infinite; for(int i = 1; i <= Sum; i++) { double d; if(Lower[i] != 0) d = prow[i] * g; else d = -prow[i] * g; if(d < 0.0D && Basis[i] == 0 && Upbo[i] > 0.0D) { double quot; if(Lower[i] == 0) quot = -drow[i] / d; else quot = drow[i] / d; if(quot < theta) { theta = quot; pivot = d; colnr.value = i; } else if(quot == theta && Math.abs(d) > Math.abs(pivot)) { pivot = d; colnr.value = i; } } } if(Lp.trace != 0) System.out.println("col_dual:" + colnr.value + ", pivot element: " + prow[(int)colnr.value]); if(colnr.value > 0.0D) Doiter = 1; return (short)(colnr.value <= 0.0D ? 0 : 1); } private void iteration(int row_nr, int varin, Ref theta, double up, Ref minit, Ref low, short primal, double pcol[]) { Lp.iter++; minit.value = theta.value <= up + Epsb ? 0 : 1; if(minit.value != 0.0D) { theta.value = up; low.value = low.value != 0.0D ? 0 : 1; } int k = Eta_col_end[Eta_size + 1]; double pivot = Eta_value[k - 1]; for(int i = Eta_col_end[Eta_size]; i < k; i++) { double f = Rhs[Eta_row_nr[i]] - theta.value * Eta_value[i]; f = Util.round(f, Epsb); Rhs[Eta_row_nr[i]] = f; } if(minit.value == 0.0D) { Rhs[row_nr] = theta.value; int varout = Bas[row_nr]; Bas[row_nr] = varin; Basis[varout] = 0; Basis[varin] = 1; if(primal != 0 && pivot < 0.0D) Lower[varout] = 0; if(low.value == 0.0D && up < Infinite) { low.value = 1.0D; Rhs[row_nr] = up - Rhs[row_nr]; for(int i = Eta_col_end[Eta_size]; i < k; i++) Eta_value[i] = -Eta_value[i]; } addetacol(); Num_inv++; } if(Lp.trace != 0) { System.out.print("Theta = " + theta.value + " "); if(minit.value != 0.0D) { if(Lower[varin] == 0) System.out.print("Iteration:" + Lp.iter + ", variable" + varin + " changed from 0 to its upper bound of " + Upbo[varin] + "\n"); else System.out.print("Iteration:" + Lp.iter + ", variable" + varin + " changed its upper bound of " + Upbo[varin] + " to 0\n"); } else { System.out.print("Iteration:" + Lp.iter + ", variable" + varin + " entered basis at:" + Rhs[row_nr] + "\n"); } if(primal == 0) { double f = 0.0D; for(int i = 1; i <= Rows; i++) if(Rhs[i] < 0.0D) f -= Rhs[i]; else if(Rhs[i] > Upbo[Bas[i]]) f += Rhs[i] - Upbo[Bas[i]]; System.out.println("feasibility gap of this basis:" + f); return; } System.out.println("objective function value of this feasible basis: " + Rhs[0]); } } private int solvelp() { double f = 0.0D; double theta = 0.0D; int colnr = 0; int row_nr = 0; Ref ref1 = new Ref(0.0D); Ref ref2 = new Ref(0.0D); Ref ref3 = new Ref(0.0D); double drow[] = new double[Sum + 1]; double prow[] = new double[Sum + 1]; double Pcol[] = new double[Rows + 1]; int i; for(i = 0; i <= Sum; i++) { drow[i] = 0.0D; prow[i] = 0.0D; } for(i = 0; i <= Rows; i++) Pcol[i] = 0.0D; Lp.iter = 0; short minit = 0; Status = 5; DoInvert = 0; Doiter = 0; i = 0; short primal; for(primal = 1; i != Rows && primal != 0; primal = (short)(Rhs[i] < 0.0D || Rhs[i] > Upbo[Bas[i]] ? 0 : 1)) i++; if(Lp.trace != 0) if(primal != 0) System.out.print("Start at feasible basis\n"); else System.out.print("Start at infeasible basis\n"); if(primal == 0) { drow[0] = 1.0D; for(i = 1; i <= Rows; i++) drow[i] = 0.0D; Extrad = 0.0D; for(i = 1; i <= Columns; i++) { int varnr = Rows + i; drow[varnr] = 0.0D; for(int j = Col_end[i - 1]; j < Col_end[i]; j++) if(drow[Mat[j].row_nr] != 0.0D) drow[varnr] += drow[Mat[j].row_nr] * Mat[j].value; if(drow[varnr] < Extrad) Extrad = drow[varnr]; } } else { Extrad = 0.0D; } if(Lp.trace != 0) System.out.println("Extrad = " + Extrad); minit = 0; while(Status == 5) { Doiter = 0; DoInvert = 0; construct_solution(Solution); debug_print_bounds(Upbo, Lowbo); debug_print_solution(); if(primal != 0) { ref1.value = colnr; short flag = colprim(ref1, minit, drow); colnr = (int)ref1.value; if(flag != 0) { setpivcol(Lower[colnr], colnr, Pcol); ref1.value = row_nr; ref2.value = theta; flag = rowprim(colnr, ref1, ref2, Pcol); row_nr = (int)ref1.value; theta = ref2.value; if(flag != 0) condensecol(row_nr, Pcol); } } else { if(minit == 0) { ref1.value = row_nr; short flag = rowdual(ref1); row_nr = (int)ref1.value; } if(row_nr > 0) { ref1.value = colnr; short flag = coldual(row_nr, ref1, minit, prow, drow); colnr = (int)ref1.value; if(flag != 0) { setpivcol(Lower[colnr], colnr, Pcol); if(Pcol[row_nr] == 0.0D) { System.err.println("An attempt was made to divide by zero (Pcol[" + row_nr + "])"); System.err.println("This indicates numerical instability"); Doiter = 0; if(JustInverted == 0) { System.out.println("Reinverting Eta"); DoInvert = 1; } else { System.out.println("Can't reinvert, failure"); Status = 4; } } else { condensecol(row_nr, Pcol); f = Rhs[row_nr] - Upbo[Bas[row_nr]]; if(f > 0.0D) { theta = f / Pcol[row_nr]; if(theta <= Upbo[colnr]) Lower[Bas[row_nr]] = (short)(Lower[Bas[row_nr]] != 0 ? 0 : 1); } else { theta = Rhs[row_nr] / Pcol[row_nr]; } } } else { Status = 2; } } else { primal = 1; Doiter = 0; Extrad = 0.0D; DoInvert = 1; } } if(Doiter != 0) { ref1.value = theta; ref2.value = minit; ref3.value = Lower[colnr]; iteration(row_nr, colnr, ref1, Upbo[colnr], ref2, ref3, primal, Pcol); theta = ref1.value; minit = (short)(int)ref2.value; Lower[colnr] = (short)(int)ref3.value; } if(Num_inv >= Lp.max_num_inv) DoInvert = 1; if(DoInvert != 0) { if(Lp.print_at_invert != 0) System.out.println("Inverting: Primal = " + primal); invert(); } } Lp.total_iter += Lp.iter; return Status; } private short is_int(double value) { double tmp = value - Math.floor(value); if(tmp < Epsilon) return 1; return (short)(tmp <= 1.0D - Epsilon ? 0 : 1); } private void construct_solution(double sol[]) { for(int i = 0; i <= Rows; i++) sol[i] = 0.0D; if(Lp.scaling_used != 0) { for(int i = Rows + 1; i <= Sum; i++) sol[i] = Lowbo[i] * Lp.scale[i]; for(int i = 1; i <= Rows; i++) { int basi = Bas[i]; if(basi > Rows) sol[basi] += Rhs[i] * Lp.scale[basi]; } for(int i = Rows + 1; i <= Sum; i++) if(Basis[i] == 0 && Lower[i] == 0) sol[i] += Upbo[i] * Lp.scale[i]; for(int j = 1; j <= Columns; j++) { double f = sol[Rows + j]; if(f != 0.0D) { for(int i = Col_end[j - 1]; i < Col_end[j]; i++) sol[Mat[i].row_nr] += (f / Lp.scale[Rows + j]) * (Mat[i].value / Lp.scale[Mat[i].row_nr]); } } for(int i = 0; i <= Rows; i++) if(Math.abs(sol[i]) < Epsb) sol[i] = 0.0D; else if(Lp.ch_sign[i] != 0) sol[i] = -sol[i]; return; } for(int i = Rows + 1; i <= Sum; i++) sol[i] = Lowbo[i]; for(int i = 1; i <= Rows; i++) { int basi = Bas[i]; if(basi > Rows) sol[basi] += Rhs[i]; } for(int i = Rows + 1; i <= Sum; i++) if(Basis[i] == 0 && Lower[i] == 0) sol[i] += Upbo[i]; for(int j = 1; j <= Columns; j++) { double f = sol[Rows + j]; if(f != 0.0D) { for(int i = Col_end[j - 1]; i < Col_end[j]; i++) sol[Mat[i].row_nr] += f * Mat[i].value; } } for(int i = 0; i <= Rows; i++) if(Math.abs(sol[i]) < Epsb) sol[i] = 0.0D; else if(Lp.ch_sign[i] != 0) sol[i] = -sol[i]; } private void calculate_duals() { for(int i = 1; i <= Rows; i++) Lp.duals[i] = 0.0D; Lp.duals[0] = 1.0D; btran(Lp.duals); if(Lp.scaling_used != 0) { for(int i = 1; i <= Rows; i++) Lp.duals[i] *= Lp.scale[i] / Lp.scale[0]; } for(int i = 1; i <= Rows; i++) if(Lp.basis[i] != 0) Lp.duals[i] = 0.0D; else if(Lp.ch_sign[0] == Lp.ch_sign[i]) Lp.duals[i] = -Lp.duals[i]; } private int milpsolve(double upbo[], double lowbo[], short sbasis[], short slower[], int sbas[]) { Random rdm = new Random(); int notint = 0; if(Break_bb != 0) return 8; Level++; Lp.total_nodes++; if(Level > Lp.max_level) Lp.max_level = Level; debug_print("starting solve\n"); System.arraycopy(upbo, 0, Upbo, 0, Sum + 1); System.arraycopy(lowbo, 0, Lowbo, 0, Sum + 1); System.arraycopy(sbasis, 0, Basis, 0, Sum + 1); System.arraycopy(slower, 0, Lower, 0, Sum + 1); System.arraycopy(sbas, 0, Bas, 0, Rows + 1); System.arraycopy(Orig_rh, 0, Rh, 0, Rows + 1); if(Lp.anti_degen != 0) { for(int i = 1; i <= Columns; i++) { double tmpdouble = rdm.nextDouble() * 0.001D; if(tmpdouble > Epsb) Lowbo[i + Rows] -= tmpdouble; tmpdouble = rdm.nextDouble() * 0.001D; if(tmpdouble > Epsb) Upbo[i + Rows] += tmpdouble; } Lp.eta_valid = 0; } if(Lp.eta_valid == 0) { for(int i = 1; i <= Columns; i++) if(Lowbo[Rows + i] != 0.0D) { double theta = Lowbo[Rows + i]; if(Upbo[Rows + i] < Infinite) Upbo[Rows + i] -= theta; for(int j = Col_end[i - 1]; j < Col_end[i]; j++) Rh[Mat[j].row_nr] -= theta * Mat[j].value; } invert(); Lp.eta_valid = 1; } int failure = solvelp(); if(Lp.anti_degen != 0) { System.arraycopy(upbo, 0, Upbo, 0, Sum + 1); System.arraycopy(lowbo, 0, Lowbo, 0, Sum + 1); System.arraycopy(Orig_rh, 0, Rh, 0, Rows + 1); for(int i = 1; i <= Columns; i++) if(Lowbo[Rows + i] != 0.0D) { double theta = Lowbo[Rows + i]; if(Upbo[Rows + i] < Infinite) Upbo[Rows + i] -= theta; for(int j = Col_end[i - 1]; j < Col_end[i]; j++) Rh[Mat[j].row_nr] -= theta * Mat[j].value; } invert(); Lp.eta_valid = 1; failure = solvelp(); } if(failure != 0) debug_print("this problem has no solution, it is " + (failure != 3 ? "infeasible" : "unbounded")); if(failure == 2 && Lp.verbose != 0) System.out.print("level" + Level + " INF\n"); if(failure == 0) { construct_solution(Solution); debug_print("a solution was found\n"); debug_print_solution(); int is_worse; if(Maximise != 0) is_worse = Solution[0] > Best_solution[0] ? 0 : 1; else is_worse = Solution[0] < Best_solution[0] ? 0 : 1; if(is_worse != 0) { if(Lp.verbose != 0) System.out.println("level" + Level + " OPT NOB value " + Solution[0] + " bound " + Best_solution[0]); debug_print("but it was worse than the best sofar, discarded\n"); Level--; return 1; } if(Lp.bb_rule == 0) { notint = 0; for(int i = Rows + 1; i <= Sum && notint == 0; i++) if(Must_be_int[i] != 0 && is_int(Solution[i]) == 0) if(lowbo[i] == upbo[i]) { System.err.println("Warning: integer var " + (i - Rows) + " is already fixed at " + lowbo[i] + ", but has non-integer value " + Solution[i]); System.err.println("Perhaps the -e option should be used"); } else { notint = i; } } if(Lp.bb_rule == 1) { int nr_not_int = 0; for(int i = Rows + 1; i <= Sum; i++) if(Must_be_int[i] != 0 && is_int(Solution[i]) == 0) nr_not_int++; if(nr_not_int == 0) { notint = 0; } else { int select_not_int = rdm.nextInt() % nr_not_int + 1; int i; for(i = Rows + 1; select_not_int > 0; i++) if(Must_be_int[i] != 0 && is_int(Solution[i]) == 0) select_not_int--; notint = i - 1; } } if(Lp.verbose == 1) if(notint != 0) System.out.println("level " + Level + " OPT value " + Solution[0]); else System.out.println("level " + Level + " OPT INT value " + Solution[0]); if(notint != 0) { double new_upbo[] = new double[Sum + 1]; double new_lowbo[] = new double[Sum + 1]; short new_lower[] = new short[Sum + 1]; short new_basis[] = new short[Sum + 1]; int new_bas[] = new int[Rows + 1]; System.arraycopy(upbo, 0, new_upbo, 0, Sum + 1); System.arraycopy(lowbo, 0, new_lowbo, 0, Sum + 1); System.arraycopy(Lower, 0, new_lower, 0, Sum + 1); System.arraycopy(Basis, 0, new_basis, 0, Sum + 1); System.arraycopy(Bas, 0, new_bas, 0, Rows + 1); if(Lp.names_used != 0) debug_print("not enough ints. Selecting var " + Lp.col_name[notint - Rows] + ", val: " + Solution[notint]); else debug_print("not enough ints. Selecting Var [" + notint + "], val: " + Solution[notint]); debug_print("current bounds:\n"); debug_print_bounds(upbo, lowbo); int resone; int restwo; if(Floor_first != 0) { double new_bound = Math.ceil(Solution[notint]) - 1.0D; if(new_bound < lowbo[notint]) { debug_print("New upper bound value " + new_bound + " conflicts with old lower bound " + lowbo[notint] + "\n"); resone = 1; } else { new_upbo[notint] = new_bound; debug_print("starting first subproblem with bounds:"); debug_print_bounds(new_upbo, lowbo); Lp.eta_valid = 0; resone = milpsolve(new_upbo, lowbo, new_basis, new_lower, new_bas); Lp.eta_valid = 0; } new_bound++; if(new_bound > upbo[notint]) { debug_print("New lower bound value " + new_bound + " conflicts with old upper bound " + upbo[notint] + "\n"); restwo = 1; } else { new_lowbo[notint] = new_bound; debug_print("starting second subproblem with bounds:"); debug_print_bounds(upbo, new_lowbo); Lp.eta_valid = 0; restwo = milpsolve(upbo, new_lowbo, new_basis, new_lower, new_bas); Lp.eta_valid = 0; } } else { double new_bound = Math.ceil(Solution[notint]); if(new_bound > upbo[notint]) { debug_print("New lower bound value " + new_bound + " conflicts with old upper bound " + upbo[notint] + "\n"); resone = 1; } else { new_lowbo[notint] = new_bound; debug_print("starting first subproblem with bounds:"); debug_print_bounds(upbo, new_lowbo); Lp.eta_valid = 0; resone = milpsolve(upbo, new_lowbo, new_basis, new_lower, new_bas); Lp.eta_valid = 0; } new_bound--; if(new_bound < lowbo[notint]) { debug_print("New upper bound value " + new_bound + " conflicts with old lower bound " + lowbo[notint] + "\n"); restwo = 1; } else { new_upbo[notint] = new_bound; debug_print("starting second subproblem with bounds:"); debug_print_bounds(new_upbo, lowbo); Lp.eta_valid = 0; restwo = milpsolve(new_upbo, lowbo, new_basis, new_lower, new_bas); Lp.eta_valid = 0; } } if(resone != 0 && restwo != 0) failure = 2; else failure = 0; } else { debug_print("--> valid solution found\n"); if(Maximise != 0) is_worse = Solution[0] >= Best_solution[0] ? 0 : 1; else is_worse = Solution[0] <= Best_solution[0] ? 0 : 1; if(is_worse == 0) { if(Lp.debug != 0 || Lp.verbose != 0 && Lp.print_sol == 0) System.out.print("*** new best solution: old: " + Best_solution[0] + ", new: " + Solution[0] + " ***\n"); System.arraycopy(Solution, 0, Best_solution, 0, Sum + 1); calculate_duals(); if(Lp.print_sol != 0) print_solution(Lp); if(Lp.break_at_int != 0) { if(Maximise != 0 && Best_solution[0] > Lp.break_value) Break_bb = 1; if(Maximise == 0 && Best_solution[0] < Lp.break_value) Break_bb = 1; } } } } Level--; return failure; } public int solve(lprec lp) { if(lp.active == 0) set_globals(lp); lp.total_iter = 0; lp.max_level = 1; lp.total_nodes = 0; if(Isvalid(lp) != 0) { if(Maximise != 0 && lp.obj_bound == Infinite) Best_solution[0] = -Infinite; else if(Maximise == 0 && lp.obj_bound == -Infinite) Best_solution[0] = Infinite; else Best_solution[0] = lp.obj_bound; Level = 0; if(lp.basis_valid == 0) { for(int i = 0; i <= lp.rows; i++) { lp.basis[i] = 1; lp.bas[i] = i; } for(int i = lp.rows + 1; i <= lp.sum; i++) lp.basis[i] = 0; for(int i = 0; i <= lp.sum; i++) lp.lower[i] = 1; lp.basis_valid = 1; } lp.eta_valid = 0; Break_bb = 0; int result = milpsolve(Orig_upbo, Orig_lowbo, Basis, Lower, Bas); lp.eta_size = Eta_size; lp.eta_alloc = Eta_alloc; lp.num_inv = Num_inv; return result; } else { return 4; } } public int lag_solve(lprec lp, double start_bound, int num_iter, short verbose) { double OrigObj[] = new double[lp.columns + 1]; double ModObj[] = new double[lp.columns + 1]; for(int i = 0; i <= lp.columns; i++) ModObj[i] = 0.0D; double SubGrad[] = new double[lp.nr_lagrange]; for(int i = 0; i < lp.nr_lagrange; i++) SubGrad[i] = 0.0D; double BestFeasSol[] = new double[lp.sum + 1]; for(int i = 0; i <= lp.sum; i++) BestFeasSol[i] = 0.0D; int old_bas[] = new int[lp.rows + 1]; System.arraycopy(lp.bas, 0, old_bas, 0, lp.rows + 1); short old_lower[] = new short[lp.sum + 1]; System.arraycopy(lp.lower, 0, old_lower, 0, lp.sum + 1); get_row(lp, 0, OrigObj); double pie = 2D; double Zub; double Zlb; if(lp.maximise != 0) { Zub = 9.9999999999999998E+023D; Zlb = start_bound; } else { Zlb = -9.9999999999999998E+023D; Zub = start_bound; } short status = 5; double Step = 1.0D; short OrigFeas = 0; short AnyFeas = 0; int citer = 0; for(int i = 0; i < lp.nr_lagrange; i++) lp.lambda[i] = 0.0D; while(status == 5) { citer++; for(int i = 1; i <= lp.columns; i++) { ModObj[i] = OrigObj[i]; for(int j = 0; j < lp.nr_lagrange; j++) if(lp.maximise != 0) ModObj[i] -= lp.lambda[j] * lp.lag_row[j][i]; else ModObj[i] += lp.lambda[j] * lp.lag_row[j][i]; } for(int i = 1; i <= lp.columns; i++) set_mat(lp, 0, i, ModObj[i]); double rhsmod = 0.0D; for(int i = 0; i < lp.nr_lagrange; i++) if(lp.maximise != 0) rhsmod += lp.lambda[i] * lp.lag_rhs[i]; else rhsmod -= lp.lambda[i] * lp.lag_rhs[i]; if(verbose != 0) { System.out.println("Zub: " + Zub + " Zlb: " + Zlb + " Step: " + Step + " pie: " + pie + " Feas " + OrigFeas); for(int i = 0; i < lp.nr_lagrange; i++) System.out.println(i + " SubGrad " + SubGrad[i] + " lambda " + lp.lambda[i]); } if(verbose != 0 && lp.sum < 20) print_lp(lp); int result = solve(lp); if(verbose != 0 && lp.sum < 20) print_solution(lp); short same_basis = 1; for(int i = 1; same_basis != 0 && i < lp.rows; i++) same_basis = (short)(old_bas[i] != lp.bas[i] ? 0 : 1); for(int i = 1; same_basis != 0 && i < lp.sum; i++) same_basis = (short)(old_lower[i] != lp.lower[i] ? 0 : 1); if(same_basis == 0) { System.arraycopy(lp.lower, 0, old_lower, 0, lp.sum + 1); System.arraycopy(lp.bas, 0, old_bas, 0, lp.rows + 1); pie *= 0.95000000000000007D; } if(verbose != 0) System.out.println("result: " + result + " same basis: " + same_basis); if(result == 3) { for(int i = 1; i <= lp.columns; i++) System.out.print(ModObj[i] + " "); System.exit(-1); } if(result == 4) status = 4; if(result == 2) status = 2; double SqrsumSubGrad = 0.0D; for(int i = 0; i < lp.nr_lagrange; i++) { SubGrad[i] = -lp.lag_rhs[i]; for(int j = 1; j <= lp.columns; j++) SubGrad[i] += lp.best_solution[lp.rows + j] * lp.lag_row[i][j]; SqrsumSubGrad += SubGrad[i] * SubGrad[i]; } OrigFeas = 1; for(int i = 0; i < lp.nr_lagrange; i++) if(lp.lag_con_type[i] != 0) { if(Math.abs(SubGrad[i]) > lp.epsb) OrigFeas = 0; } else if(SubGrad[i] > lp.epsb) OrigFeas = 0; if(OrigFeas != 0) { AnyFeas = 1; double Ztmp = 0.0D; for(int i = 1; i <= lp.columns; i++) Ztmp += lp.best_solution[lp.rows + i] * OrigObj[i]; if(lp.maximise != 0 && Ztmp > Zlb) { Zlb = Ztmp; for(int i = 1; i <= lp.sum; i++) BestFeasSol[i] = lp.best_solution[i]; BestFeasSol[0] = Zlb; if(verbose != 0) System.out.println("Best feasible solution: " + Zlb); } else if(Ztmp < Zub) { Zub = Ztmp; for(int i = 1; i <= lp.sum; i++) BestFeasSol[i] = lp.best_solution[i]; BestFeasSol[0] = Zub; if(verbose != 0) System.out.println("Best feasible solution: " + Zub); } } if(lp.maximise != 0) Zub = Math.min(Zub, rhsmod + lp.best_solution[0]); else Zlb = Math.max(Zlb, rhsmod + lp.best_solution[0]); if(Math.abs(Zub - Zlb) < 0.001D) status = 0; Step = (pie * (1.05D * Zub - Zlb)) / SqrsumSubGrad; for(int i = 0; i < lp.nr_lagrange; i++) { lp.lambda[i] += Step * SubGrad[i]; if(lp.lag_con_type[i] == 0 && lp.lambda[i] < 0.0D) lp.lambda[i] = 0.0D; } if(citer == num_iter && status == 5) if(AnyFeas != 0) status = 6; else status = 7; } for(int i = 0; i <= lp.sum; i++) lp.best_solution[i] = BestFeasSol[i]; for(int i = 1; i <= lp.columns; i++) set_mat(lp, 0, i, OrigObj[i]); if(lp.maximise != 0) lp.lag_bound = Zub; else lp.lag_bound = Zlb; return status; } public solve() { } lprec Lp; int Rows; int Columns; int Sum; int Non_zeros; int Level; matrec Mat[]; int Col_no[]; int Col_end[]; int Row_end[]; double Orig_rh[]; double Rh[]; double Rhs[]; short Must_be_int[]; double Orig_upbo[]; double Orig_lowbo[]; double Upbo[]; double Lowbo[]; int Bas[]; short Basis[]; short Lower[]; int Eta_alloc; int Eta_size; double Eta_value[]; int Eta_row_nr[]; int Eta_col_end[]; int Num_inv; double Solution[]; double Best_solution[]; double Infinite; double Epsilon; double Epsb; double Epsd; double Epsel; double TREJ; double TINV; short Maximise; short Floor_first; double Extrad; int Warn_count; short JustInverted; short Status; short Doiter; short DoInvert; short Break_bb; }