demo/lp_demo.cc
author alpar
Mon, 24 Oct 2005 08:09:59 +0000
changeset 1734 2fb5ceac10e7
parent 1636 260ac104190f
child 1875 98698b69a902
permissions -rw-r--r--
- dijkstraZero() added. (Until we conclude how to handle the related problem.)
- processed() query function added.
athos@1577
     1
/* -*- C++ -*-
ladanyi@1636
     2
 * demo/lp_demo.cc - Part of LEMON, a generic C++ optimization library
athos@1577
     3
 *
athos@1577
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
athos@1577
     5
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
athos@1577
     6
 *
athos@1577
     7
 * Permission to use, modify and distribute this software is granted
athos@1577
     8
 * provided that this copyright notice appears in all copies. For
athos@1577
     9
 * precise terms see the accompanying LICENSE file.
athos@1577
    10
 *
athos@1577
    11
 * This software is provided "AS IS" with no warranty of any kind,
athos@1577
    12
 * express or implied, and with no claim as to its suitability for any
athos@1577
    13
 * purpose.
athos@1577
    14
 *
athos@1577
    15
 */
athos@1577
    16
athos@1577
    17
/// \ingroup demos
athos@1577
    18
/// \file
athos@1577
    19
/// \brief A program demonstrating the LEMON LP solver interface
athos@1577
    20
///
athos@1577
    21
/// This program is a simple application of the LEMON LP solver
athos@1577
    22
/// interface: we formulate a linear programming (LP) problem and then
athos@1577
    23
/// solve it using the underlying solver (GLPK or CPLEX for
athos@1577
    24
/// example). For the detailed documentation of the LEMON LP solver
athos@1577
    25
/// interface read \ref lemon::LpSolverBase "this".
alpar@1641
    26
///
alpar@1641
    27
/// \include lp_demo.cc
athos@1577
    28
alpar@1610
    29
#include <lemon/lp.h>
ladanyi@1387
    30
alpar@1362
    31
#include <iostream>
alpar@1381
    32
alpar@1362
    33
using namespace lemon;
alpar@1362
    34
alpar@1362
    35
