COIN-OR::LEMON - Graph Library

Changeset 55:edb7d5759e0d in lemon-tutorial

03/01/10 02:27:36 (8 years ago)
Peter Kovacs <kpeter@…>

Greatly extend LP section

2 edited


  • lp.dox

    r50 r55  
    4545quite easily. 
    47 In this section, we will show two examples. The first one shows how simple 
    48 it is to formalize and solve an LP problem in LEMON, while the second one 
    49 shows how LEMON facilitates solving network optimization problems using LP 
    50 solvers. 
    52 \code 
    53   Lp lp; 
    55   Lp::Col x1 = lp.addCol(); 
    56   Lp::Col x2 = lp.addCol(); 
    58   lp.addRow(0 <= x1 + x2 <= 100); 
    59   lp.addRow(2 * x1 <= x2 + 32); 
    61   lp.colLowerBound(x1, 0); 
    62   lp.colUpperBound(x2, 100); 
    64   lp.max(); 
    65   lp.obj(10 * x1 + 6 * x2); 
    66   lp.solve(); 
    68   std::cout << "Objective function value: " << lp.primal() << std::endl; 
    69   std::cout << "x1 = " << lp.primal(x1) << std::endl; 
    70   std::cout << "x2 = " << lp.primal(x2) << std::endl; 
    71 \endcode 
    73 \ref LpBase::Col "Lp::Col" type represents the variables in the LP problems, 
    74 while \ref LpBase::Row "Lp::Row" represents the constraints. The numerical 
    75 operators can be used to form expressions from columns and dual 
    76 expressions from rows. Due to the suitable operator overloads, 
    77 a problem can be described in C++ conveniently, directly as it is 
     47[SEC]sec_lp_basics[SEC] Basic LP Features 
     49The following example demonstrates how simple it is to formalize and solve 
     50an LP problem in LEMON. You can find the whole program in \ref 
     53\skip Create 
     54\until } 
     55\until } 
     57\ref LpBase::Col "Lp::Col" type represents the columns, i.e. the (primal) 
     58variables of the LP problem. The numerical operators can be used to form 
     59expressions from columns, which are required for specifying rows 
     60(constraints) and the objective function. Due to the suitable operator 
     61overloads, a problem can be described in C++ conveniently, directly as it is 
    7862expressed in mathematics. 
     63After specifying all the parameters of the problem, we can solve it using 
     64the \ref LpSolver::solve() "solve()" function. The status of the solution 
     65(namely OPTIMAL, UNBOUNDED, INFEASIBLE etc.) can be obtained using 
     66\ref LpSolver::primalType() "primalType()" and the results can be 
     67obtained using \ref LpSolver::primal() "primal()". 
     69The above problem has an optimal solution. If you execute this example, 
     70it will print out the following results. 
     73  Objective function value: 67.5 
     74  x1 = 7.5 
     75  x2 = 10 
     78However, if you, for example, removed the lines that specify the rows, 
     79you would obtain an LP problem, for which the objective function value 
     80is unbounded over the feasible solutions. Thus the program would print 
     81out this line. 
     84  Optimal solution found. 
     87If you would like to build linear expressions or constraints in more steps, 
     88then you can use the classes \ref LpBase::Expr "Lp::Expr" and 
     89\ref LpBase::Constr "Lp::Constr". For example, this line 
     91  lp.addRow(x1 - 5 <= x2); 
     93can also be written as 
     95  Lp::Expr e1, e2; 
     96  e1 = x1; 
     97  e1 -= 5; 
     98  e2 = x2; 
     99  Lp::Constr c = e1 <= e2; 
     100  lp.addRow(c); 
     103These classes make it easy to build more complex expressions and constraints, 
     104e.g. using loops. For example, we can sum all the variables (columns) in an 
     105expression using the \ref LpBase::ColIt "Lp::ColIt" iterator, which can be 
     106used the same as node and arc iterators for graphs. 
     109  Lp::Expr sum; 
     110  for (Lp::ColIt col(lp); col != INVALID; ++col) { 
     111    sum += col; 
     112  } 
     115After solving the problem, you can query the value of any primal expression, 
     116not just the individual columns and the objective function. 
     118\todo Check this example after closing ticket #326. 
     121  std::cout << lp.primal(sum) << std::endl; 
     124Of course, working with the dual problem is also supported by the LP 
     125interface. \ref LpBase::Row "Lp::Row" represents the rows, i.e. the dual 
     126variables of the LP problem. 
     129  Lp::Row r = lp.addRow(x2 >= 3); 
     132The dual solutions of an LP problem can be obtained using the functions 
     133\ref LpSolver::dualType() "dualType()" and \ref LpSolver::dual "dual()" 
     134(after solving the problem). 
     137  std::cout << lp.dual(r) << std::endl; 
     140\ref LpBase::DualExpr "Lp::DualExpr" can be used to build dual expressions 
     141from rows and \ref LpBase::RowIt "Lp::RowIt" can be used to list the rows. 
     144  Lp::DualExpr dual_sum; 
     145  for (Lp::RowIt row(lp); row != INVALID; ++row) { 
     146    dual_sum += row; 
     147  } 
     150The LP solver interface provides several other features, which are 
     151documented in the classes \ref LpBase and \ref LpSolver. 
     152For detailed documentation, see these classes in the reference manual. 
     154If you would like to use a specific solver instead of the default one, 
     155you can use \ref GlpkLp, \ref ClpLp, \ref CplexLp etc. instead of 
     156the class \ref Lp. 
     159[SEC]sec_lp_mip[SEC] Mixed Integer Programming 
     161LEMON also provides a similar high-level interface for mixed integer 
     162programming (MIP) solvers. The default MIP solver can be used through 
     163the class \ref Mip, while the concrete solvers are implemented in the 
     164classes \ref GlpkMip, \ref CbcMip, \ref CplexMip etc. 
     166The following example demonstrates the usage of the MIP solver interface. 
     167The whole program can be found in \ref 
     170\skip Create 
     171\until } 
     172\until } 
     174\todo Check this demo file after closing ticket #326. 
     175E.g. could we write <tt>mip.sol()</tt> instead of <tt>mip.solValue()</tt>? 
     176Or could we write <tt>primalValue()</tt> for \c Lp in \c 
     178In this program, the same problem is built as in the above example, 
     179with the exception that the variable \c x1 is specified to be 
     180\c INTEGER valued. \c x2 is set to \c REAL, which is the default option. 
     183  // Set the type of the columns 
     184  mip.colType(x1, Mip::INTEGER); 
     185  mip.colType(x2, Mip::REAL); 
     188Because of this integrality requirement, the results will be different 
     189from the LP solution. 
     192  Objective function value: 67 
     193  x1 = 8 
     194  x2 = 9 
     197The documnetation of the MIP solver interface can be found in the 
     198reference manual at the class \ref MipSolver. The common parts of the 
     199LP and MIP interfaces are docmented in their common ancestor class 
     200\ref LpBase. 
     203[SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems 
     205The LP and MIP solvers are powerful tools for solving various complex 
     206optimization problems, as well. 
    80207The following example solves a maximum flow problem with linear 
    81 programming. Several other graph optimization problems can also be 
    82 expressed as linear programs and this interface helps to solve them easily 
    83 (though usually not so efficiently as by a direct combinatorial method). 
    85 \code 
    86   Lp lp; 
    87   ListDigraph::ArcMap<Lp::Col> f(g); 
    88   lp.addColSet(f); 
    90   // Capacity constraints 
    91   for (ListDigraph::ArcIt a(g); a != INVALID; ++a) { 
    92     lp.colLowerBound(f[a], 0); 
    93     lp.colUpperBound(f[a], capacity[a]); 
    94   } 
    96   // Flow conservation constraints 
    97   for (ListDigraph::NodeIt n(g); n != INVALID; ++n) { 
    98     if (n == src || n == trg) continue; 
    99     Lp::Expr e; 
    100     for (ListDigraph::OutArcIt a(g,n); a != INVALID; ++a) e += f[a]; 
    101     for (ListDigraph::InArcIt a(g,n); a != INVALID; ++a) e -= f[a]; 
    102     lp.addRow(e == 0); 
    103   } 
    105   // Objective function 
    106   Lp::Expr o; 
    107   for (ListDigraph::OutArcIt a(g,src); a != INVALID; ++a) o += f[a]; 
    108   for (ListDigraph::InArcIt a(g,src); a != INVALID; ++a) o -= f[a]; 
    110   lp.max(); 
    111   lp.obj(o); 
    112   lp.solve(); 
    114   std::cout << "Max flow value: " << lp.primal() << std::endl; 
    115 \endcode 
     208programming, see the whole program in \re 
     209Several other graph optimization problems can also be expressed as 
     210linear programs and the interface provided in LEMON facilitates solving 
     211them easily (though usually not so efficiently as by a direct 
     212combinatorial method, if one exists).  
     215\skip DIGRAPH_TYPEDEFS 
     216\until solve() 
     218\note This problem can be solved much more efficiently using common 
     219combinatorial optimization methods, such as the \ref Preflow 
     220"preflow push-relabel algorithm". 
  • toc.txt

    r46 r55  
    3434** sec_other_adaptors 
    3535* sec_lp 
     36** sec_lp_basics 
     37** sec_lp_mip 
     38** sec_lp_optimization 
    3639* sec_lgf 
    3740* sec_tools 
Note: See TracChangeset for help on using the changeset viewer.