Adding Rows to a Problem: Example lpex3.c

INDEX PREVIOUS NEXT

This example illustrates how to develop your own solution algorithms with routines from the Callable Library. It also shows you how to add rows to a problem object. Here is the problem example lpex3 solves:

Minimize	c*x
subject to	Hx = d   Ax = b   1 x u
where	H =	( -1 0 1 0 1 0 0 0 )	d =	( -3 )
		( 1 -1 0 1 0 0 0 0 )		( 1 )
		( 0 1 -1 0 0 1 -1 0 )		( 4 )
		( 0 0 0 -1 0 -1 0 1 )		( 3 )
		( 0 0 0 0 -1 0 1 -1 )		( -5 )
	A =	( 2 1 -2 -1 2 -1 -2 -3 )	b =	( 4 )
		( 1 -3 2 3 -1 2 1 1 )		( -2 )
	c =	(-9 1 4 2 -8 2 8 12 )
	l =	( 0 0 0 0 0 0 0 0 )
	u =	(50 50 50 50 50 50 50 50 )

1. The ILOG CPLEX Network Optimizer is used to solve

   Minimize	c*x
   subject to	Hx = d  l x u

2. The constraints Ax=b are added to the problem, and the dual simplex optimizer is used to solve the new problem, starting at the optimal basis of the simpler network problem.

The example first calls CPXopenCPLEX to create the environment and then turns on the ILOG CPLEX screen indicator (CPX_PARAM_SCRIND). Next it sets the simplex display level (CPX_PARAM_SIMDISPLAY) to 2 to indicate iteration-by-iteration output, so that the progress of each iteration of the hybrid optimizer can be observed. Setting this parameter to 2 is not generally recommended; the example does so only for illustrative purposes.

The example creates a problem object by a call to CPXcreateprob. Then the network data is copied via a call to CPXcopylp. After the network data is copied, the parameter CPX_PARAM_LPMETHOD is set to CPX_ALG_NET and the routine CPXlpopt is called to solve the network part of the optimization problem using the network optimizer. The objective value of this problem is retrieved by CPXgetobjval.

Then the extra rows are added by calling CPXaddrows. For convenience, the total number of nonzeros in the rows being added is stored in an extra element of the array rmatbeg, and this element is passed for the parameter nzcnt. The name arguments to CPXaddrows are NULL, since no variable or constraint names were defined for this problem.

After the CPXaddrows call, parameter CPX_PARAM_LPMETHOD is set to CPX_ALG_DUAL and the routine CPXlpopt is called to re-optimize the problem using the dual simplex optimizer. After re-optimization, CPXsolution is called to determine the solution status, the objective value, and the primal solution. NULL is passed for the other solution values, since they are not printed by this example.

At the end, the problem is written as a SAV file by CPXwriteprob. This file can then be read into the ILOG CPLEX Interactive Optimizer to analyze whether the problem was correctly generated. Using a SAV file is recommended over MPS and LP files, as SAV files preserve the full numeric precision of the problem.

After the TERMINATE: label, CPXfreeprob releases the problem object, and CPXcloseCPLEX releases the ILOG CPLEX environment.

/*------------------------------------------------------------------------*/
/*  File: examples/src/lpex3.c                                            */
/*  Version 9.0                                                           */
/*------------------------------------------------------------------------*/
/*  Copyright (C) 1997-2003 by ILOG.                                      */
/*  All Rights Reserved.                                                  */
/*  Permission is expressly granted to use this example in the            */
/*  course of developing applications that use ILOG products.             */
/*------------------------------------------------------------------------*/

/* lpex3.c, example of using CPXaddrows to solve a problem */

/* Bring in the CPLEX function declarations and the C library 
   header file stdio.h with the following single include. */

#include <ilcplex/cplex.h>

/* Bring in the declarations for the string functions */

#include <stdio.h>
#include <stdlib.h>

