test/mip_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 461 08d495d48089
child 537 0fec6a017ead
child 540 9db62975c32b
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
deba@458
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@458
     2
 *
deba@458
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@458
     4
 *
deba@458
     5
 * Copyright (C) 2003-2008
deba@458
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@458
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@458
     8
 *
deba@458
     9
 * Permission to use, modify and distribute this software is granted
deba@458
    10
 * provided that this copyright notice appears in all copies. For
deba@458
    11
 * precise terms see the accompanying LICENSE file.
deba@458
    12
 *
deba@458
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@458
    14
 * express or implied, and with no claim as to its suitability for any
deba@458
    15
 * purpose.
deba@458
    16
 *
deba@458
    17
 */
deba@458
    18
deba@458
    19
#include "test_tools.h"
deba@458
    20
deba@458
    21
deba@458
    22
#ifdef HAVE_CONFIG_H
deba@458
    23
#include <lemon/config.h>
deba@458
    24
#endif
deba@458
    25
deba@458
    26
#ifdef HAVE_CPLEX
alpar@461
    27
#include <lemon/cplex.h>
deba@458
    28
#endif
deba@458
    29
deba@458
    30
#ifdef HAVE_GLPK
alpar@461
    31
#include <lemon/glpk.h>
deba@458
    32
#endif
deba@458
    33
deba@458
    34
deba@458
    35
using namespace lemon;
deba@458
    36
deba@459
    37
void solveAndCheck(MipSolver& mip, MipSolver::ProblemType stat,
deba@458
    38
                   double exp_opt) {
deba@458
    39
  using std::string;
deba@458
    40
deba@459
    41
  mip.solve();
deba@458
    42
  //int decimal,sign;
deba@458
    43
  std::ostringstream buf;
deba@459
    44
  buf << "Type should be: " << int(stat)<<" and it is "<<int(mip.type());
deba@458
    45
deba@458
    46
deba@458
    47
  //  itoa(stat,buf1, 10);
deba@459
    48
  check(mip.type()==stat, buf.str());
deba@458
    49
deba@459
    50
  if (stat ==  MipSolver::OPTIMAL) {
deba@458
    51
    std::ostringstream sbuf;
deba@458
    52
    buf << "Wrong optimal value: the right optimum is " << exp_opt;
deba@459
    53
    check(std::abs(mip.solValue()-exp_opt) < 1e-3, sbuf.str());
deba@458
    54
    //+ecvt(exp_opt,2)
deba@458
    55
  }
deba@458
    56
}
deba@458
    57
deba@459
    58
void aTest(MipSolver& mip)
deba@458
    59
{
deba@458
    60
 //The following example is very simple
deba@458
    61
deba@458
    62
deba@459
    63
  typedef MipSolver::Row Row;
deba@459
    64
  typedef MipSolver::Col Col;
deba@458
    65
deba@458
    66
deba@458
    67
deba@458
    68
  Col x1 = mip.addCol();
deba@458
    69
  Col x2 = mip.addCol();
deba@458
    70
deba@458
    71
deba@458
    72
  //Objective function
deba@458
    73
  mip.obj(x1);
deba@458
    74
deba@458
    75
  mip.max();
deba@458
    76
deba@458
    77
deba@458
    78
  //Unconstrained optimization
deba@458
    79
  mip.solve();
deba@458
    80
  //Check it out!
deba@458
    81
deba@458
    82
  //Constraints
deba@458
    83
  mip.addRow(2*x1+x2 <=2);
deba@458
    84
  mip.addRow(x1-2*x2 <=0);
deba@458
    85
deba@458
    86
  //Nonnegativity of the variable x1
deba@458
    87
  mip.colLowerBound(x1, 0);
deba@458
    88
deba@458
    89
  //Maximization of x1
deba@458
    90
  //over the triangle with vertices (0,0),(4/5,2/5),(0,2)
deba@458
    91
  double expected_opt=4.0/5.0;
deba@459
    92
  solveAndCheck(mip, MipSolver::OPTIMAL, expected_opt);
deba@458
    93
deba@458
    94
  //Restrict x2 to integer
deba@459
    95
  mip.colType(x2,MipSolver::INTEGER);
deba@458
    96
  expected_opt=1.0/2.0;
deba@459
    97
  solveAndCheck(mip, MipSolver::OPTIMAL, expected_opt);
deba@458
    98
deba@458
    99
deba@458
   100
  //Restrict both to integer
deba@459
   101
  mip.colType(x1,MipSolver::INTEGER);
deba@458
   102
  expected_opt=0;
deba@459
   103
  solveAndCheck(mip, MipSolver::OPTIMAL, expected_opt);
deba@458
   104
deba@458
   105
deba@458
   106
deba@458
   107
}
deba@458
   108
deba@458
   109
deba@458
   110
int main()
deba@458
   111
{
deba@458
   112
deba@458
   113
#ifdef HAVE_GLPK
deba@459
   114
  {
alpar@462
   115
    GlpkMip mip1;
deba@459
   116
    aTest(mip1);
deba@459
   117
  }
deba@458
   118
#endif
deba@458
   119
deba@458
   120
#ifdef HAVE_CPLEX
deba@459
   121
  try {
alpar@462
   122
    CplexMip mip2;
deba@459
   123
    aTest(mip2);
deba@459
   124
  } catch (CplexEnv::LicenseError& error) {
deba@459
   125
#ifdef LEMON_FORCE_CPLEX_CHECK
deba@459
   126
    check(false, error.what());
deba@459
   127
#else
deba@459
   128
    std::cerr << error.what() << std::endl;
deba@459
   129
    std::cerr << "Cplex license check failed, lp check skipped" << std::endl;
deba@459
   130
#endif
deba@459
   131
  }
deba@458
   132
#endif
deba@458
   133
deba@458
   134
  return 0;
deba@458
   135
deba@458
   136
}