int main()
alpar@1362
    36
{     
alpar@1362
    37
 //The following example is taken from the documentation of the GLPK library.
alpar@1362
    38
 //See it in the GLPK reference manual and among the GLPK sample files (sample.c)
athos@1530
    39
athos@1530
    40
  //A default solver is taken
alpar@1610
    41
  Lp lp;
alpar@1610
    42
  typedef Lp::Row Row;
alpar@1610
    43
  typedef Lp::Col Col;
athos@1513
    44
  
alpar@1362
    45
athos@1577
    46
  std::cout<<"A program demonstrating the LEMON LP solver interface"<<std::endl; 
athos@1577
    47
  std::cout<<"Solver used: "<<default_solver_name<<std::endl;
athos@1577
    48
athos@1513
    49
  //This will be a maximization
alpar@1362
    50
  lp.max();
alpar@1362
    51
athos@1513
    52
  //We add coloumns (variables) to our problem
alpar@1362
    53
  Col x1 = lp.addCol();
alpar@1362
    54
  Col x2 = lp.addCol();
alpar@1362
    55
  Col x3 = lp.addCol();
alpar@1362
    56
alpar@1362
    57
  //Constraints
alpar@1362
    58
  lp.addRow(x1+x2+x3 <=100);  
alpar@1362
    59
  lp.addRow(10*x1+4*x2+5*x3<=600);  
alpar@1362
    60
  lp.addRow(2*x1+2*x2+6*x3<=300);  
alpar@1362
    61
  //Nonnegativity of the variables
alpar@1362
    62
  lp.colLowerBound(x1, 0);
alpar@1362
    63
  lp.colLowerBound(x2, 0);
alpar@1362
    64
  lp.colLowerBound(x3, 0);
alpar@1362
    65
  //Objective function
alpar@1362
    66
  lp.setObj(10*x1+6*x2+4*x3);
alpar@1362
    67
  
athos@1513
    68
  //Call the routine of the underlying LP solver
alpar@1362
    69
  lp.solve();
alpar@1362
    70
athos@1513
    71
  //Print results
alpar@1362
    72
  if (lp.primalStatus()==LpSolverBase::OPTIMAL){
athos@1577
    73
    std::cout<<"Optimal solution found!"<<std::endl;
athos@1577
    74
    printf("optimum value = %g; x1 = %g; x2 = %g; x3 = %g\n", 
alpar@1362
    75
	   lp.primalValue(), 
alpar@1362
    76
	   lp.primal(x1), lp.primal(x2), lp.primal(x3));
alpar@1362
    77
  }
alpar@1362
    78
  else{
alpar@1362
    79
    std::cout<<"Optimal solution not found!"<<std::endl;
alpar@1362
    80
  }
alpar@1362
    81
athos@1530
    82
  //End of LEMON style code
alpar@1362
    83
alpar@1362
    84
  //Here comes the same problem written in C using GLPK API routines
alpar@1362
    85
alpar@1362
    86
//   LPX *lp;
alpar@1362
    87
//       int ia[1+1000], ja[1+1000];
alpar@1362
    88
//       double ar[1+1000], Z, x1, x2, x3;
alpar@1362
    89
// s1:   lp = lpx_create_prob();
alpar@1362
    90
// s2:   lpx_set_prob_name(lp, "sample");
alpar@1362
    91
// s3:   lpx_set_obj_dir(lp, LPX_MAX);
alpar@1362
    92
// s4:   lpx_add_rows(lp, 3);
alpar@1362
    93
// s5:   lpx_set_row_name(lp, 1, "p");
alpar@1362
    94
// s6:   lpx_set_row_bnds(lp, 1, LPX_UP, 0.0, 100.0);
alpar@1362
    95
// s7:   lpx_set_row_name(lp, 2, "q");
alpar@1362
    96
// s8:   lpx_set_row_bnds(lp, 2, LPX_UP, 0.0, 600.0);
alpar@1362
    97
// s9:   lpx_set_row_name(lp, 3, "r");
alpar@1362
    98
// s10:  lpx_set_row_bnds(lp, 3, LPX_UP, 0.0, 300.0);
alpar@1362
    99
// s11:  lpx_add_cols(lp, 3);
alpar@1362
   100
// s12:  lpx_set_col_name(lp, 1, "x1");
alpar@1362
   101
// s13:  lpx_set_col_bnds(lp, 1, LPX_LO, 0.0, 0.0);
alpar@1362
   102
// s14:  lpx_set_obj_coef(lp, 1, 10.0);
alpar@1362
   103
// s15:  lpx_set_col_name(lp, 2, "x2");
alpar@1362
   104
// s16:  lpx_set_col_bnds(lp, 2, LPX_LO, 0.0, 0.0);
alpar@1362
   105
// s17:  lpx_set_obj_coef(lp, 2, 6.0);
alpar@1362
   106
// s18:  lpx_set_col_name(lp, 3, "x3");
alpar@1362
   107
// s19:  lpx_set_col_bnds(lp, 3, LPX_LO, 0.0, 0.0);
alpar@1362
   108
// s20:  lpx_set_obj_coef(lp, 3, 4.0);
alpar@1362
   109
// s21:  ia[1] = 1, ja[1] = 1, ar[1] =  1.0; /* a[1,1] =  1 */
alpar@1362
   110
// s22:  ia[2] = 1, ja[2] = 2, ar[2] =  1.0; /* a[1,2] =  1 */
alpar@1362
   111
// s23:  ia[3] = 1, ja[3] = 3, ar[3] =  1.0; /* a[1,3] =  1 */
alpar@1362
   112
// s24:  ia[4] = 2, ja[4] = 1, ar[4] = 10.0; /* a[2,1] = 10 */
alpar@1362
   113
// s25:  ia[5] = 3, ja[5] = 1, ar[5] =  2.0; /* a[3,1] =  2 */
alpar@1362
   114
// s26:  ia[6] = 2, ja[6] = 2, ar[6] =  4.0; /* a[2,2] =  4 */
alpar@1362
   115
// s27:  ia[7] = 3, ja[7] = 2, ar[7] =  2.0; /* a[3,2] =  2 */
alpar@1362
   116
// s28:  ia[8] = 2, ja[8] = 3, ar[8] =  5.0; /* a[2,3] =  5 */
alpar@1362
   117
// s29:  ia[9] = 3, ja[9] = 3, ar[9] =  6.0; /* a[3,3] =  6 */
alpar@1362
   118
// s30:  lpx_load_matrix(lp, 9, ia, ja, ar);
alpar@1362
   119
// s31:  lpx_simplex(lp);
alpar@1362
   120
// s32:  Z = lpx_get_obj_val(lp);
alpar@1362
   121
// s33:  x1 = lpx_get_col_prim(lp, 1);
alpar@1362
   122
// s34:  x2 = lpx_get_col_prim(lp, 2);
alpar@1362
   123
// s35:  x3 = lpx_get_col_prim(lp, 3);
alpar@1362
   124
// s36:  printf("\nZ = %g; x1 = %g; x2 = %g; x3 = %g\n", Z, x1, x2, x3);
alpar@1362
   125
// s37:  lpx_delete_prob(lp);
alpar@1362
   126
//       return 0;
alpar@1362
   127
alpar@1362
   128
  return 0;
alpar@1362
   129
}