/* Modified example from Chvatal, "Linear Programming", Chapter 26.
 *   minimize  c*x
 *   subject to  Hx = d
 *               Ax = b
 *               l <= x <= u
 *   where
 *
 *   H = ( -1  0  1  0  1  0  0  0 )  d = ( -3 )
 *       (  1 -1  0  1  0  0  0  0 )      (  1 )
 *       (  0  1 -1  0  0  1 -1  0 )      (  4 )
 *       (  0  0  0 -1  0 -1  0  1 )      (  3 )
 *       (  0  0  0  0 -1  0  1 -1 )      ( -5 )
 *
 *   A = (  2  1 -2 -1  2 -1 -2 -3 )  b = (  4 )
 *       (  1 -3  2  3 -1  2  1  1 )      ( -2 )
 *
 *   c = ( -9  1  4  2 -8  2  8 12 ) 
 *   l = (  0  0  0  0  0  0  0  0 )
 *   u = ( 50 50 50 50 50 50 50 50 )
 *
 *
 *
 *  Treat the constraints with A as the complicating constraints, and
 *  the constraints with H as the "simple" problem.
 *  
 *  The idea is to solve the simple problem first, and then add the
 *  constraints for the complicating constraints, and solve with dual.
 *
 */


#define  COLSORIG  8
#define  ROWSSUB   5
#define  NZSUB     (2*COLSORIG)
#define  ROWSCOMP  2
#define  NZCOMP    (ROWSCOMP*COLSORIG)
#define  ROWSTOT   (ROWSSUB+ROWSCOMP)
#define  NZTOT     (NZCOMP+NZSUB)


