Example: Using a Starting Basis in an LP Problem

> Continuous Optimization > Solving LPs: Simplex Optimizers > Example: Using a Starting Basis in an LP Problem

Example: Using a Starting Basis in an LP Problem

Here is an approach mentioned in the section Tuning LP Performance, which is to start with an advanced basis. The following small example demonstrates an approach to setting a starting basis by hand.

Example ilolpex6.cpp

The example, ilolpex6.cpp, resembles one you may have studied in the ILOG CPLEX Getting Started manual, ilolpex1.cpp. This example differs from that one in these ways:

Arrays are constructed using the populatebycolumn method, and thus no command line arguments are needed to select a construction method.
In the main routine, the arrays cstat and rstat set the status of the initial basis.
After the problem data has been copied into the problem object, the basis is copied by a call to cplex.setBasisStatuses.
After the problem has been optimized, the iteration count is printed. For the given data and basis, the basis is optimal, so no iterations are required to optimize the problem.

The main program starts by declaring the environment and terminates by calling method end for the environment. The code in between is encapsulated in a try block that catches all Concert Technology exceptions and prints them to the C++ error stream cerr. All other exceptions are caught as well, and a simple error message is issued. Next the model object and the cplex object are constructed. The function populatebycolumn builds the problem object and, as noted earlier, cplex.setBasisStatuses copies the advanced starting basis.

The call to cplex.solve optimizes the problem, and the subsequent print of the iteration count demonstrates that the advanced basis took effect. In fact, this basis is immediately determined to be the optimal one, resulting in zero iterations being performed, in contrast to the behavior seen in the example program ilolpex1.cpp where the same model is solved without the use of an advanced basis.

Complete Program

The complete program, ilolpex6.cpp, appears here and online in the standard distribution

// -------------------------------------------------------------- -*- C++ -*-
// File: examples/src/ilolpex6.cpp 
// Version 9.0    
// --------------------------------------------------------------------------
//  Copyright (C) 1999-2003 by ILOG.
//  All Rights Reserved.
//  Permission is expressly granted to use this example in the
//  course of developing applications that use ILOG products.
// --------------------------------------------------------------------------
//
// ilolpex6.cpp - Illustrates that optimal basis can be copied and
//                used to start an optimization.

#include <ilcplex/ilocplex.h>
ILOSTLBEGIN


static void
   populatebycolumn (IloModel model, IloNumVarArray var, IloRangeArray rng);

int
main (int argc, char **argv)
{
   IloEnv   env;
   try {
      IloModel model(env, "example");

      IloNumVarArray var(env);
      IloRangeArray  rng(env);
      populatebycolumn (model, var, rng);

      IloCplex cplex(model);

      IloCplex::BasisStatusArray cstat(env), rstat(env);
      cstat.add(IloCplex::AtUpper);
      cstat.add(IloCplex::Basic);
      cstat.add(IloCplex::Basic);
      rstat.add(IloCplex::AtLower);
      rstat.add(IloCplex::AtLower);
      cplex.setBasisStatuses(cstat, var, rstat, rng);
      cplex.solve();

      cplex.out() << "Solution status = " << cplex.getStatus() << endl;
      cplex.out() << "Solution value  = " << cplex.getObjValue() << endl;
      cplex.out() << "Iteration count = " << cplex.getNiterations() << endl;

      IloNumArray vals(env);
      cplex.getValues(vals, var);
      env.out() << "Values        = " << vals << endl;
      cplex.getSlacks(vals, rng);
      env.out() << "Slacks        = " << vals << endl;
      cplex.getDuals(vals, rng);
      env.out() << "Duals         = " << vals << endl;
      cplex.getReducedCosts(vals, var);
      env.out() << "Reduced Costs = " << vals << endl;

      cplex.exportModel("lpex6.lp");
   }
   catch (IloException& e) {
      cerr << "Concert exception caught: " << e << endl;
   }
   catch (...) {
      cerr << "Unknown exception caught" << endl;
   }

   env.end();
   return 0;
}  // END main


static void
populatebycolumn (IloModel model, IloNumVarArray x, IloRangeArray c)
{
   IloEnv env = model.getEnv();

   IloObjective obj = IloMaximize(env);
   c.add(IloRange(env, -IloInfinity, 20.0));
   c.add(IloRange(env, -IloInfinity, 30.0));

   x.add(IloNumVar(obj(1.0) + c[0](-1.0) + c[1]( 1.0), 35.0, 40.0));
   x.add(obj(2.0) + c[0]( 1.0) + c[1](-3.0));
   x.add(obj(3.0) + c[0]( 1.0) + c[1]( 1.0));

   model.add(obj);
   model.add(c);
}  // END populatebycolumn

PREVIOUS NEXT