COIN-OR::LEMON - Graph Library

Changeset 55:edb7d5759e0d in lemon-tutorial


Ignore:
Timestamp:
03/01/10 02:27:36 (14 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
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.