import qs.*; 

The Problem class

Problem is the library's central class. It wraps all information about a linear programming problem as well as parameter data guiding qsopt's solver methods. It supports a host of methods to create, manipulate, and solve problems.

The remainder of this page explains how to read/write a problem from/to a file, solve a problem , access a solution , and build a problem through method calls.

How to read/write a problem from/to a file

   boolean isMpsFormat = true; 
   Problem prob = Problem.read("yourfile.mps", isMpsFormat);
   if (prob == null) {
      throw new QSException("Could not parse problem.");
   } 
   prob.write("yourfile.lp", !isMpsFormat);

It is a good habit to give LP format files the extension ".lp" and MPS format file the extension ".mps". Thus files are compatible with the conventions used by the Windows and Java graphical user interfaces.

See Pretty Printer application for a full program listing.

How to solve a problem

   Problem prob; 
   boolean doPrimal; 
   // acquire a problem from a file or 
   // build it from scratch using add_cols, add_rows, ...
   if (doPrimal) {
      prob.opt_primal();
   } else {
      prob.opt_dual();
   }

   if (doPrimal) { 
      prob.setparam(QS.PARAM_PRIMAL_PRICING_I, QS.PRIMAL_DANTZIG);
      prob.setparam(QS.PARAM_PRIMAL_PRICING_II, QS.PRIMAL_DEVEX);
   } else {
      prob.setparam(QS.PARAM_DUAL_PRICING_I, QS.DUAL_DANTZIG);
      prob.setparam(QS.PARAM_DUAL_PRICING_II, QS.DUAL_STEEP);
   }

Sometimes it is useful to watch the solver's progress. To do so turn on simplex tracing on:

   prob.setparam(QS.PARAM_SIMPLEX_DISPLAY, 1); 

   prob.setparam(QS.PARAM_SIMPLEX_DISPLAY, 0); 

   prob.setparam(QS.PARAM_SIMPLEX_MAX_ITERATIONS, somePositiveNumber); 

See Simple Solver application for a full program listing.

How to access a solution

A problem's solution is cached in the Problem class and remains available until the problem is changed. The following code excerpt shows how a solution is accessed:

   // a solution is available only if a previous solver run was successful
   // and the problem has not changed since
   if (prob.get_status() == QS.LP_OPTIMAL) {  
      double optimal = prob.get_objval();
   
      int nrows = prob.get_rowcount();
      double pi[] = new double[nrows];
      double slack[] = new double[nrows];
      String rows[] = new String[nrows];
	
      int ncols = prob.get_colcount();
      double x[] = new double[ncols];
      double rc[] = new double[ncols];

      prob.get_solution(x, pi, slack, rc);

      // now print this information for the human reader : 
      String cols[] = new String[ncols];
      prob.get_rownames(rows);
      prob.get_colnames(cols);

      System.out.println("Row information");
      for (int i = 0; i < nrows; i++) {
         if ((pi[i] != 0.0) || (slack[i] != 0.0)) {
	    System.out.println("\t" + rows[i] + ": pi = " + pi[i] + "; " +
                            "slack = " + slack[i]);
         }
      }
      System.out.println("Column information");
      for (int j = 0; j < ncols; j++) {
         if (x[j] != 0.0 || rc[j] != 0.0) {
	    System.out.println("\t" + cols[j] + ": x = " + x[j] + "; " +
                               "rc = " + rc[j]);
         }
      }

See Simple Solver application for a full program listing.

How to build a problem through method calls

Maximize  3.0x + 2.0y + 4.0z                   
Subject to                                     
   3.1x + 2.3y + 1.4z <= 12.2           
   5.0x + 1.1y         = 10.0           
   x >= 2.0                             
   y free                               
   1.0 <= z <= 10.0                     

By default qsopt minimizes the objective, therefore prob's objective sense needs to be changed on line 3.

Lines 5 to 9 define 2 rows, whose names default to "c1" and "c2". Their right hand sides and senses are defined by the two arrays rhs and sense on lines 5 and 6. An 'L' sense indicates that a row should be lower than its right hand side, an 'E' indicates equality, and a 'G' indicates that a row should be greater than its right hand side. Since the rows are initially empty matcnt and matbgn on lines 7 and 8 contain zeros.

The arrays on lines 14 to 21 define the problems variables, their names, and coefficients. There are three variables. names[i], obj[i], upper[i] and lower[i] define variable i's name, its coefficient in the objective function, its lower, and its upper bound. QS.MAXDOUBLE is used to indicate inifnity.

matcnt[i] defines in how many rows a variable appears with a non zero coefficient. The i-th variable's coefficients for the rows they appear in are stored in

   matval[matbgn[i]] ... matval[matbgn[i] + matcnt[i]-1]

   matind[matbgn[i]] ... matind[matbgn[i] + matcnt[i]-1]

   1   Problem prob = new Problem("define");
   2
   3   prob.change_objsense (QS.MIN); 
   4   { // add rows 2 rows and define their right hand sides 
   5      double rhs[] = { 12.2, 10.0 };
   6      char sense[] = { 'L', 'E' };
   7      int matcnt[] = { 0, 0, 0 };
   8      int matbgn[] = { 0, 0, 0 };
   9      prob.add_rows(2, matcnt, matbgn, null, null, rhs, sense, null);
  10   }
  11
  12   { // add variables x, y, z, add their coeffs to the rows, to objective 
  13     // define their bounds
  14      int matcnt[] = { 2, 2, 1};
  15      int matbgn[] = { 0, 2, 4 }; 
  16      int matind[] =  { 0, 1, 0, 1, 0 }; 
  17      double matval[] = { 3.1, 5.0, 2.3, 1.1, 1.4 };
  18      double obj[] = { 3.0, 2.0, 4.0};
  19      double lower[] = { 2.0, -QS.MAXDOUBLE, 1.0}; 
  20      double upper[] = { QS.MAXDOUBLE, QS.MAXDOUBLE, 10.0 }; 
  21      String names[] = { "x", "y", "z" };
  22      
  23      prob.add_cols(3, matcnt, matbgn, matind, matval, 
  24                       obj, lower, upper, names);
  24   }

See Define a Problem through method calls for a full program listing.