int
main()
{
   /* Data for original problem.  Arrays have to be big enough to hold
      problem plus additional constraints.  */

   double  Hrhs[ROWSTOT]     = { -3, 1, 4, 3, -5};
   double  Hlb[COLSORIG]     = { 0, 0, 0, 0, 0, 0, 0, 0};
   double  Hub[COLSORIG]     = { 50, 50, 50, 50, 50, 50, 50, 50 };
   double  Hcost[COLSORIG]   = { -9,  1,  4, 2, -8,  2,  8,  12 };
   char    Hsense[ROWSTOT]   = { `E', `E', `E', `E', `E' };
   int     Hmatbeg[COLSORIG] = { 0, 2, 4, 6, 8, 10, 12, 14};
   int     Hmatcnt[COLSORIG] = { 2, 2, 2, 2, 2, 2, 2, 2};
   int     Hmatind[NZTOT]    = { 0, 1, 1, 2, 0, 2, 1, 3, 
                                 0, 4, 2, 3, 2, 4, 3, 4};
   double  Hmatval[NZTOT]    = { -1.0, 1.0, -1.0, 1.0, 1.0, -1.0, 1.0, -1.0,
                                 1.0, -1.0, 1.0, -1.0, -1.0, 1.0, 1.0, -1.0 };

   /* Data for CPXaddrows call */

   double  Arhs[ROWSCOMP]    = { 4, -2};
   char    Asense[ROWSCOMP]  = { `E', `E' };
   /* Note - use a trick for rmatbeg by putting the total nonzero count in 
             the last element.  This is not required by the CPXaddrows call. */
   int     Armatbeg[ROWSCOMP+1] = { 0, 8, 16};
   int     Armatind[NZCOMP]   = { 0, 1, 2, 3, 4, 5, 6, 7,  
                                  0, 1, 2, 3, 4, 5, 6, 7  };
   double  Armatval[NZCOMP]   = {  2.0,  1.0, -2.0, -1.0,  
                                   2.0, -1.0, -2.0, -3.0,
                                   1.0, -3.0,  2.0,  3.0, 
                                  -1.0,  2.0,  1.0,  1.0 };

   double        x[COLSORIG];

   CPXENVptr     env = NULL;
   CPXLPptr      lp = NULL;

   int           j;
   int           status, lpstat;
   double        objval;

   /* Initialize the CPLEX environment */

   env = CPXopenCPLEX (&status);

   /* If an error occurs, the status value indicates the reason for
      failure.  A call to CPXgeterrorstring will produce the text of
      the error message.  Note that CPXopenCPLEX produces no output,
      so the only way to see the cause of the error is to use
      CPXgeterrorstring.  For other CPLEX routines, the errors will
      be seen if the CPX_PARAM_SCRIND indicator is set to CPX_ON.  */

   if ( env == NULL ) {
      char  errmsg[1024];
      fprintf (stderr, "Could not open CPLEX environment.\n");
      CPXgeterrorstring (env, status, errmsg);
      fprintf (stderr, "%s", errmsg);
      goto TERMINATE;
   }

   /* Turn on output to the screen */

   status = CPXsetintparam (env, CPX_PARAM_SCRIND, CPX_ON);
   if ( status ) {
      fprintf (stderr, 
               "Failure to turn on screen indicator, error %d.\n", status);
      goto TERMINATE;
   }

   status = CPXsetintparam (env, CPX_PARAM_SIMDISPLAY, 2);
   if ( status ) {
      fprintf (stderr,"Failed to turn up simplex display level.\n");
      goto TERMINATE;
   }

   /* Create the problem */

   lp = CPXcreateprob (env, &status, "chvatal");
   
   if ( lp == NULL ) {
      fprintf (stderr,"Failed to create subproblem\n");
      status = 1;
      goto TERMINATE;
   }

   /* Copy network part of problem.  */

   status = CPXcopylp (env, lp, COLSORIG, ROWSSUB, CPX_MIN, Hcost, Hrhs, 
                       Hsense, Hmatbeg, Hmatcnt, Hmatind, Hmatval, 
                       Hlb, Hub, NULL);

   if ( status ) {
      fprintf (stderr, "CPXcopylp failed.\n");
      goto TERMINATE;
   }


   status = CPXsetintparam (env, CPX_PARAM_LPMETHOD, CPX_ALG_NET);
   if ( status ) {
      fprintf (stderr, 
               "Failed to set the optimization method, error %d.\n", status);
      goto TERMINATE;
   }

   status = CPXlpopt (env, lp);
   if ( status ) {
      fprintf (stderr, "Failed to optimize LP.\n");
      goto TERMINATE;
   }

   status = CPXgetobjval (env, lp, &objval);
   if ( status ) {
      fprintf (stderr,"CPXgetobjval failed\n");
      goto TERMINATE;
   }

   printf ("After network optimization, objective is %.10g\n", objval);

   /* Now add the extra rows to the problem.  */

   status = CPXaddrows (env, lp, 0, ROWSCOMP, Armatbeg[ROWSCOMP], 
                        Arhs, Asense, Armatbeg, Armatind, Armatval, 
                        NULL, NULL);
   if ( status ) {
      fprintf (stderr,"CPXaddrows failed.\n");
      goto TERMINATE;
   }

   /* Because the problem is dual feasible with the rows added, using
      the dual simplex method is indicated.  */

   status = CPXsetintparam (env, CPX_PARAM_LPMETHOD, CPX_ALG_DUAL);
   if ( status ) {
      fprintf (stderr, 
               "Failed to set the optimization method, error %d.\n", status);
      goto TERMINATE;
   }

   status = CPXlpopt (env, lp);
   if ( status ) {
      fprintf (stderr, "Failed to optimize LP.\n");
      goto TERMINATE;
   }

   status = CPXsolution (env, lp, &lpstat, &objval, x, NULL, NULL, NULL);
   if ( status ) {
      fprintf (stderr,"CPXsolution failed.\n");
      goto TERMINATE;
   }

   printf ("Solution status %d\n",lpstat);
   printf ("Objective value %g\n",objval);
   printf ("Solution is:\n");
   for (j = 0; j < COLSORIG; j++) {
      printf ("x[%d] = %g\n",j,x[j]);
   }

   /* Put the problem and basis into a SAV file to use it in the
    * Interactive Optimizer and see if problem is correct */

   status = CPXwriteprob (env, lp, "lpex3.sav", NULL);
   if ( status ) {
      fprintf (stderr, "CPXwriteprob failed.\n");
      goto TERMINATE;
   }
   
TERMINATE:

   /* Free up the problem as allocated by CPXcreateprob, if necessary */

   if ( lp != NULL ) {
      status = CPXfreeprob (env, &lp);
      if ( status ) {
         fprintf (stderr, "CPXfreeprob failed, error code %d.\n", status);
      }
   }

   /* Free up the CPLEX environment, if necessary */

   if ( env != NULL ) {
      status = CPXcloseCPLEX (&env);

      /* Note that CPXcloseCPLEX produces no output,
         so the only way to see the cause of the error is to use
         CPXgeterrorstring.  For other CPLEX routines, the errors will
         be seen if the CPX_PARAM_SCRIND indicator is set to CPX_ON. */

      if ( status ) {
         char  errmsg[1024];
         fprintf (stderr, "Could not close CPLEX environment.\n");
         CPXgeterrorstring (env, status, errmsg);
         fprintf (stderr, "%s", errmsg);
      }
   }
     
   return (status);

} /* END main */