COIN-OR::LEMON - Graph Library

Changeset 55:edb7d5759e0d in lemon-tutorial


Ignore:
Timestamp:
03/01/10 02:27:36 (8 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Greatly extend LP section

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lp.dox

    r50 r55  
    4545quite easily. 
    4646 
    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. 
    51  
    52 \code 
    53   Lp lp; 
    54  
    55   Lp::Col x1 = lp.addCol(); 
    56   Lp::Col x2 = lp.addCol(); 
    57  
    58   lp.addRow(0 <= x1 + x2 <= 100); 
    59   lp.addRow(2 * x1 <= x2 + 32); 
    60  
    61   lp.colLowerBound(x1, 0); 
    62   lp.colUpperBound(x2, 100); 
    63  
    64   lp.max(); 
    65   lp.obj(10 * x1 + 6 * x2); 
    66   lp.solve(); 
    67  
    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 
    72  
    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 
     48 
     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 lp_demo.cc. 
     51 
     52\dontinclude lp_demo.cc 
     53\skip Create 
     54\until } 
     55\until } 
     56 
     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. 
    79  
     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()". 
     68 
     69The above problem has an optimal solution. If you execute this example, 
     70it will print out the following results. 
     71 
     72\code 
     73  Objective function value: 67.5 
     74  x1 = 7.5 
     75  x2 = 10 
     76\endcode 
     77 
     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. 
     82 
     83\code 
     84  Optimal solution found. 
     85\endcode 
     86 
     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 
     90\code 
     91  lp.addRow(x1 - 5 <= x2); 
     92\endcode 
     93can also be written as 
     94\code 
     95  Lp::Expr e1, e2; 
     96  e1 = x1; 
     97  e1 -= 5; 
     98  e2 = x2; 
     99  Lp::Constr c = e1 <= e2; 
     100  lp.addRow(c); 
     101\endcode 
     102 
     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. 
     107 
     108\code 
     109  Lp::Expr sum; 
     110  for (Lp::ColIt col(lp); col != INVALID; ++col) { 
     111    sum += col; 
     112  } 
     113\endcode 
     114 
     115After solving the problem, you can query the value of any primal expression, 
     116not just the individual columns and the objective function. 
     117 
     118\todo Check this example after closing ticket #326. 
     119 
     120\code 
     121  std::cout << lp.primal(sum) << std::endl; 
     122\endcode 
     123 
     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. 
     127 
     128\code 
     129  Lp::Row r = lp.addRow(x2 >= 3); 
     130\endcode 
     131 
     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). 
     135 
     136\code 
     137  std::cout << lp.dual(r) << std::endl; 
     138\endcode 
     139 
     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. 
     142 
     143\code 
     144  Lp::DualExpr dual_sum; 
     145  for (Lp::RowIt row(lp); row != INVALID; ++row) { 
     146    dual_sum += row; 
     147  } 
     148\endcode 
     149 
     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. 
     153 
     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. 
     157 
     158 
     159[SEC]sec_lp_mip[SEC] Mixed Integer Programming 
     160 
     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. 
     165 
     166The following example demonstrates the usage of the MIP solver interface. 
     167The whole program can be found in \ref mip_demo.cc. 
     168 
     169\dontinclude mip_demo.cc 
     170\skip Create 
     171\until } 
     172\until } 
     173 
     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 lp_demo.cc? 
     177 
     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. 
     181 
     182\code 
     183  // Set the type of the columns 
     184  mip.colType(x1, Mip::INTEGER); 
     185  mip.colType(x2, Mip::REAL); 
     186\endcode 
     187 
     188Because of this integrality requirement, the results will be different 
     189from the LP solution. 
     190 
     191\code 
     192  Objective function value: 67 
     193  x1 = 8 
     194  x2 = 9 
     195\endcode 
     196 
     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. 
     201 
     202 
     203[SEC]sec_lp_optimization[SEC] Solving Complex Optimization Problems 
     204 
     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). 
    84  
    85 \code 
    86   Lp lp; 
    87   ListDigraph::ArcMap<Lp::Col> f(g); 
    88   lp.addColSet(f); 
    89  
    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   } 
    95  
    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   } 
    104  
    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]; 
    109  
    110   lp.max(); 
    111   lp.obj(o); 
    112   lp.solve(); 
    113  
    114   std::cout << "Max flow value: " << lp.primal() << std::endl; 
    115 \endcode 
     208programming, see the whole program in \re lp_maxflow_demo.cc. 
     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).  
     213 
     214\dontinclude lp_maxflow_demo.cc 
     215\skip DIGRAPH_TYPEDEFS 
     216\until solve() 
     217 
     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". 
    116221 
    117222[TRAILER] 
  • 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.