- } /* milpsolve */
-
- public int solve(Problem lp)
- {
- int result, i;
-
- if(lp.active == FALSE)
- set_globals(lp);
-
- lp.total_iter = 0;
- lp.max_level = 1;
- lp.total_nodes = 0;
-
- if(Isvalid(lp) != FALSE)
- {
- if(Maximise != FALSE && lp.obj_bound == Infinite)
- Best_solution[0]=-Infinite;
- else if(Maximise == FALSE && lp.obj_bound==-Infinite)
- Best_solution[0] = Infinite;
- else
- Best_solution[0] = lp.obj_bound;
-
- Level = 0;
-
- if(lp.basis_valid == FALSE)
- {
- for(i = 0; i <= lp.rows; i++)
- {
- lp.basis[i] = TRUE;
- lp.bas[i] = i;
- }
- for(i = lp.rows+1; i <= lp.sum; i++)
- lp.basis[i] = FALSE;
- for(i = 0; i <= lp.sum; i++)
- lp.lower[i] = TRUE;
- lp.basis_valid = TRUE;
- }
-
- lp.eta_valid = FALSE;
- Break_bb = FALSE;
- 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);
- }
-
- /* if we get here, Isvalid(lp) failed. I suggest we return FAILURE */
- return(FAILURE);
- }
-
- public int lag_solve(Problem lp, float start_bound, int num_iter, short verbose)
- {
- int i, j, result, citer;
- short status, OrigFeas, AnyFeas, same_basis;
- float[] OrigObj, ModObj, SubGrad, BestFeasSol;
- float Zub, Zlb, Ztmp, pie;
- float rhsmod, Step, SqrsumSubGrad;
- int[] old_bas;
- short[] old_lower;
-
- /* allocate mem */
- OrigObj = new float[lp.columns + 1];
- ModObj = new float[lp.columns + 1];
- for (i = 0; i <= lp.columns; i++)
- ModObj[i] = 0;
- SubGrad = new float[lp.nr_lagrange];
- for (i = 0; i < lp.nr_lagrange; i++)
- SubGrad[i] = 0;
- BestFeasSol = new float[lp.sum + 1];
- for (i = 0; i <= lp.sum; i++)
- BestFeasSol[i] = 0;
- old_bas = new int[lp.rows + 1];
- System.arraycopy(lp.bas, 0, old_bas, 0, lp.rows + 1);
- old_lower = new short[lp.sum + 1];
- System.arraycopy(lp.lower, 0, old_lower, 0, lp.sum + 1);
-
- get_row(lp, 0, OrigObj);
-
- pie = 2;
-
- if(lp.maximise != FALSE)
- {
- Zub = DEF_INFINITE;
- Zlb = start_bound;
- }
- else
- {
- Zlb = -DEF_INFINITE;
- Zub = start_bound;
- }
- status = RUNNING;
- Step = 1;
- OrigFeas = FALSE;
- AnyFeas = FALSE;
- citer = 0;
-
- for(i = 0 ; i < lp.nr_lagrange; i++)
- lp.lambda[i] = 0;
-
- while(status == RUNNING)
- {
- citer++;
-
- for(i = 1; i <= lp.columns; i++)
- {
- ModObj[i] = OrigObj[i];
- for(j = 0; j < lp.nr_lagrange; j++)
- {
- if(lp.maximise != FALSE)
- ModObj[i] -= lp.lambda[j] * lp.lag_row[j][i];
- else
- ModObj[i] += lp.lambda[j] * lp.lag_row[j][i];
- }
- }
- for(i = 1; i <= lp.columns; i++)
- {
- set_mat(lp, 0, i, ModObj[i]);
- /* fSystem.out.print(stderr, "%f ", ModObj[i]); */
- }
- rhsmod = 0;
- for(i = 0; i < lp.nr_lagrange; i++)
- if(lp.maximise != FALSE)
- rhsmod += lp.lambda[i] * lp.lag_rhs[i];
- else
- rhsmod -= lp.lambda[i] * lp.lag_rhs[i];
-
- if(verbose != FALSE)
- {
- System.out.println("Zub: " + Zub + " Zlb: " + Zlb + " Step: " + Step +
- " pie: " + pie + " Feas " + OrigFeas);
- for(i = 0; i < lp.nr_lagrange; i++)
- System.out.println(i + " SubGrad " + SubGrad[i] + " lambda " + lp.lambda[i]);
- }
-
-
- result = solve(lp);
-
- same_basis = TRUE;
- i = 1;
- while(same_basis != FALSE && i < lp.rows)
- {
- same_basis = (old_bas[i] == lp.bas[i])? (short)1: (short)0;
- i++;
- }
- i = 1;
- while(same_basis != FALSE && i < lp.sum)
- {
- same_basis=(old_lower[i] == lp.lower[i])? (short)1:(short)0;
- i++;
- }
- if(same_basis == FALSE)
- {
- System.arraycopy(lp.lower, 0, old_lower, 0, lp.sum+1);
- System.arraycopy(lp.bas, 0, old_bas, 0, lp.rows+1);
- pie *= 0.95;
- }
-
- if(verbose != FALSE)
- System.out.println("result: " + result + " same basis: " + same_basis);
-
- if(result == UNBOUNDED)
- {
- for(i = 1; i <= lp.columns; i++)
- System.out.print(ModObj[i] + " ");
- System.exit(FAIL);
- }
-
- if(result == FAILURE)
- status = FAILURE;
-
- if(result == INFEASIBLE)
- status = INFEASIBLE;
-
- SqrsumSubGrad = 0;
- for(i = 0; i < lp.nr_lagrange; i++)
- {
- SubGrad[i]= -lp.lag_rhs[i];
- for(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 = TRUE;
- for(i = 0; i < lp.nr_lagrange; i++)
- if(lp.lag_con_type[i] != FALSE)
- {
- if(Math.abs(SubGrad[i]) > lp.epsb)
- OrigFeas = FALSE;
- }
- else if(SubGrad[i] > lp.epsb)
- OrigFeas = FALSE;
-
- if(OrigFeas != FALSE)
- {
- AnyFeas = TRUE;
- Ztmp = 0;
- for(i = 1; i <= lp.columns; i++)
- Ztmp += lp.best_solution[lp.rows + i] * OrigObj[i];
- if((lp.maximise != FALSE) && (Ztmp > Zlb))
- {
- Zlb = Ztmp;
- for(i = 1; i <= lp.sum; i++)
- BestFeasSol[i] = lp.best_solution[i];
- BestFeasSol[0] = Zlb;
- if(verbose != FALSE)
- System.out.println("Best feasible solution: " + Zlb);
- }
- else if(Ztmp < Zub)
- {
- Zub = Ztmp;
- for(i = 1; i <= lp.sum; i++)
- BestFeasSol[i] = lp.best_solution[i];
- BestFeasSol[0] = Zub;
- if(verbose != FALSE)
- System.out.println("Best feasible solution: " + Zub);
- }
- }
-
- if(lp.maximise != FALSE)
- Zub = Math.min(Zub, rhsmod + lp.best_solution[0]);
- else
- Zlb = Math.max(Zlb, rhsmod + lp.best_solution[0]);
-
- if(Math.abs(Zub-Zlb) < (float)0.001)
- {
- status = OPTIMAL;
- }
- Step = (float)(pie * ((1.05*Zub) - Zlb) / SqrsumSubGrad);
-
- for(i = 0; i < lp.nr_lagrange; i++)
- {
- lp.lambda[i] += Step * SubGrad[i];
- if(lp.lag_con_type[i] == FALSE && lp.lambda[i] < 0)
- lp.lambda[i] = 0;
- }
-
- if(citer == num_iter && status==RUNNING)
- if(AnyFeas != FALSE)
- status = FEAS_FOUND;
- else
- status = NO_FEAS_FOUND;
- }
-
- for(i = 0; i <= lp.sum; i++)
- lp.best_solution[i] = BestFeasSol[i];
-
- for(i = 1; i <= lp.columns; i++)
- set_mat(lp, 0, i, OrigObj[i]);
-
- if(lp.maximise != FALSE)
- lp.lag_bound = Zub;
- else
- lp.lag_bound = Zlb;
- return(status);
- }
-
- } // end of class solve
-
-
- public static class Matrix {
- public int row_nr;
- public float value;
- public Matrix(int r, float v) { row_nr = r; value = v; }
- }
-
-
- public static class Problem {
- String lp_name; /* the name of the lp */
-
- public short active; /*TRUE if the globals point to this structure*/
- public short verbose; /* ## Verbose flag */
- public short debug; /* ## Print B&B information */
- public short trace; /* ## Print information on pivot selection */
- public short anti_degen; /* ## Do perturbations */
-
- public int rows; /* Nr of constraint rows in the problem */
- int rows_alloc; /* The allocated memory for Rows sized data */
- int columns; /* The number of columns (= variables) */
- int columns_alloc;
- int sum; /* The size of the variables + the slacks */
- int sum_alloc;
-
- short names_used; /* Flag to indecate if names for rows and
- columns are used */
- String[] row_name; /* rows_alloc+1 */
- int[] col_name; /* columns_alloc+1 */
-
- /* Row[0] of the sparce matrix is the objective function */
-
- int non_zeros; /* The number of elements in the sparce matrix*/
- int mat_alloc; /* The allocated size for matrix sized
- structures */
- Matrix[] mat; /* mat_alloc :The sparse matrix */
- Matrix[] alternate_mat; /* mat_alloc :The sparse matrix */
- int[] col_end; /* columns_alloc+1 :Cend[i] is the index of the
- first element after column i.
- column[i] is stored in elements
- col_end[i-1] to col_end[i]-1 */
- int[] col_no; /* mat_alloc :From Row 1 on, col_no contains the
- column nr. of the
- nonzero elements, row by row */
- short row_end_valid; /* true if row_end & col_no are valid */
- int[] row_end; /* rows_alloc+1 :row_end[i] is the index of the
- first element in Colno after row i */
- float[] orig_rh; /* rows_alloc+1 :The RHS after scaling & sign
- changing, but before `Bound transformation' */
- float[] rh; /* rows_alloc+1 :As orig_rh, but after Bound
- transformation */
- float[] rhs; /* rows_alloc+1 :The RHS of the curent simplex
- tableau */
- float[] orig_upbo; /* sum_alloc+1 :Bound before transformations */
- float[] orig_lowbo; /* " " */
- float[] upbo; /* " " :Upper bound after transformation
- & B&B work*/
- float[] lowbo; /* " " :Lower bound after transformation
- & B&B work */
-
- short basis_valid; /* TRUE is the basis is still valid */
- int[] bas; /* rows_alloc+1 :The basis column list */
- short[] basis; /* sum_alloc+1 : basis[i] is TRUE if the column
- is in the basis */
- short[] lower; /* " " :TRUE is the variable is at its
- lower bound (or in the basis), it is FALSE
- if the variable is at its upper bound */
-
- short eta_valid; /* TRUE if current Eta structures are valid */
- int eta_alloc; /* The allocated memory for Eta */
- int eta_size; /* The number of Eta columns */
- int num_inv; /* The number of float pivots */
- int max_num_inv; /* ## The number of float pivots between
- reinvertions */
- float[] eta_value; /* eta_alloc :The Structure containing the
- values of Eta */
- int[] eta_row_nr; /* " " :The Structure containing the Row
- indexes of Eta */
- int[] eta_col_end; /* rows_alloc + MaxNumInv : eta_col_end[i] is
- the start index of the next Eta column */
-
- short bb_rule; /* what rule for selecting B&B variables */
-
- short break_at_int; /* TRUE if stop at first integer better than
- break_value */
- float break_value;
-
- float obj_bound; /* ## Objective function bound for speedup of
- B&B */
- int iter; /* The number of iterations in the simplex
- solver (LP) */
- int total_iter; /* The total number of iterations (B&B) (ILP)*/
- int max_level; /* The Deepest B&B level of the last solution */
- int total_nodes; /* total number of nodes processed in b&b */
- public float[] solution; /* sum_alloc+1 :The Solution of the last LP,
- 0 = The Optimal Value,
- 1..rows The Slacks,
- rows+1..sum The Variables */
- public float[] best_solution; /* " " :The Best 'Integer' Solution */
- float[] duals; /* rows_alloc+1 :The dual variables of the
- last LP */
-
- short maximise; /* TRUE if the goal is to maximise the
- objective function */
- short floor_first; /* TRUE if B&B does floor bound first */
- short[] ch_sign; /* rows_alloc+1 :TRUE if the Row in the matrix
- has changed sign
- (a`x > b, x>=0) is translated to
- s + -a`x = -b with x>=0, s>=0) */
-
- short scaling_used; /* TRUE if scaling is used */
- short columns_scaled; /* TRUE is the columns are scaled too, Only use
- if all variables are non-integer */
- float[] scale; /* sum_alloc+1 :0..Rows the scaling of the Rows,
- Rows+1..Sum the scaling of the columns */
-
- int nr_lagrange; /* Nr. of Langrangian relaxation constraints */
- float[][]lag_row; /* NumLagrange, columns+1:Pointer to pointer of
- rows */
- float[] lag_rhs; /* NumLagrange :Pointer to pointer of Rhs */
- float[] lambda; /* NumLagrange :Lambda Values */
- short[] lag_con_type; /* NumLagrange :TRUE if constraint type EQ */
- float lag_bound; /* the lagrangian lower bound */
-
- short valid; /* Has this lp pased the 'test' */
- float infinite; /* ## numercal stuff */
- float epsilon; /* ## */
- float epsb; /* ## */
- float epsd; /* ## */
- float epsel; /* ## */
-
-
- public Problem (int nrows, int ncolumns, int matalloc) {
- int i, nsum;
- nsum=nrows+ncolumns;
- rows=nrows;
- columns=ncolumns;
- sum=nsum;
- rows_alloc=rows;
- columns_alloc=columns;
- sum_alloc=sum;
- mat_alloc=matalloc;
- eta_alloc=10000;
- max_num_inv=DEFNUMINV;
- col_no = new int[mat_alloc];
- col_end = new int[columns + 1];
- row_end = new int[rows + 1];
- orig_rh = new float[rows + 1];
- rh = new float[rows + 1];
- rhs = new float[rows + 1];
- orig_upbo = new float[sum + 1];
- upbo = new float[sum + 1];
- orig_lowbo = new float[sum + 1];
- lowbo = new float[sum + 1];
- bas = new int[rows+1];
- basis = new short[sum + 1];
- lower = new short[sum + 1];
- eta_value = new float[eta_alloc];
- eta_row_nr = new int[eta_alloc];
- eta_col_end = new int[rows_alloc + max_num_inv];
- solution = new float[sum + 1];
- best_solution = new float[sum + 1];
- duals = new float[rows + 1];
- ch_sign = new short[rows + 1];
- mat = new Matrix[mat_alloc];
- for(int j=0; j<mat.length; j++) mat[j] = new Matrix(0, 0);
- alternate_mat = new Matrix[mat_alloc];
- for(int j=0; j<alternate_mat.length; j++) alternate_mat[j] = new Matrix(0, 0);