test/mip_test.cc
author kpeter
Mon, 18 Feb 2008 03:34:16 +0000
changeset 2577 2c6204d4b0f6
parent 2553 bfced05fa852
permissions -rw-r--r--
Add a cost scaling min cost flow algorithm.

Add a cost scaling algorithm, which is performing generalized
push-relabel operations. It is almost as efficient as the capacity
scaling algorithm, but slower than network simplex.
alpar@2391
     1
/* -*- C++ -*-
alpar@2391
     2
 *
alpar@2391
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@2391
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
alpar@2391
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391
     8
 *
alpar@2391
     9
 * Permission to use, modify and distribute this software is granted
alpar@2391
    10
 * provided that this copyright notice appears in all copies. For
alpar@2391
    11
 * precise terms see the accompanying LICENSE file.
alpar@2391
    12
 *
alpar@2391
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@2391
    14
 * express or implied, and with no claim as to its suitability for any
alpar@2391
    15
 * purpose.
alpar@2391
    16
 *
alpar@2391
    17
 */
alpar@2391
    18
athos@2149
    19
#include "test_tools.h"
athos@2146
    20
athos@2218
    21
athos@2221
    22
#ifdef HAVE_CONFIG_H
alpar@2571
    23
#include <lemon/config.h>
athos@2221
    24
#endif
athos@2221
    25
deba@2227
    26
#ifdef HAVE_CPLEX
deba@2227
    27
#include <lemon/mip_cplex.h>
deba@2227
    28
#endif
deba@2227
    29
deba@2227
    30
#ifdef HAVE_GLPK
deba@2227
    31
#include <lemon/mip_glpk.h>
deba@2227
    32
#endif
athos@2221
    33
athos@2218
    34
athos@2146
    35
using namespace lemon;
athos@2146
    36
athos@2218
    37
void solveAndCheck(MipSolverBase& lp, MipSolverBase::SolutionStatus stat, 
athos@2149
    38
		   double exp_opt) {
athos@2149
    39
  using std::string;
athos@2218
    40
athos@2149
    41
  lp.solve();
athos@2149
    42
  //int decimal,sign;
athos@2149
    43
  std::ostringstream buf;
deba@2441
    44
  buf << "Primalstatus should be: " << int(stat)<<" and it is "<<int(lp.mipStatus());
athos@2146
    45
athos@2218
    46
athos@2149
    47
  //  itoa(stat,buf1, 10);
athos@2213
    48
  check(lp.mipStatus()==stat, buf.str());
athos@2149
    49
athos@2218
    50
  if (stat ==  MipSolverBase::OPTIMAL) {
deba@2386
    51
    std::ostringstream sbuf;
athos@2149
    52
    buf << "Wrong optimal value: the right optimum is " << exp_opt; 
deba@2386
    53
    check(std::abs(lp.primalValue()-exp_opt) < 1e-3, sbuf.str());
athos@2149
    54
    //+ecvt(exp_opt,2)
athos@2149
    55
  }
athos@2149
    56
}
athos@2149
    57
athos@2218
    58
void aTest(MipSolverBase& mip)
athos@2149
    59
{
athos@2149
    60
 //The following example is very simple
athos@2149
    61
athos@2218
    62
athos@2218
    63
  typedef MipSolverBase::Row Row;
athos@2218
    64
  typedef MipSolverBase::Col Col;
athos@2218
    65
athos@2149
    66
athos@2149
    67
athos@2149
    68
  Col x1 = mip.addCol();
athos@2149
    69
  Col x2 = mip.addCol();
athos@2149
    70
athos@2149
    71
athos@2213
    72
  //Objective function
deba@2369
    73
  mip.obj(x1);
athos@2213
    74
athos@2213
    75
  mip.max();
athos@2213
    76
athos@2213
    77
athos@2213
    78
  //Unconstrained optimization
athos@2213
    79
  mip.solve();
athos@2213
    80
  //Check it out!
athos@2213
    81
athos@2149
    82
  //Constraints
athos@2149
    83
  mip.addRow(2*x1+x2 <=2);  
deba@2441
    84
  mip.addRow(x1-2*x2 <=0);
athos@2149
    85
athos@2149
    86
  //Nonnegativity of the variable x1
athos@2149
    87
  mip.colLowerBound(x1, 0);
athos@2149
    88
athos@2149
    89
  //Maximization of x1
athos@2221
    90
  //over the triangle with vertices (0,0),(4/5,2/5),(0,2)
athos@2149
    91
  double expected_opt=4.0/5.0;
athos@2218
    92
  solveAndCheck(mip, MipSolverBase::OPTIMAL, expected_opt);
athos@2149
    93
athos@2149
    94
  //Restrict x2 to integer
athos@2267
    95
  mip.colType(x2,MipSolverBase::INT);  
athos@2149
    96
  expected_opt=1.0/2.0;
athos@2218
    97
  solveAndCheck(mip, MipSolverBase::OPTIMAL, expected_opt);
athos@2149
    98
athos@2149
    99
athos@2149
   100
  //Restrict both to integer
athos@2267
   101
  mip.colType(x1,MipSolverBase::INT);  
athos@2149
   102
  expected_opt=0;
athos@2218
   103
  solveAndCheck(mip, MipSolverBase::OPTIMAL, expected_opt);
athos@2149
   104
athos@2149
   105
 
athos@2149
   106
athos@2149
   107
}
athos@2149
   108
athos@2149
   109
athos@2149
   110
int main() 
athos@2149
   111
{
athos@2146
   112
athos@2147
   113
#ifdef HAVE_GLPK
athos@2149
   114
  MipGlpk mip1;
athos@2149
   115
  aTest(mip1);
athos@2147
   116
#endif
athos@2146
   117
athos@2218
   118
#ifdef HAVE_CPLEX
athos@2218
   119
  MipCplex mip2;
athos@2218
   120
  aTest(mip2);
athos@2218
   121
#endif
athos@2218
   122
athos@2147
   123
  return 0;
athos@2146
   124
athos@2146
   125
}