r607:49a39bae067c
Sun, 29 Mar 2009 23:19:14
[Not Reviewed]
0 comments (0 inline)
0
18
0
5
6
7
39
12
| 1 | 1 |
CMAKE_MINIMUM_REQUIRED(VERSION 2.6) |
| 2 | 2 |
|
| 3 | 3 |
IF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
|
| 4 | 4 |
INCLUDE(${CMAKE_SOURCE_DIR}/cmake/version.cmake)
|
| 5 | 5 |
ELSE(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
|
| 6 | 6 |
SET(PROJECT_NAME "LEMON") |
| 7 | 7 |
SET(PROJECT_VERSION "hg-tip" CACHE STRING "LEMON version string.") |
| 8 | 8 |
ENDIF(EXISTS ${CMAKE_SOURCE_DIR}/cmake/version.cmake)
|
| 9 | 9 |
|
| 10 | 10 |
PROJECT(${PROJECT_NAME})
|
| 11 | 11 |
|
| 12 |
SET(CMAKE_MODULE_PATH ${
|
|
| 12 |
SET(CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR}/cmake)
|
|
| 13 | 13 |
|
| 14 | 14 |
INCLUDE(FindDoxygen) |
| 15 | 15 |
INCLUDE(FindGhostscript) |
| 16 | 16 |
FIND_PACKAGE(GLPK 4.33) |
| 17 | 17 |
|
| 18 | 18 |
ADD_DEFINITIONS(-DHAVE_CONFIG_H) |
| 19 | 19 |
|
| 20 | 20 |
IF(MSVC) |
| 21 | 21 |
SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
|
| 22 | 22 |
# Suppressed warnings: |
| 23 | 23 |
# C4250: 'class1' : inherits 'class2::member' via dominance |
| 24 | 24 |
# C4355: 'this' : used in base member initializer list |
| 25 | 25 |
# C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning) |
| 26 | 26 |
# C4996: 'function': was declared deprecated |
| 27 | 27 |
ENDIF(MSVC) |
| 28 | 28 |
|
| 29 | 29 |
IF(GLPK_FOUND) |
| 30 | 30 |
SET(HAVE_LP TRUE) |
| 31 | 31 |
SET(HAVE_MIP TRUE) |
| 32 | 32 |
SET(HAVE_GLPK TRUE) |
| 33 | 33 |
ENDIF(GLPK_FOUND) |
| 34 | 34 |
|
| 35 | 35 |
INCLUDE(CheckTypeSize) |
| 36 | 36 |
CHECK_TYPE_SIZE("long long" LONG_LONG)
|
| 37 | 37 |
|
| 38 | 38 |
ENABLE_TESTING() |
| 39 | 39 |
|
| 40 | 40 |
ADD_SUBDIRECTORY(lemon) |
| 41 |
IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
|
|
| 41 | 42 |
ADD_SUBDIRECTORY(demo) |
| 42 | 43 |
ADD_SUBDIRECTORY(tools) |
| 43 | 44 |
ADD_SUBDIRECTORY(doc) |
| 44 | 45 |
ADD_SUBDIRECTORY(test) |
| 46 |
ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
|
|
| 45 | 47 |
|
| 48 |
IF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
|
|
| 46 | 49 |
IF(WIN32) |
| 47 | 50 |
SET(CPACK_PACKAGE_NAME ${PROJECT_NAME})
|
| 48 | 51 |
SET(CPACK_PACKAGE_VENDOR "EGRES") |
| 49 | 52 |
SET(CPACK_PACKAGE_DESCRIPTION_SUMMARY |
| 50 | 53 |
"LEMON - Library of Efficient Models and Optimization in Networks") |
| 51 |
SET(CPACK_RESOURCE_FILE_LICENSE "${
|
|
| 54 |
SET(CPACK_RESOURCE_FILE_LICENSE "${PROJECT_SOURCE_DIR}/LICENSE")
|
|
| 52 | 55 |
|
| 53 | 56 |
SET(CPACK_PACKAGE_VERSION ${PROJECT_VERSION})
|
| 54 | 57 |
|
| 55 | 58 |
SET(CPACK_PACKAGE_INSTALL_DIRECTORY |
| 56 | 59 |
"${PROJECT_NAME} ${PROJECT_VERSION}")
|
| 57 | 60 |
SET(CPACK_PACKAGE_INSTALL_REGISTRY_KEY |
| 58 | 61 |
"${PROJECT_NAME} ${PROJECT_VERSION}")
|
| 59 | 62 |
|
| 60 | 63 |
SET(CPACK_COMPONENTS_ALL headers library html_documentation bin) |
| 61 | 64 |
|
| 62 | 65 |
SET(CPACK_COMPONENT_HEADERS_DISPLAY_NAME "C++ headers") |
| 63 | 66 |
SET(CPACK_COMPONENT_LIBRARY_DISPLAY_NAME "Dynamic-link library") |
| 64 | 67 |
SET(CPACK_COMPONENT_BIN_DISPLAY_NAME "Command line utilities") |
| 65 | 68 |
SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DISPLAY_NAME "HTML documentation") |
| 66 | 69 |
|
| 67 | 70 |
SET(CPACK_COMPONENT_HEADERS_DESCRIPTION |
| 68 | 71 |
"C++ header files") |
| 69 | 72 |
SET(CPACK_COMPONENT_LIBRARY_DESCRIPTION |
| 70 | 73 |
"DLL and import library") |
| 71 | 74 |
SET(CPACK_COMPONENT_BIN_DESCRIPTION |
| 72 | 75 |
"Command line utilities") |
| 73 | 76 |
SET(CPACK_COMPONENT_HTML_DOCUMENTATION_DESCRIPTION |
| 74 | 77 |
"Doxygen generated documentation") |
| 75 | 78 |
|
| 76 | 79 |
SET(CPACK_COMPONENT_HEADERS_DEPENDS library) |
| 77 | 80 |
|
| 78 | 81 |
SET(CPACK_COMPONENT_HEADERS_GROUP "Development") |
| 79 | 82 |
SET(CPACK_COMPONENT_LIBRARY_GROUP "Development") |
| 80 | 83 |
SET(CPACK_COMPONENT_HTML_DOCUMENTATION_GROUP "Documentation") |
| 81 | 84 |
|
| 82 | 85 |
SET(CPACK_COMPONENT_GROUP_DEVELOPMENT_DESCRIPTION |
| 83 | 86 |
"Components needed to develop software using LEMON") |
| 84 | 87 |
SET(CPACK_COMPONENT_GROUP_DOCUMENTATION_DESCRIPTION |
| 85 | 88 |
"Documentation of LEMON") |
| 86 | 89 |
|
| 87 | 90 |
SET(CPACK_ALL_INSTALL_TYPES Full Developer) |
| 88 | 91 |
|
| 89 | 92 |
SET(CPACK_COMPONENT_HEADERS_INSTALL_TYPES Developer Full) |
| 90 | 93 |
SET(CPACK_COMPONENT_LIBRARY_INSTALL_TYPES Developer Full) |
| 91 | 94 |
SET(CPACK_COMPONENT_HTML_DOCUMENTATION_INSTALL_TYPES Full) |
| 92 | 95 |
|
| 93 | 96 |
SET(CPACK_GENERATOR "NSIS") |
| 94 |
SET(CPACK_NSIS_MUI_ICON "${CMAKE_SOURCE_DIR}/cmake/nsis/lemon.ico")
|
|
| 95 |
SET(CPACK_NSIS_MUI_UNIICON "${CMAKE_SOURCE_DIR}/cmake/nsis/uninstall.ico")
|
|
| 96 |
|
|
| 97 |
SET(CPACK_NSIS_MUI_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis/lemon.ico")
|
|
| 98 |
SET(CPACK_NSIS_MUI_UNIICON "${PROJECT_SOURCE_DIR}/cmake/nsis/uninstall.ico")
|
|
| 99 |
#SET(CPACK_PACKAGE_ICON "${PROJECT_SOURCE_DIR}/cmake/nsis\\\\installer.bmp")
|
|
| 97 | 100 |
SET(CPACK_NSIS_INSTALLED_ICON_NAME "bin\\\\lemon.ico") |
| 98 | 101 |
SET(CPACK_NSIS_DISPLAY_NAME "${CPACK_PACKAGE_INSTALL_DIRECTORY} ${PROJECT_NAME}")
|
| 99 | 102 |
SET(CPACK_NSIS_HELP_LINK "http:\\\\\\\\lemon.cs.elte.hu") |
| 100 | 103 |
SET(CPACK_NSIS_URL_INFO_ABOUT "http:\\\\\\\\lemon.cs.elte.hu") |
| 101 | 104 |
SET(CPACK_NSIS_CONTACT "lemon-user@lemon.cs.elte.hu") |
| 102 | 105 |
SET(CPACK_NSIS_CREATE_ICONS_EXTRA " |
| 103 | 106 |
CreateShortCut \\\"$SMPROGRAMS\\\\$STARTMENU_FOLDER\\\\Documentation.lnk\\\" \\\"$INSTDIR\\\\share\\\\doc\\\\index.html\\\" |
| 104 | 107 |
") |
| 105 | 108 |
SET(CPACK_NSIS_DELETE_ICONS_EXTRA " |
| 106 | 109 |
!insertmacro MUI_STARTMENU_GETFOLDER Application $MUI_TEMP |
| 107 | 110 |
Delete \\\"$SMPROGRAMS\\\\$MUI_TEMP\\\\Documentation.lnk\\\" |
| 108 | 111 |
") |
| 109 | 112 |
|
| 110 | 113 |
INCLUDE(CPack) |
| 111 | 114 |
ENDIF(WIN32) |
| 115 |
ENDIF(${CMAKE_SOURCE_DIR} STREQUAL ${PROJECT_SOURCE_DIR})
|
| 1 |
LEMON code without an explicit copyright is covered by the following |
|
| 1 |
LEMON code without an explicit copyright notice is covered by the following |
|
| 2 | 2 |
copyright/license. |
| 3 | 3 |
|
| 4 | 4 |
Copyright (C) 2003-2009 Egervary Jeno Kombinatorikus Optimalizalasi |
| 5 | 5 |
Kutatocsoport (Egervary Combinatorial Optimization Research Group, |
| 6 | 6 |
EGRES). |
| 7 | 7 |
|
| 8 |
=========================================================================== |
|
| 9 |
Boost Software License, Version 1.0 |
|
| 10 |
=========================================================================== |
|
| 11 |
|
|
| 8 | 12 |
Permission is hereby granted, free of charge, to any person or organization |
| 9 | 13 |
obtaining a copy of the software and accompanying documentation covered by |
| 10 | 14 |
this license (the "Software") to use, reproduce, display, distribute, |
| 11 | 15 |
execute, and transmit the Software, and to prepare derivative works of the |
| 12 | 16 |
Software, and to permit third-parties to whom the Software is furnished to |
| 13 | 17 |
do so, all subject to the following: |
| 14 | 18 |
|
| 15 | 19 |
The copyright notices in the Software and this entire statement, including |
| 16 | 20 |
the above license grant, this restriction and the following disclaimer, |
| 17 | 21 |
must be included in all copies of the Software, in whole or in part, and |
| 18 | 22 |
all derivative works of the Software, unless such copies or derivative |
| 19 | 23 |
works are solely in the form of machine-executable object code generated by |
| 20 | 24 |
a source language processor. |
| 21 | 25 |
|
| 22 | 26 |
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 23 | 27 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 24 | 28 |
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT |
| 25 | 29 |
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE |
| 26 | 30 |
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, |
| 27 | 31 |
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
| 28 | 32 |
DEALINGS IN THE SOFTWARE. |
| 29 |
|
|
| 30 |
=========================================================================== |
|
| 31 |
This license is a verbatim copy of the Boost Software License, Version 1.0. |
|
| 32 |
|
|
| 33 |
| 1 |
2009-03-27 LEMON joins to the COIN-OR initiative |
|
| 2 |
|
|
| 3 |
COIN-OR (Computational Infrastructure for Operations Research, |
|
| 4 |
http://www.coin-or.org) project is an initiative to spur the |
|
| 5 |
development of open-source software for the operations research |
|
| 6 |
community. |
|
| 7 |
|
|
| 1 | 8 |
2008-10-13 Version 1.0 released |
| 2 | 9 |
|
| 3 | 10 |
This is the first stable release of LEMON. Compared to the 0.x |
| 4 | 11 |
release series, it features a considerably smaller but more |
| 5 | 12 |
matured set of tools. The API has also completely revised and |
| 6 | 13 |
changed in several places. |
| 7 | 14 |
|
| 8 | 15 |
* The major name changes compared to the 0.x series (see the |
| 9 | 16 |
Migration Guide in the doc for more details) |
| 10 | 17 |
* Graph -> Digraph, UGraph -> Graph |
| 11 | 18 |
* Edge -> Arc, UEdge -> Edge |
| 12 | 19 |
* source(UEdge)/target(UEdge) -> u(Edge)/v(Edge) |
| 13 | 20 |
* Other improvements |
| 14 | 21 |
* Better documentation |
| 15 | 22 |
* Reviewed and cleaned up codebase |
| 16 | 23 |
* CMake based build system (along with the autotools based one) |
| 17 | 24 |
* Contents of the library (ported from 0.x) |
| 18 | 25 |
* Algorithms |
| 19 | 26 |
* breadth-first search (bfs.h) |
| 20 | 27 |
* depth-first search (dfs.h) |
| 21 | 28 |
* Dijkstra's algorithm (dijkstra.h) |
| 22 | 29 |
* Kruskal's algorithm (kruskal.h) |
| 23 | 30 |
* Data structures |
| 24 | 31 |
* graph data structures (list_graph.h, smart_graph.h) |
| 25 | 32 |
* path data structures (path.h) |
| 26 | 33 |
* binary heap data structure (bin_heap.h) |
| 27 | 34 |
* union-find data structures (unionfind.h) |
| 28 | 35 |
* miscellaneous property maps (maps.h) |
| 29 | 36 |
* two dimensional vector and bounding box (dim2.h) |
| 30 | 37 |
* Concepts |
| 31 | 38 |
* graph structure concepts (concepts/digraph.h, concepts/graph.h, |
| 32 | 39 |
concepts/graph_components.h) |
| 33 | 40 |
* concepts for other structures (concepts/heap.h, concepts/maps.h, |
| 34 | 41 |
concepts/path.h) |
| 35 | 42 |
* Tools |
| 36 | 43 |
* Mersenne twister random number generator (random.h) |
| 37 | 44 |
* tools for measuring cpu and wall clock time (time_measure.h) |
| 38 | 45 |
* tools for counting steps and events (counter.h) |
| 39 | 46 |
* tool for parsing command line arguments (arg_parser.h) |
| 40 | 47 |
* tool for visualizing graphs (graph_to_eps.h) |
| 41 | 48 |
* tools for reading and writing data in LEMON Graph Format |
| 42 | 49 |
(lgf_reader.h, lgf_writer.h) |
| 43 | 50 |
* tools to handle the anomalies of calculations with |
| 44 | 51 |
floating point numbers (tolerance.h) |
| 45 | 52 |
* tools to manage RGB colors (color.h) |
| 46 | 53 |
* Infrastructure |
| 47 | 54 |
* extended assertion handling (assert.h) |
| 48 | 55 |
* exception classes and error handling (error.h) |
| 49 | 56 |
* concept checking (concept_check.h) |
| 50 | 57 |
* commonly used mathematical constants (math.h) |
| 1 | 1 |
INCLUDE_DIRECTORIES( |
| 2 |
${CMAKE_SOURCE_DIR}
|
|
| 3 |
${CMAKE_BINARY_DIR}
|
|
| 2 |
${PROJECT_SOURCE_DIR}
|
|
| 3 |
${PROJECT_BINARY_DIR}
|
|
| 4 | 4 |
) |
| 5 | 5 |
|
| 6 |
LINK_DIRECTORIES(${
|
|
| 6 |
LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
|
|
| 7 | 7 |
|
| 8 | 8 |
SET(DEMOS |
| 9 | 9 |
arg_parser_demo |
| 10 | 10 |
graph_to_eps_demo |
| 11 | 11 |
lgf_demo) |
| 12 | 12 |
|
| 13 | 13 |
FOREACH(DEMO_NAME ${DEMOS})
|
| 14 | 14 |
ADD_EXECUTABLE(${DEMO_NAME} ${DEMO_NAME}.cc)
|
| 15 | 15 |
TARGET_LINK_LIBRARIES(${DEMO_NAME} lemon)
|
| 16 | 16 |
ENDFOREACH(DEMO_NAME) |
| 1 | 1 |
SET(PACKAGE_NAME ${PROJECT_NAME})
|
| 2 | 2 |
SET(PACKAGE_VERSION ${PROJECT_VERSION})
|
| 3 |
SET(abs_top_srcdir ${CMAKE_SOURCE_DIR})
|
|
| 4 |
SET(abs_top_builddir ${CMAKE_BINARY_DIR})
|
|
| 3 |
SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
|
|
| 4 |
SET(abs_top_builddir ${PROJECT_BINARY_DIR})
|
|
| 5 | 5 |
|
| 6 | 6 |
CONFIGURE_FILE( |
| 7 |
${CMAKE_SOURCE_DIR}/doc/Doxyfile.in
|
|
| 8 |
${CMAKE_BINARY_DIR}/doc/Doxyfile
|
|
| 7 |
${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
|
|
| 8 |
${PROJECT_BINARY_DIR}/doc/Doxyfile
|
|
| 9 | 9 |
@ONLY) |
| 10 | 10 |
|
| 11 | 11 |
IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE) |
| 12 | 12 |
FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
|
| 13 | 13 |
IF(UNIX) |
| 14 | 14 |
ADD_CUSTOM_TARGET(html |
| 15 | 15 |
COMMAND rm -rf gen-images |
| 16 | 16 |
COMMAND mkdir gen-images |
| 17 | 17 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
|
| 18 | 18 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
|
| 19 | 19 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
|
| 20 | 20 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
|
| 21 | 21 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
|
| 22 | 22 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
|
| 23 | 23 |
COMMAND rm -rf html |
| 24 | 24 |
COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
|
| 25 | 25 |
WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
|
| 26 | 26 |
ELSEIF(WIN32) |
| 27 | 27 |
ADD_CUSTOM_TARGET(html |
| 28 | 28 |
COMMAND if exist gen-images rmdir /s /q gen-images |
| 29 | 29 |
COMMAND mkdir gen-images |
| 30 | 30 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
|
| 31 | 31 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
|
| 32 | 32 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
|
| 33 | 33 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
|
| 34 | 34 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
|
| 35 | 35 |
COMMAND if exist html rmdir /s /q html |
| 36 | 36 |
COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile
|
| 37 | 37 |
WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR})
|
| 38 | 38 |
ENDIF(UNIX) |
| 39 | 39 |
INSTALL( |
| 40 | 40 |
DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
|
| 41 | 41 |
DESTINATION share/doc |
| 42 | 42 |
COMPONENT html_documentation) |
| 43 | 43 |
ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE) |
| 1 | 1 |
INCLUDE_DIRECTORIES( |
| 2 |
${CMAKE_SOURCE_DIR}
|
|
| 3 |
${CMAKE_BINARY_DIR}
|
|
| 2 |
${PROJECT_SOURCE_DIR}
|
|
| 3 |
${PROJECT_BINARY_DIR}
|
|
| 4 | 4 |
) |
| 5 | 5 |
|
| 6 | 6 |
CONFIGURE_FILE( |
| 7 | 7 |
${CMAKE_CURRENT_SOURCE_DIR}/config.h.cmake
|
| 8 | 8 |
${CMAKE_CURRENT_BINARY_DIR}/config.h
|
| 9 | 9 |
) |
| 10 | 10 |
|
| 11 | 11 |
SET(LEMON_SOURCES |
| 12 | 12 |
arg_parser.cc |
| 13 | 13 |
base.cc |
| 14 | 14 |
color.cc |
| 15 | 15 |
lp_base.cc |
| 16 | 16 |
lp_skeleton.cc |
| 17 | 17 |
random.cc |
| 18 | 18 |
bits/windows.cc |
| 19 | 19 |
) |
| 20 | 20 |
|
| 21 | 21 |
IF(HAVE_GLPK) |
| 22 | 22 |
SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
|
| 23 | 23 |
INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
|
| 24 | 24 |
IF(WIN32) |
| 25 | 25 |
INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
|
| 26 | 26 |
INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
|
| 27 | 27 |
INSTALL(FILES ${GLPK_BIN_DIR}/zlib1.dll DESTINATION bin)
|
| 28 | 28 |
ENDIF(WIN32) |
| 29 | 29 |
ENDIF(HAVE_GLPK) |
| 30 | 30 |
|
| 31 | 31 |
ADD_LIBRARY(lemon ${LEMON_SOURCES})
|
| 32 | 32 |
|
| 33 | 33 |
INSTALL( |
| 34 | 34 |
TARGETS lemon |
| 35 | 35 |
ARCHIVE DESTINATION lib |
| 36 | 36 |
COMPONENT library) |
| 37 | 37 |
|
| 38 | 38 |
INSTALL( |
| 39 | 39 |
DIRECTORY . bits concepts |
| 40 | 40 |
DESTINATION include/lemon |
| 41 | 41 |
COMPONENT headers |
| 42 | 42 |
FILES_MATCHING PATTERN "*.h") |
| 1 | 1 |
EXTRA_DIST += \ |
| 2 | 2 |
lemon/lemon.pc.in \ |
| 3 | 3 |
lemon/CMakeLists.txt |
| 4 | 4 |
|
| 5 | 5 |
pkgconfig_DATA += lemon/lemon.pc |
| 6 | 6 |
|
| 7 | 7 |
lib_LTLIBRARIES += lemon/libemon.la |
| 8 | 8 |
|
| 9 | 9 |
lemon_libemon_la_SOURCES = \ |
| 10 | 10 |
lemon/arg_parser.cc \ |
| 11 | 11 |
lemon/base.cc \ |
| 12 | 12 |
lemon/color.cc \ |
| 13 | 13 |
lemon/lp_base.cc \ |
| 14 | 14 |
lemon/lp_skeleton.cc \ |
| 15 | 15 |
lemon/random.cc \ |
| 16 | 16 |
lemon/bits/windows.cc |
| 17 | 17 |
|
| 18 | 18 |
|
| 19 | 19 |
lemon_libemon_la_CXXFLAGS = \ |
| 20 |
$(AM_CXXFLAGS) \ |
|
| 20 | 21 |
$(GLPK_CFLAGS) \ |
| 21 | 22 |
$(CPLEX_CFLAGS) \ |
| 22 | 23 |
$(SOPLEX_CXXFLAGS) \ |
| 23 | 24 |
$(CLP_CXXFLAGS) |
| 24 | 25 |
|
| 25 | 26 |
lemon_libemon_la_LDFLAGS = \ |
| 26 | 27 |
$(GLPK_LIBS) \ |
| 27 | 28 |
$(CPLEX_LIBS) \ |
| 28 | 29 |
$(SOPLEX_LIBS) \ |
| 29 | 30 |
$(CLP_LIBS) |
| 30 | 31 |
|
| 31 | 32 |
if HAVE_GLPK |
| 32 | 33 |
lemon_libemon_la_SOURCES += lemon/glpk.cc |
| 33 | 34 |
endif |
| 34 | 35 |
|
| 35 | 36 |
if HAVE_CPLEX |
| 36 | 37 |
lemon_libemon_la_SOURCES += lemon/cplex.cc |
| 37 | 38 |
endif |
| 38 | 39 |
|
| 39 | 40 |
if HAVE_SOPLEX |
| 40 | 41 |
lemon_libemon_la_SOURCES += lemon/soplex.cc |
| 41 | 42 |
endif |
| 42 | 43 |
|
| 43 | 44 |
if HAVE_CLP |
| 44 | 45 |
lemon_libemon_la_SOURCES += lemon/clp.cc |
| 45 | 46 |
endif |
| 46 | 47 |
|
| 47 | 48 |
lemon_HEADERS += \ |
| 48 | 49 |
lemon/adaptors.h \ |
| 49 | 50 |
lemon/arg_parser.h \ |
| 50 | 51 |
lemon/assert.h \ |
| 51 | 52 |
lemon/bfs.h \ |
| 52 | 53 |
lemon/bin_heap.h \ |
| 53 | 54 |
lemon/circulation.h \ |
| 54 | 55 |
lemon/clp.h \ |
| 55 | 56 |
lemon/color.h \ |
| 56 | 57 |
lemon/concept_check.h \ |
| 57 | 58 |
lemon/connectivity.h \ |
| 58 | 59 |
lemon/counter.h \ |
| 59 | 60 |
lemon/core.h \ |
| 60 | 61 |
lemon/cplex.h \ |
| 61 | 62 |
lemon/dfs.h \ |
| 62 | 63 |
lemon/dijkstra.h \ |
| 63 | 64 |
lemon/dim2.h \ |
| 64 | 65 |
lemon/dimacs.h \ |
| 65 | 66 |
lemon/edge_set.h \ |
| 66 | 67 |
lemon/elevator.h \ |
| 67 | 68 |
lemon/error.h \ |
| 68 | 69 |
lemon/euler.h \ |
| 69 | 70 |
lemon/full_graph.h \ |
| 70 | 71 |
lemon/glpk.h \ |
| 71 | 72 |
lemon/gomory_hu.h \ |
| 72 | 73 |
lemon/graph_to_eps.h \ |
| 73 | 74 |
lemon/grid_graph.h \ |
| 74 | 75 |
lemon/hypercube_graph.h \ |
| 75 | 76 |
lemon/kruskal.h \ |
| 76 | 77 |
lemon/hao_orlin.h \ |
| 77 | 78 |
lemon/lgf_reader.h \ |
| 78 | 79 |
lemon/lgf_writer.h \ |
| 79 | 80 |
lemon/list_graph.h \ |
| 80 | 81 |
lemon/lp.h \ |
| 81 | 82 |
lemon/lp_base.h \ |
| 82 | 83 |
lemon/lp_skeleton.h \ |
| 83 | 84 |
lemon/list_graph.h \ |
| 84 | 85 |
lemon/maps.h \ |
| 85 | 86 |
lemon/math.h \ |
| 86 | 87 |
lemon/max_matching.h \ |
| 87 | 88 |
lemon/min_cost_arborescence.h \ |
| 88 | 89 |
lemon/nauty_reader.h \ |
| 89 | 90 |
lemon/path.h \ |
| 90 | 91 |
lemon/preflow.h \ |
| 91 | 92 |
lemon/radix_sort.h \ |
| 92 | 93 |
lemon/random.h \ |
| 93 | 94 |
lemon/smart_graph.h \ |
| 94 | 95 |
lemon/soplex.h \ |
| 95 | 96 |
lemon/suurballe.h \ |
| 96 | 97 |
lemon/time_measure.h \ |
| 97 | 98 |
lemon/tolerance.h \ |
| 98 | 99 |
lemon/unionfind.h \ |
| 99 | 100 |
lemon/bits/windows.h |
| 100 | 101 |
|
| 101 | 102 |
bits_HEADERS += \ |
| 102 | 103 |
lemon/bits/alteration_notifier.h \ |
| 103 | 104 |
lemon/bits/array_map.h \ |
| 104 | 105 |
lemon/bits/base_extender.h \ |
| 105 | 106 |
lemon/bits/bezier.h \ |
| 106 | 107 |
lemon/bits/default_map.h \ |
| 107 | 108 |
lemon/bits/edge_set_extender.h \ |
| 108 | 109 |
lemon/bits/enable_if.h \ |
| 109 | 110 |
lemon/bits/graph_adaptor_extender.h \ |
| 110 | 111 |
lemon/bits/graph_extender.h \ |
| 111 | 112 |
lemon/bits/map_extender.h \ |
| 112 | 113 |
lemon/bits/path_dump.h \ |
| 113 | 114 |
lemon/bits/solver_bits.h \ |
| 114 | 115 |
lemon/bits/traits.h \ |
| 115 | 116 |
lemon/bits/variant.h \ |
| 116 | 117 |
lemon/bits/vector_map.h |
| 117 | 118 |
|
| 118 | 119 |
concept_HEADERS += \ |
| 119 | 120 |
lemon/concepts/digraph.h \ |
| 120 | 121 |
lemon/concepts/graph.h \ |
| 121 | 122 |
lemon/concepts/graph_components.h \ |
| 122 | 123 |
lemon/concepts/heap.h \ |
| 123 | 124 |
lemon/concepts/maps.h \ |
| 124 | 125 |
lemon/concepts/path.h |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include <iostream> |
| 20 | 20 |
#include <vector> |
| 21 | 21 |
#include <cstring> |
| 22 | 22 |
|
| 23 | 23 |
#include <lemon/cplex.h> |
| 24 | 24 |
|
| 25 | 25 |
extern "C" {
|
| 26 | 26 |
#include <ilcplex/cplex.h> |
| 27 | 27 |
} |
| 28 | 28 |
|
| 29 | 29 |
|
| 30 | 30 |
///\file |
| 31 | 31 |
///\brief Implementation of the LEMON-CPLEX lp solver interface. |
| 32 | 32 |
namespace lemon {
|
| 33 | 33 |
|
| 34 | 34 |
CplexEnv::LicenseError::LicenseError(int status) {
|
| 35 | 35 |
if (!CPXgeterrorstring(0, status, _message)) {
|
| 36 | 36 |
std::strcpy(_message, "Cplex unknown error"); |
| 37 | 37 |
} |
| 38 | 38 |
} |
| 39 | 39 |
|
| 40 | 40 |
CplexEnv::CplexEnv() {
|
| 41 | 41 |
int status; |
| 42 | 42 |
_cnt = new int; |
| 43 | 43 |
_env = CPXopenCPLEX(&status); |
| 44 | 44 |
if (_env == 0) {
|
| 45 | 45 |
delete _cnt; |
| 46 | 46 |
_cnt = 0; |
| 47 | 47 |
throw LicenseError(status); |
| 48 | 48 |
} |
| 49 | 49 |
} |
| 50 | 50 |
|
| 51 | 51 |
CplexEnv::CplexEnv(const CplexEnv& other) {
|
| 52 | 52 |
_env = other._env; |
| 53 | 53 |
_cnt = other._cnt; |
| 54 | 54 |
++(*_cnt); |
| 55 | 55 |
} |
| 56 | 56 |
|
| 57 | 57 |
CplexEnv& CplexEnv::operator=(const CplexEnv& other) {
|
| 58 | 58 |
_env = other._env; |
| 59 | 59 |
_cnt = other._cnt; |
| 60 | 60 |
++(*_cnt); |
| 61 | 61 |
return *this; |
| 62 | 62 |
} |
| 63 | 63 |
|
| 64 | 64 |
CplexEnv::~CplexEnv() {
|
| 65 | 65 |
--(*_cnt); |
| 66 | 66 |
if (*_cnt == 0) {
|
| 67 | 67 |
delete _cnt; |
| 68 | 68 |
CPXcloseCPLEX(&_env); |
| 69 | 69 |
} |
| 70 | 70 |
} |
| 71 | 71 |
|
| 72 | 72 |
CplexBase::CplexBase() : LpBase() {
|
| 73 | 73 |
int status; |
| 74 | 74 |
_prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem"); |
| 75 | 75 |
} |
| 76 | 76 |
|
| 77 | 77 |
CplexBase::CplexBase(const CplexEnv& env) |
| 78 | 78 |
: LpBase(), _env(env) {
|
| 79 | 79 |
int status; |
| 80 | 80 |
_prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem"); |
| 81 | 81 |
} |
| 82 | 82 |
|
| 83 | 83 |
CplexBase::CplexBase(const CplexBase& cplex) |
| 84 | 84 |
: LpBase() {
|
| 85 | 85 |
int status; |
| 86 | 86 |
_prob = CPXcloneprob(cplexEnv(), cplex._prob, &status); |
| 87 | 87 |
rows = cplex.rows; |
| 88 | 88 |
cols = cplex.cols; |
| 89 | 89 |
} |
| 90 | 90 |
|
| 91 | 91 |
CplexBase::~CplexBase() {
|
| 92 | 92 |
CPXfreeprob(cplexEnv(),&_prob); |
| 93 | 93 |
} |
| 94 | 94 |
|
| 95 | 95 |
int CplexBase::_addCol() {
|
| 96 | 96 |
int i = CPXgetnumcols(cplexEnv(), _prob); |
| 97 | 97 |
double lb = -INF, ub = INF; |
| 98 | 98 |
CPXnewcols(cplexEnv(), _prob, 1, 0, &lb, &ub, 0, 0); |
| 99 | 99 |
return i; |
| 100 | 100 |
} |
| 101 | 101 |
|
| 102 | 102 |
|
| 103 | 103 |
int CplexBase::_addRow() {
|
| 104 | 104 |
int i = CPXgetnumrows(cplexEnv(), _prob); |
| 105 | 105 |
const double ub = INF; |
| 106 | 106 |
const char s = 'L'; |
| 107 | 107 |
CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0); |
| 108 | 108 |
return i; |
| 109 | 109 |
} |
| 110 | 110 |
|
| 111 | 111 |
|
| 112 | 112 |
void CplexBase::_eraseCol(int i) {
|
| 113 | 113 |
CPXdelcols(cplexEnv(), _prob, i, i); |
| 114 | 114 |
} |
| 115 | 115 |
|
| 116 | 116 |
void CplexBase::_eraseRow(int i) {
|
| 117 | 117 |
CPXdelrows(cplexEnv(), _prob, i, i); |
| 118 | 118 |
} |
| 119 | 119 |
|
| 120 | 120 |
void CplexBase::_eraseColId(int i) {
|
| 121 | 121 |
cols.eraseIndex(i); |
| 122 | 122 |
cols.shiftIndices(i); |
| 123 | 123 |
} |
| 124 | 124 |
void CplexBase::_eraseRowId(int i) {
|
| 125 | 125 |
rows.eraseIndex(i); |
| 126 | 126 |
rows.shiftIndices(i); |
| 127 | 127 |
} |
| 128 | 128 |
|
| 129 | 129 |
void CplexBase::_getColName(int col, std::string &name) const {
|
| 130 | 130 |
int size; |
| 131 | 131 |
CPXgetcolname(cplexEnv(), _prob, 0, 0, 0, &size, col, col); |
| 132 | 132 |
if (size == 0) {
|
| 133 | 133 |
name.clear(); |
| 134 | 134 |
return; |
| 135 | 135 |
} |
| 136 | 136 |
|
| 137 | 137 |
size *= -1; |
| 138 | 138 |
std::vector<char> buf(size); |
| 139 | 139 |
char *cname; |
| 140 | 140 |
int tmp; |
| 141 | 141 |
CPXgetcolname(cplexEnv(), _prob, &cname, &buf.front(), size, |
| 142 | 142 |
&tmp, col, col); |
| 143 | 143 |
name = cname; |
| 144 | 144 |
} |
| 145 | 145 |
|
| 146 | 146 |
void CplexBase::_setColName(int col, const std::string &name) {
|
| 147 | 147 |
char *cname; |
| 148 | 148 |
cname = const_cast<char*>(name.c_str()); |
| 149 | 149 |
CPXchgcolname(cplexEnv(), _prob, 1, &col, &cname); |
| 150 | 150 |
} |
| 151 | 151 |
|
| 152 | 152 |
int CplexBase::_colByName(const std::string& name) const {
|
| 153 | 153 |
int index; |
| 154 | 154 |
if (CPXgetcolindex(cplexEnv(), _prob, |
| 155 | 155 |
const_cast<char*>(name.c_str()), &index) == 0) {
|
| 156 | 156 |
return index; |
| 157 | 157 |
} |
| 158 | 158 |
return -1; |
| 159 | 159 |
} |
| 160 | 160 |
|
| 161 | 161 |
void CplexBase::_getRowName(int row, std::string &name) const {
|
| 162 | 162 |
int size; |
| 163 | 163 |
CPXgetrowname(cplexEnv(), _prob, 0, 0, 0, &size, row, row); |
| 164 | 164 |
if (size == 0) {
|
| 165 | 165 |
name.clear(); |
| 166 | 166 |
return; |
| 167 | 167 |
} |
| 168 | 168 |
|
| 169 | 169 |
size *= -1; |
| 170 | 170 |
std::vector<char> buf(size); |
| 171 | 171 |
char *cname; |
| 172 | 172 |
int tmp; |
| 173 | 173 |
CPXgetrowname(cplexEnv(), _prob, &cname, &buf.front(), size, |
| 174 | 174 |
&tmp, row, row); |
| 175 | 175 |
name = cname; |
| 176 | 176 |
} |
| 177 | 177 |
|
| 178 | 178 |
void CplexBase::_setRowName(int row, const std::string &name) {
|
| 179 | 179 |
char *cname; |
| 180 | 180 |
cname = const_cast<char*>(name.c_str()); |
| 181 | 181 |
CPXchgrowname(cplexEnv(), _prob, 1, &row, &cname); |
| 182 | 182 |
} |
| 183 | 183 |
|
| 184 | 184 |
int CplexBase::_rowByName(const std::string& name) const {
|
| 185 | 185 |
int index; |
| 186 | 186 |
if (CPXgetrowindex(cplexEnv(), _prob, |
| 187 | 187 |
const_cast<char*>(name.c_str()), &index) == 0) {
|
| 188 | 188 |
return index; |
| 189 | 189 |
} |
| 190 | 190 |
return -1; |
| 191 | 191 |
} |
| 192 | 192 |
|
| 193 | 193 |
void CplexBase::_setRowCoeffs(int i, ExprIterator b, |
| 194 | 194 |
ExprIterator e) |
| 195 | 195 |
{
|
| 196 | 196 |
std::vector<int> indices; |
| 197 | 197 |
std::vector<int> rowlist; |
| 198 | 198 |
std::vector<Value> values; |
| 199 | 199 |
|
| 200 | 200 |
for(ExprIterator it=b; it!=e; ++it) {
|
| 201 | 201 |
indices.push_back(it->first); |
| 202 | 202 |
values.push_back(it->second); |
| 203 | 203 |
rowlist.push_back(i); |
| 204 | 204 |
} |
| 205 | 205 |
|
| 206 | 206 |
CPXchgcoeflist(cplexEnv(), _prob, values.size(), |
| 207 | 207 |
&rowlist.front(), &indices.front(), &values.front()); |
| 208 | 208 |
} |
| 209 | 209 |
|
| 210 | 210 |
void CplexBase::_getRowCoeffs(int i, InsertIterator b) const {
|
| 211 | 211 |
int tmp1, tmp2, tmp3, length; |
| 212 | 212 |
CPXgetrows(cplexEnv(), _prob, &tmp1, &tmp2, 0, 0, 0, &length, i, i); |
| 213 | 213 |
|
| 214 | 214 |
length = -length; |
| 215 | 215 |
std::vector<int> indices(length); |
| 216 | 216 |
std::vector<double> values(length); |
| 217 | 217 |
|
| 218 | 218 |
CPXgetrows(cplexEnv(), _prob, &tmp1, &tmp2, |
| 219 | 219 |
&indices.front(), &values.front(), |
| 220 | 220 |
length, &tmp3, i, i); |
| 221 | 221 |
|
| 222 | 222 |
for (int i = 0; i < length; ++i) {
|
| 223 | 223 |
*b = std::make_pair(indices[i], values[i]); |
| 224 | 224 |
++b; |
| 225 | 225 |
} |
| 226 | 226 |
} |
| 227 | 227 |
|
| 228 | 228 |
void CplexBase::_setColCoeffs(int i, ExprIterator b, ExprIterator e) {
|
| 229 | 229 |
std::vector<int> indices; |
| 230 | 230 |
std::vector<int> collist; |
| 231 | 231 |
std::vector<Value> values; |
| 232 | 232 |
|
| 233 | 233 |
for(ExprIterator it=b; it!=e; ++it) {
|
| 234 | 234 |
indices.push_back(it->first); |
| 235 | 235 |
values.push_back(it->second); |
| 236 | 236 |
collist.push_back(i); |
| 237 | 237 |
} |
| 238 | 238 |
|
| 239 | 239 |
CPXchgcoeflist(cplexEnv(), _prob, values.size(), |
| 240 | 240 |
&indices.front(), &collist.front(), &values.front()); |
| 241 | 241 |
} |
| 242 | 242 |
|
| 243 | 243 |
void CplexBase::_getColCoeffs(int i, InsertIterator b) const {
|
| 244 | 244 |
|
| 245 | 245 |
int tmp1, tmp2, tmp3, length; |
| 246 | 246 |
CPXgetcols(cplexEnv(), _prob, &tmp1, &tmp2, 0, 0, 0, &length, i, i); |
| 247 | 247 |
|
| 248 | 248 |
length = -length; |
| 249 | 249 |
std::vector<int> indices(length); |
| 250 | 250 |
std::vector<double> values(length); |
| 251 | 251 |
|
| 252 | 252 |
CPXgetcols(cplexEnv(), _prob, &tmp1, &tmp2, |
| 253 | 253 |
&indices.front(), &values.front(), |
| 254 | 254 |
length, &tmp3, i, i); |
| 255 | 255 |
|
| 256 | 256 |
for (int i = 0; i < length; ++i) {
|
| 257 | 257 |
*b = std::make_pair(indices[i], values[i]); |
| 258 | 258 |
++b; |
| 259 | 259 |
} |
| 260 | 260 |
|
| 261 | 261 |
} |
| 262 | 262 |
|
| 263 | 263 |
void CplexBase::_setCoeff(int row, int col, Value value) {
|
| 264 | 264 |
CPXchgcoef(cplexEnv(), _prob, row, col, value); |
| 265 | 265 |
} |
| 266 | 266 |
|
| 267 | 267 |
CplexBase::Value CplexBase::_getCoeff(int row, int col) const {
|
| 268 | 268 |
CplexBase::Value value; |
| 269 | 269 |
CPXgetcoef(cplexEnv(), _prob, row, col, &value); |
| 270 | 270 |
return value; |
| 271 | 271 |
} |
| 272 | 272 |
|
| 273 | 273 |
void CplexBase::_setColLowerBound(int i, Value value) {
|
| 274 | 274 |
const char s = 'L'; |
| 275 | 275 |
CPXchgbds(cplexEnv(), _prob, 1, &i, &s, &value); |
| 276 | 276 |
} |
| 277 | 277 |
|
| 278 | 278 |
CplexBase::Value CplexBase::_getColLowerBound(int i) const {
|
| 279 | 279 |
CplexBase::Value res; |
| 280 | 280 |
CPXgetlb(cplexEnv(), _prob, &res, i, i); |
| 281 | 281 |
return res <= -CPX_INFBOUND ? -INF : res; |
| 282 | 282 |
} |
| 283 | 283 |
|
| 284 | 284 |
void CplexBase::_setColUpperBound(int i, Value value) |
| 285 | 285 |
{
|
| 286 | 286 |
const char s = 'U'; |
| 287 | 287 |
CPXchgbds(cplexEnv(), _prob, 1, &i, &s, &value); |
| 288 | 288 |
} |
| 289 | 289 |
|
| 290 | 290 |
CplexBase::Value CplexBase::_getColUpperBound(int i) const {
|
| 291 | 291 |
CplexBase::Value res; |
| 292 | 292 |
CPXgetub(cplexEnv(), _prob, &res, i, i); |
| 293 | 293 |
return res >= CPX_INFBOUND ? INF : res; |
| 294 | 294 |
} |
| 295 | 295 |
|
| 296 | 296 |
CplexBase::Value CplexBase::_getRowLowerBound(int i) const {
|
| 297 | 297 |
char s; |
| 298 | 298 |
CPXgetsense(cplexEnv(), _prob, &s, i, i); |
| 299 | 299 |
CplexBase::Value res; |
| 300 | 300 |
|
| 301 | 301 |
switch (s) {
|
| 302 | 302 |
case 'G': |
| 303 | 303 |
case 'R': |
| 304 | 304 |
case 'E': |
| 305 | 305 |
CPXgetrhs(cplexEnv(), _prob, &res, i, i); |
| 306 | 306 |
return res <= -CPX_INFBOUND ? -INF : res; |
| 307 | 307 |
default: |
| 308 | 308 |
return -INF; |
| 309 | 309 |
} |
| 310 | 310 |
} |
| 311 | 311 |
|
| 312 | 312 |
CplexBase::Value CplexBase::_getRowUpperBound(int i) const {
|
| 313 | 313 |
char s; |
| 314 | 314 |
CPXgetsense(cplexEnv(), _prob, &s, i, i); |
| 315 | 315 |
CplexBase::Value res; |
| 316 | 316 |
|
| 317 | 317 |
switch (s) {
|
| 318 | 318 |
case 'L': |
| 319 | 319 |
case 'E': |
| 320 | 320 |
CPXgetrhs(cplexEnv(), _prob, &res, i, i); |
| 321 | 321 |
return res >= CPX_INFBOUND ? INF : res; |
| 322 | 322 |
case 'R': |
| 323 | 323 |
CPXgetrhs(cplexEnv(), _prob, &res, i, i); |
| 324 | 324 |
{
|
| 325 | 325 |
double rng; |
| 326 | 326 |
CPXgetrngval(cplexEnv(), _prob, &rng, i, i); |
| 327 | 327 |
res += rng; |
| 328 | 328 |
} |
| 329 | 329 |
return res >= CPX_INFBOUND ? INF : res; |
| 330 | 330 |
default: |
| 331 | 331 |
return INF; |
| 332 | 332 |
} |
| 333 | 333 |
} |
| 334 | 334 |
|
| 335 | 335 |
//This is easier to implement |
| 336 | 336 |
void CplexBase::_set_row_bounds(int i, Value lb, Value ub) {
|
| 337 | 337 |
if (lb == -INF) {
|
| 338 | 338 |
const char s = 'L'; |
| 339 | 339 |
CPXchgsense(cplexEnv(), _prob, 1, &i, &s); |
| 340 | 340 |
CPXchgrhs(cplexEnv(), _prob, 1, &i, &ub); |
| 341 | 341 |
} else if (ub == INF) {
|
| 342 | 342 |
const char s = 'G'; |
| 343 | 343 |
CPXchgsense(cplexEnv(), _prob, 1, &i, &s); |
| 344 | 344 |
CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb); |
| 345 | 345 |
} else if (lb == ub){
|
| 346 | 346 |
const char s = 'E'; |
| 347 | 347 |
CPXchgsense(cplexEnv(), _prob, 1, &i, &s); |
| 348 | 348 |
CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb); |
| 349 | 349 |
} else {
|
| 350 | 350 |
const char s = 'R'; |
| 351 | 351 |
CPXchgsense(cplexEnv(), _prob, 1, &i, &s); |
| 352 | 352 |
CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb); |
| 353 | 353 |
double len = ub - lb; |
| 354 | 354 |
CPXchgrngval(cplexEnv(), _prob, 1, &i, &len); |
| 355 | 355 |
} |
| 356 | 356 |
} |
| 357 | 357 |
|
| 358 | 358 |
void CplexBase::_setRowLowerBound(int i, Value lb) |
| 359 | 359 |
{
|
| 360 | 360 |
LEMON_ASSERT(lb != INF, "Invalid bound"); |
| 361 | 361 |
_set_row_bounds(i, lb, CplexBase::_getRowUpperBound(i)); |
| 362 | 362 |
} |
| 363 | 363 |
|
| 364 | 364 |
void CplexBase::_setRowUpperBound(int i, Value ub) |
| 365 | 365 |
{
|
| 366 | 366 |
|
| 367 | 367 |
LEMON_ASSERT(ub != -INF, "Invalid bound"); |
| 368 | 368 |
_set_row_bounds(i, CplexBase::_getRowLowerBound(i), ub); |
| 369 | 369 |
} |
| 370 | 370 |
|
| 371 | 371 |
void CplexBase::_setObjCoeffs(ExprIterator b, ExprIterator e) |
| 372 | 372 |
{
|
| 373 | 373 |
std::vector<int> indices; |
| 374 | 374 |
std::vector<Value> values; |
| 375 | 375 |
for(ExprIterator it=b; it!=e; ++it) {
|
| 376 | 376 |
indices.push_back(it->first); |
| 377 | 377 |
values.push_back(it->second); |
| 378 | 378 |
} |
| 379 | 379 |
CPXchgobj(cplexEnv(), _prob, values.size(), |
| 380 | 380 |
&indices.front(), &values.front()); |
| 381 | 381 |
|
| 382 | 382 |
} |
| 383 | 383 |
|
| 384 | 384 |
void CplexBase::_getObjCoeffs(InsertIterator b) const |
| 385 | 385 |
{
|
| 386 | 386 |
int num = CPXgetnumcols(cplexEnv(), _prob); |
| 387 | 387 |
std::vector<Value> x(num); |
| 388 | 388 |
|
| 389 | 389 |
CPXgetobj(cplexEnv(), _prob, &x.front(), 0, num - 1); |
| 390 | 390 |
for (int i = 0; i < num; ++i) {
|
| 391 | 391 |
if (x[i] != 0.0) {
|
| 392 | 392 |
*b = std::make_pair(i, x[i]); |
| 393 | 393 |
++b; |
| 394 | 394 |
} |
| 395 | 395 |
} |
| 396 | 396 |
} |
| 397 | 397 |
|
| 398 | 398 |
void CplexBase::_setObjCoeff(int i, Value obj_coef) |
| 399 | 399 |
{
|
| 400 | 400 |
CPXchgobj(cplexEnv(), _prob, 1, &i, &obj_coef); |
| 401 | 401 |
} |
| 402 | 402 |
|
| 403 | 403 |
CplexBase::Value CplexBase::_getObjCoeff(int i) const |
| 404 | 404 |
{
|
| 405 | 405 |
Value x; |
| 406 | 406 |
CPXgetobj(cplexEnv(), _prob, &x, i, i); |
| 407 | 407 |
return x; |
| 408 | 408 |
} |
| 409 | 409 |
|
| 410 | 410 |
void CplexBase::_setSense(CplexBase::Sense sense) {
|
| 411 | 411 |
switch (sense) {
|
| 412 | 412 |
case MIN: |
| 413 | 413 |
CPXchgobjsen(cplexEnv(), _prob, CPX_MIN); |
| 414 | 414 |
break; |
| 415 | 415 |
case MAX: |
| 416 | 416 |
CPXchgobjsen(cplexEnv(), _prob, CPX_MAX); |
| 417 | 417 |
break; |
| 418 | 418 |
} |
| 419 | 419 |
} |
| 420 | 420 |
|
| 421 | 421 |
CplexBase::Sense CplexBase::_getSense() const {
|
| 422 | 422 |
switch (CPXgetobjsen(cplexEnv(), _prob)) {
|
| 423 | 423 |
case CPX_MIN: |
| 424 | 424 |
return MIN; |
| 425 | 425 |
case CPX_MAX: |
| 426 | 426 |
return MAX; |
| 427 | 427 |
default: |
| 428 | 428 |
LEMON_ASSERT(false, "Invalid sense"); |
| 429 | 429 |
return CplexBase::Sense(); |
| 430 | 430 |
} |
| 431 | 431 |
} |
| 432 | 432 |
|
| 433 | 433 |
void CplexBase::_clear() {
|
| 434 | 434 |
CPXfreeprob(cplexEnv(),&_prob); |
| 435 | 435 |
int status; |
| 436 | 436 |
_prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem"); |
| 437 | 437 |
rows.clear(); |
| 438 | 438 |
cols.clear(); |
| 439 | 439 |
} |
| 440 | 440 |
|
| 441 | 441 |
// CplexLp members |
| 442 | 442 |
|
| 443 | 443 |
CplexLp::CplexLp() |
| 444 |
: LpBase(), |
|
| 444 |
: LpBase(), LpSolver(), CplexBase() {}
|
|
| 445 | 445 |
|
| 446 | 446 |
CplexLp::CplexLp(const CplexEnv& env) |
| 447 |
: LpBase(), |
|
| 447 |
: LpBase(), LpSolver(), CplexBase(env) {}
|
|
| 448 | 448 |
|
| 449 | 449 |
CplexLp::CplexLp(const CplexLp& other) |
| 450 |
: LpBase(), |
|
| 450 |
: LpBase(), LpSolver(), CplexBase(other) {}
|
|
| 451 | 451 |
|
| 452 | 452 |
CplexLp::~CplexLp() {}
|
| 453 | 453 |
|
| 454 | 454 |
CplexLp* CplexLp::newSolver() const { return new CplexLp; }
|
| 455 | 455 |
CplexLp* CplexLp::cloneSolver() const {return new CplexLp(*this); }
|
| 456 | 456 |
|
| 457 | 457 |
const char* CplexLp::_solverName() const { return "CplexLp"; }
|
| 458 | 458 |
|
| 459 | 459 |
void CplexLp::_clear_temporals() {
|
| 460 | 460 |
_col_status.clear(); |
| 461 | 461 |
_row_status.clear(); |
| 462 | 462 |
_primal_ray.clear(); |
| 463 | 463 |
_dual_ray.clear(); |
| 464 | 464 |
} |
| 465 | 465 |
|
| 466 | 466 |
// The routine returns zero unless an error occurred during the |
| 467 | 467 |
// optimization. Examples of errors include exhausting available |
| 468 | 468 |
// memory (CPXERR_NO_MEMORY) or encountering invalid data in the |
| 469 | 469 |
// CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a |
| 470 | 470 |
// user-specified CPLEX limit, or proving the model infeasible or |
| 471 | 471 |
// unbounded, are not considered errors. Note that a zero return |
| 472 | 472 |
// value does not necessarily mean that a solution exists. Use query |
| 473 | 473 |
// routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain |
| 474 | 474 |
// further information about the status of the optimization. |
| 475 | 475 |
CplexLp::SolveExitStatus CplexLp::convertStatus(int status) {
|
| 476 | 476 |
#if CPX_VERSION >= 800 |
| 477 | 477 |
if (status == 0) {
|
| 478 | 478 |
switch (CPXgetstat(cplexEnv(), _prob)) {
|
| 479 | 479 |
case CPX_STAT_OPTIMAL: |
| 480 | 480 |
case CPX_STAT_INFEASIBLE: |
| 481 | 481 |
case CPX_STAT_UNBOUNDED: |
| 482 | 482 |
return SOLVED; |
| 483 | 483 |
default: |
| 484 | 484 |
return UNSOLVED; |
| 485 | 485 |
} |
| 486 | 486 |
} else {
|
| 487 | 487 |
return UNSOLVED; |
| 488 | 488 |
} |
| 489 | 489 |
#else |
| 490 | 490 |
if (status == 0) {
|
| 491 | 491 |
//We want to exclude some cases |
| 492 | 492 |
switch (CPXgetstat(cplexEnv(), _prob)) {
|
| 493 | 493 |
case CPX_OBJ_LIM: |
| 494 | 494 |
case CPX_IT_LIM_FEAS: |
| 495 | 495 |
case CPX_IT_LIM_INFEAS: |
| 496 | 496 |
case CPX_TIME_LIM_FEAS: |
| 497 | 497 |
case CPX_TIME_LIM_INFEAS: |
| 498 | 498 |
return UNSOLVED; |
| 499 | 499 |
default: |
| 500 | 500 |
return SOLVED; |
| 501 | 501 |
} |
| 502 | 502 |
} else {
|
| 503 | 503 |
return UNSOLVED; |
| 504 | 504 |
} |
| 505 | 505 |
#endif |
| 506 | 506 |
} |
| 507 | 507 |
|
| 508 | 508 |
CplexLp::SolveExitStatus CplexLp::_solve() {
|
| 509 | 509 |
_clear_temporals(); |
| 510 | 510 |
return convertStatus(CPXlpopt(cplexEnv(), _prob)); |
| 511 | 511 |
} |
| 512 | 512 |
|
| 513 | 513 |
CplexLp::SolveExitStatus CplexLp::solvePrimal() {
|
| 514 | 514 |
_clear_temporals(); |
| 515 | 515 |
return convertStatus(CPXprimopt(cplexEnv(), _prob)); |
| 516 | 516 |
} |
| 517 | 517 |
|
| 518 | 518 |
CplexLp::SolveExitStatus CplexLp::solveDual() {
|
| 519 | 519 |
_clear_temporals(); |
| 520 | 520 |
return convertStatus(CPXdualopt(cplexEnv(), _prob)); |
| 521 | 521 |
} |
| 522 | 522 |
|
| 523 | 523 |
CplexLp::SolveExitStatus CplexLp::solveBarrier() {
|
| 524 | 524 |
_clear_temporals(); |
| 525 | 525 |
return convertStatus(CPXbaropt(cplexEnv(), _prob)); |
| 526 | 526 |
} |
| 527 | 527 |
|
| 528 | 528 |
CplexLp::Value CplexLp::_getPrimal(int i) const {
|
| 529 | 529 |
Value x; |
| 530 | 530 |
CPXgetx(cplexEnv(), _prob, &x, i, i); |
| 531 | 531 |
return x; |
| 532 | 532 |
} |
| 533 | 533 |
|
| 534 | 534 |
CplexLp::Value CplexLp::_getDual(int i) const {
|
| 535 | 535 |
Value y; |
| 536 | 536 |
CPXgetpi(cplexEnv(), _prob, &y, i, i); |
| 537 | 537 |
return y; |
| 538 | 538 |
} |
| 539 | 539 |
|
| 540 | 540 |
CplexLp::Value CplexLp::_getPrimalValue() const {
|
| 541 | 541 |
Value objval; |
| 542 | 542 |
CPXgetobjval(cplexEnv(), _prob, &objval); |
| 543 | 543 |
return objval; |
| 544 | 544 |
} |
| 545 | 545 |
|
| 546 | 546 |
CplexLp::VarStatus CplexLp::_getColStatus(int i) const {
|
| 547 | 547 |
if (_col_status.empty()) {
|
| 548 | 548 |
_col_status.resize(CPXgetnumcols(cplexEnv(), _prob)); |
| 549 | 549 |
CPXgetbase(cplexEnv(), _prob, &_col_status.front(), 0); |
| 550 | 550 |
} |
| 551 | 551 |
switch (_col_status[i]) {
|
| 552 | 552 |
case CPX_BASIC: |
| 553 | 553 |
return BASIC; |
| 554 | 554 |
case CPX_FREE_SUPER: |
| 555 | 555 |
return FREE; |
| 556 | 556 |
case CPX_AT_LOWER: |
| 557 | 557 |
return LOWER; |
| 558 | 558 |
case CPX_AT_UPPER: |
| 559 | 559 |
return UPPER; |
| 560 | 560 |
default: |
| 561 | 561 |
LEMON_ASSERT(false, "Wrong column status"); |
| 562 | 562 |
return CplexLp::VarStatus(); |
| 563 | 563 |
} |
| 564 | 564 |
} |
| 565 | 565 |
|
| 566 | 566 |
CplexLp::VarStatus CplexLp::_getRowStatus(int i) const {
|
| 567 | 567 |
if (_row_status.empty()) {
|
| 568 | 568 |
_row_status.resize(CPXgetnumrows(cplexEnv(), _prob)); |
| 569 | 569 |
CPXgetbase(cplexEnv(), _prob, 0, &_row_status.front()); |
| 570 | 570 |
} |
| 571 | 571 |
switch (_row_status[i]) {
|
| 572 | 572 |
case CPX_BASIC: |
| 573 | 573 |
return BASIC; |
| 574 | 574 |
case CPX_AT_LOWER: |
| 575 | 575 |
{
|
| 576 | 576 |
char s; |
| 577 | 577 |
CPXgetsense(cplexEnv(), _prob, &s, i, i); |
| 578 | 578 |
return s != 'L' ? LOWER : UPPER; |
| 579 | 579 |
} |
| 580 | 580 |
case CPX_AT_UPPER: |
| 581 | 581 |
return UPPER; |
| 582 | 582 |
default: |
| 583 | 583 |
LEMON_ASSERT(false, "Wrong row status"); |
| 584 | 584 |
return CplexLp::VarStatus(); |
| 585 | 585 |
} |
| 586 | 586 |
} |
| 587 | 587 |
|
| 588 | 588 |
CplexLp::Value CplexLp::_getPrimalRay(int i) const {
|
| 589 | 589 |
if (_primal_ray.empty()) {
|
| 590 | 590 |
_primal_ray.resize(CPXgetnumcols(cplexEnv(), _prob)); |
| 591 | 591 |
CPXgetray(cplexEnv(), _prob, &_primal_ray.front()); |
| 592 | 592 |
} |
| 593 | 593 |
return _primal_ray[i]; |
| 594 | 594 |
} |
| 595 | 595 |
|
| 596 | 596 |
CplexLp::Value CplexLp::_getDualRay(int i) const {
|
| 597 | 597 |
if (_dual_ray.empty()) {
|
| 598 | 598 |
|
| 599 | 599 |
} |
| 600 | 600 |
return _dual_ray[i]; |
| 601 | 601 |
} |
| 602 | 602 |
|
| 603 | 603 |
//7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!) |
| 604 | 604 |
// This table lists the statuses, returned by the CPXgetstat() |
| 605 | 605 |
// routine, for solutions to LP problems or mixed integer problems. If |
| 606 | 606 |
// no solution exists, the return value is zero. |
| 607 | 607 |
|
| 608 | 608 |
// For Simplex, Barrier |
| 609 | 609 |
// 1 CPX_OPTIMAL |
| 610 | 610 |
// Optimal solution found |
| 611 | 611 |
// 2 CPX_INFEASIBLE |
| 612 | 612 |
// Problem infeasible |
| 613 | 613 |
// 3 CPX_UNBOUNDED |
| 614 | 614 |
// Problem unbounded |
| 615 | 615 |
// 4 CPX_OBJ_LIM |
| 616 | 616 |
// Objective limit exceeded in Phase II |
| 617 | 617 |
// 5 CPX_IT_LIM_FEAS |
| 618 | 618 |
// Iteration limit exceeded in Phase II |
| 619 | 619 |
// 6 CPX_IT_LIM_INFEAS |
| 620 | 620 |
// Iteration limit exceeded in Phase I |
| 621 | 621 |
// 7 CPX_TIME_LIM_FEAS |
| 622 | 622 |
// Time limit exceeded in Phase II |
| 623 | 623 |
// 8 CPX_TIME_LIM_INFEAS |
| 624 | 624 |
// Time limit exceeded in Phase I |
| 625 | 625 |
// 9 CPX_NUM_BEST_FEAS |
| 626 | 626 |
// Problem non-optimal, singularities in Phase II |
| 627 | 627 |
// 10 CPX_NUM_BEST_INFEAS |
| 628 | 628 |
// Problem non-optimal, singularities in Phase I |
| 629 | 629 |
// 11 CPX_OPTIMAL_INFEAS |
| 630 | 630 |
// Optimal solution found, unscaled infeasibilities |
| 631 | 631 |
// 12 CPX_ABORT_FEAS |
| 632 | 632 |
// Aborted in Phase II |
| 633 | 633 |
// 13 CPX_ABORT_INFEAS |
| 634 | 634 |
// Aborted in Phase I |
| 635 | 635 |
// 14 CPX_ABORT_DUAL_INFEAS |
| 636 | 636 |
// Aborted in barrier, dual infeasible |
| 637 | 637 |
// 15 CPX_ABORT_PRIM_INFEAS |
| 638 | 638 |
// Aborted in barrier, primal infeasible |
| 639 | 639 |
// 16 CPX_ABORT_PRIM_DUAL_INFEAS |
| 640 | 640 |
// Aborted in barrier, primal and dual infeasible |
| 641 | 641 |
// 17 CPX_ABORT_PRIM_DUAL_FEAS |
| 642 | 642 |
// Aborted in barrier, primal and dual feasible |
| 643 | 643 |
// 18 CPX_ABORT_CROSSOVER |
| 644 | 644 |
// Aborted in crossover |
| 645 | 645 |
// 19 CPX_INForUNBD |
| 646 | 646 |
// Infeasible or unbounded |
| 647 | 647 |
// 20 CPX_PIVOT |
| 648 | 648 |
// User pivot used |
| 649 | 649 |
// |
| 650 | 650 |
// Ezeket hova tegyem: |
| 651 | 651 |
// ??case CPX_ABORT_DUAL_INFEAS |
| 652 | 652 |
// ??case CPX_ABORT_CROSSOVER |
| 653 | 653 |
// ??case CPX_INForUNBD |
| 654 | 654 |
// ??case CPX_PIVOT |
| 655 | 655 |
|
| 656 | 656 |
//Some more interesting stuff: |
| 657 | 657 |
|
| 658 | 658 |
// CPX_PARAM_PROBMETHOD 1062 int LPMETHOD |
| 659 | 659 |
// 0 Automatic |
| 660 | 660 |
// 1 Primal Simplex |
| 661 | 661 |
// 2 Dual Simplex |
| 662 | 662 |
// 3 Network Simplex |
| 663 | 663 |
// 4 Standard Barrier |
| 664 | 664 |
// Default: 0 |
| 665 | 665 |
// Description: Method for linear optimization. |
| 666 | 666 |
// Determines which algorithm is used when CPXlpopt() (or "optimize" |
| 667 | 667 |
// in the Interactive Optimizer) is called. Currently the behavior of |
| 668 | 668 |
// the "Automatic" setting is that CPLEX simply invokes the dual |
| 669 | 669 |
// simplex method, but this capability may be expanded in the future |
| 670 | 670 |
// so that CPLEX chooses the method based on problem characteristics |
| 671 | 671 |
#if CPX_VERSION < 900 |
| 672 | 672 |
void statusSwitch(CPXENVptr cplexEnv(),int& stat){
|
| 673 | 673 |
int lpmethod; |
| 674 | 674 |
CPXgetintparam (cplexEnv(),CPX_PARAM_PROBMETHOD,&lpmethod); |
| 675 | 675 |
if (lpmethod==2){
|
| 676 | 676 |
if (stat==CPX_UNBOUNDED){
|
| 677 | 677 |
stat=CPX_INFEASIBLE; |
| 678 | 678 |
} |
| 679 | 679 |
else{
|
| 680 | 680 |
if (stat==CPX_INFEASIBLE) |
| 681 | 681 |
stat=CPX_UNBOUNDED; |
| 682 | 682 |
} |
| 683 | 683 |
} |
| 684 | 684 |
} |
| 685 | 685 |
#else |
| 686 | 686 |
void statusSwitch(CPXENVptr,int&){}
|
| 687 | 687 |
#endif |
| 688 | 688 |
|
| 689 | 689 |
CplexLp::ProblemType CplexLp::_getPrimalType() const {
|
| 690 | 690 |
// Unboundedness not treated well: the following is from cplex 9.0 doc |
| 691 | 691 |
// About Unboundedness |
| 692 | 692 |
|
| 693 | 693 |
// The treatment of models that are unbounded involves a few |
| 694 | 694 |
// subtleties. Specifically, a declaration of unboundedness means that |
| 695 | 695 |
// ILOG CPLEX has determined that the model has an unbounded |
| 696 | 696 |
// ray. Given any feasible solution x with objective z, a multiple of |
| 697 | 697 |
// the unbounded ray can be added to x to give a feasible solution |
| 698 | 698 |
// with objective z-1 (or z+1 for maximization models). Thus, if a |
| 699 | 699 |
// feasible solution exists, then the optimal objective is |
| 700 | 700 |
// unbounded. Note that ILOG CPLEX has not necessarily concluded that |
| 701 | 701 |
// a feasible solution exists. Users can call the routine CPXsolninfo |
| 702 | 702 |
// to determine whether ILOG CPLEX has also concluded that the model |
| 703 | 703 |
// has a feasible solution. |
| 704 | 704 |
|
| 705 | 705 |
int stat = CPXgetstat(cplexEnv(), _prob); |
| 706 | 706 |
#if CPX_VERSION >= 800 |
| 707 | 707 |
switch (stat) |
| 708 | 708 |
{
|
| 709 | 709 |
case CPX_STAT_OPTIMAL: |
| 710 | 710 |
return OPTIMAL; |
| 711 | 711 |
case CPX_STAT_UNBOUNDED: |
| 712 | 712 |
return UNBOUNDED; |
| 713 | 713 |
case CPX_STAT_INFEASIBLE: |
| 714 | 714 |
return INFEASIBLE; |
| 715 | 715 |
default: |
| 716 | 716 |
return UNDEFINED; |
| 717 | 717 |
} |
| 718 | 718 |
#else |
| 719 | 719 |
statusSwitch(cplexEnv(),stat); |
| 720 | 720 |
//CPXgetstat(cplexEnv(), _prob); |
| 721 | 721 |
//printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
|
| 722 | 722 |
switch (stat) {
|
| 723 | 723 |
case 0: |
| 724 | 724 |
return UNDEFINED; //Undefined |
| 725 | 725 |
case CPX_OPTIMAL://Optimal |
| 726 | 726 |
return OPTIMAL; |
| 727 | 727 |
case CPX_UNBOUNDED://Unbounded |
| 728 | 728 |
return INFEASIBLE;//In case of dual simplex |
| 729 | 729 |
//return UNBOUNDED; |
| 730 | 730 |
case CPX_INFEASIBLE://Infeasible |
| 731 | 731 |
// case CPX_IT_LIM_INFEAS: |
| 732 | 732 |
// case CPX_TIME_LIM_INFEAS: |
| 733 | 733 |
// case CPX_NUM_BEST_INFEAS: |
| 734 | 734 |
// case CPX_OPTIMAL_INFEAS: |
| 735 | 735 |
// case CPX_ABORT_INFEAS: |
| 736 | 736 |
// case CPX_ABORT_PRIM_INFEAS: |
| 737 | 737 |
// case CPX_ABORT_PRIM_DUAL_INFEAS: |
| 738 | 738 |
return UNBOUNDED;//In case of dual simplex |
| 739 | 739 |
//return INFEASIBLE; |
| 740 | 740 |
// case CPX_OBJ_LIM: |
| 741 | 741 |
// case CPX_IT_LIM_FEAS: |
| 742 | 742 |
// case CPX_TIME_LIM_FEAS: |
| 743 | 743 |
// case CPX_NUM_BEST_FEAS: |
| 744 | 744 |
// case CPX_ABORT_FEAS: |
| 745 | 745 |
// case CPX_ABORT_PRIM_DUAL_FEAS: |
| 746 | 746 |
// return FEASIBLE; |
| 747 | 747 |
default: |
| 748 | 748 |
return UNDEFINED; //Everything else comes here |
| 749 | 749 |
//FIXME error |
| 750 | 750 |
} |
| 751 | 751 |
#endif |
| 752 | 752 |
} |
| 753 | 753 |
|
| 754 | 754 |
//9.0-as cplex verzio statusai |
| 755 | 755 |
// CPX_STAT_ABORT_DUAL_OBJ_LIM |
| 756 | 756 |
// CPX_STAT_ABORT_IT_LIM |
| 757 | 757 |
// CPX_STAT_ABORT_OBJ_LIM |
| 758 | 758 |
// CPX_STAT_ABORT_PRIM_OBJ_LIM |
| 759 | 759 |
// CPX_STAT_ABORT_TIME_LIM |
| 760 | 760 |
// CPX_STAT_ABORT_USER |
| 761 | 761 |
// CPX_STAT_FEASIBLE_RELAXED |
| 762 | 762 |
// CPX_STAT_INFEASIBLE |
| 763 | 763 |
// CPX_STAT_INForUNBD |
| 764 | 764 |
// CPX_STAT_NUM_BEST |
| 765 | 765 |
// CPX_STAT_OPTIMAL |
| 766 | 766 |
// CPX_STAT_OPTIMAL_FACE_UNBOUNDED |
| 767 | 767 |
// CPX_STAT_OPTIMAL_INFEAS |
| 768 | 768 |
// CPX_STAT_OPTIMAL_RELAXED |
| 769 | 769 |
// CPX_STAT_UNBOUNDED |
| 770 | 770 |
|
| 771 | 771 |
CplexLp::ProblemType CplexLp::_getDualType() const {
|
| 772 | 772 |
int stat = CPXgetstat(cplexEnv(), _prob); |
| 773 | 773 |
#if CPX_VERSION >= 800 |
| 774 | 774 |
switch (stat) {
|
| 775 | 775 |
case CPX_STAT_OPTIMAL: |
| 776 | 776 |
return OPTIMAL; |
| 777 | 777 |
case CPX_STAT_UNBOUNDED: |
| 778 | 778 |
return INFEASIBLE; |
| 779 | 779 |
default: |
| 780 | 780 |
return UNDEFINED; |
| 781 | 781 |
} |
| 782 | 782 |
#else |
| 783 | 783 |
statusSwitch(cplexEnv(),stat); |
| 784 | 784 |
switch (stat) {
|
| 785 | 785 |
case 0: |
| 786 | 786 |
return UNDEFINED; //Undefined |
| 787 | 787 |
case CPX_OPTIMAL://Optimal |
| 788 | 788 |
return OPTIMAL; |
| 789 | 789 |
case CPX_UNBOUNDED: |
| 790 | 790 |
return INFEASIBLE; |
| 791 | 791 |
default: |
| 792 | 792 |
return UNDEFINED; //Everything else comes here |
| 793 | 793 |
//FIXME error |
| 794 | 794 |
} |
| 795 | 795 |
#endif |
| 796 | 796 |
} |
| 797 | 797 |
|
| 798 | 798 |
// CplexMip members |
| 799 | 799 |
|
| 800 | 800 |
CplexMip::CplexMip() |
| 801 |
: LpBase(), |
|
| 801 |
: LpBase(), MipSolver(), CplexBase() {
|
|
| 802 | 802 |
|
| 803 | 803 |
#if CPX_VERSION < 800 |
| 804 | 804 |
CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MIP); |
| 805 | 805 |
#else |
| 806 | 806 |
CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MILP); |
| 807 | 807 |
#endif |
| 808 | 808 |
} |
| 809 | 809 |
|
| 810 | 810 |
CplexMip::CplexMip(const CplexEnv& env) |
| 811 |
: LpBase(), |
|
| 811 |
: LpBase(), MipSolver(), CplexBase(env) {
|
|
| 812 | 812 |
|
| 813 | 813 |
#if CPX_VERSION < 800 |
| 814 | 814 |
CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MIP); |
| 815 | 815 |
#else |
| 816 | 816 |
CPXchgprobtype(cplexEnv(), _prob, CPXPROB_MILP); |
| 817 | 817 |
#endif |
| 818 | 818 |
|
| 819 | 819 |
} |
| 820 | 820 |
|
| 821 | 821 |
CplexMip::CplexMip(const CplexMip& other) |
| 822 |
: LpBase(), |
|
| 822 |
: LpBase(), MipSolver(), CplexBase(other) {}
|
|
| 823 | 823 |
|
| 824 | 824 |
CplexMip::~CplexMip() {}
|
| 825 | 825 |
|
| 826 | 826 |
CplexMip* CplexMip::newSolver() const { return new CplexMip; }
|
| 827 | 827 |
CplexMip* CplexMip::cloneSolver() const {return new CplexMip(*this); }
|
| 828 | 828 |
|
| 829 | 829 |
const char* CplexMip::_solverName() const { return "CplexMip"; }
|
| 830 | 830 |
|
| 831 | 831 |
void CplexMip::_setColType(int i, CplexMip::ColTypes col_type) {
|
| 832 | 832 |
|
| 833 | 833 |
// Note If a variable is to be changed to binary, a call to CPXchgbds |
| 834 | 834 |
// should also be made to change the bounds to 0 and 1. |
| 835 | 835 |
|
| 836 | 836 |
switch (col_type){
|
| 837 | 837 |
case INTEGER: {
|
| 838 | 838 |
const char t = 'I'; |
| 839 | 839 |
CPXchgctype (cplexEnv(), _prob, 1, &i, &t); |
| 840 | 840 |
} break; |
| 841 | 841 |
case REAL: {
|
| 842 | 842 |
const char t = 'C'; |
| 843 | 843 |
CPXchgctype (cplexEnv(), _prob, 1, &i, &t); |
| 844 | 844 |
} break; |
| 845 | 845 |
default: |
| 846 | 846 |
break; |
| 847 | 847 |
} |
| 848 | 848 |
} |
| 849 | 849 |
|
| 850 | 850 |
CplexMip::ColTypes CplexMip::_getColType(int i) const {
|
| 851 | 851 |
char t; |
| 852 | 852 |
CPXgetctype (cplexEnv(), _prob, &t, i, i); |
| 853 | 853 |
switch (t) {
|
| 854 | 854 |
case 'I': |
| 855 | 855 |
return INTEGER; |
| 856 | 856 |
case 'C': |
| 857 | 857 |
return REAL; |
| 858 | 858 |
default: |
| 859 | 859 |
LEMON_ASSERT(false, "Invalid column type"); |
| 860 | 860 |
return ColTypes(); |
| 861 | 861 |
} |
| 862 | 862 |
|
| 863 | 863 |
} |
| 864 | 864 |
|
| 865 | 865 |
CplexMip::SolveExitStatus CplexMip::_solve() {
|
| 866 | 866 |
int status; |
| 867 | 867 |
status = CPXmipopt (cplexEnv(), _prob); |
| 868 | 868 |
if (status==0) |
| 869 | 869 |
return SOLVED; |
| 870 | 870 |
else |
| 871 | 871 |
return UNSOLVED; |
| 872 | 872 |
|
| 873 | 873 |
} |
| 874 | 874 |
|
| 875 | 875 |
|
| 876 | 876 |
CplexMip::ProblemType CplexMip::_getType() const {
|
| 877 | 877 |
|
| 878 | 878 |
int stat = CPXgetstat(cplexEnv(), _prob); |
| 879 | 879 |
|
| 880 | 880 |
//Fortunately, MIP statuses did not change for cplex 8.0 |
| 881 | 881 |
switch (stat) {
|
| 882 | 882 |
case CPXMIP_OPTIMAL: |
| 883 | 883 |
// Optimal integer solution has been found. |
| 884 | 884 |
case CPXMIP_OPTIMAL_TOL: |
| 885 | 885 |
// Optimal soluton with the tolerance defined by epgap or epagap has |
| 886 | 886 |
// been found. |
| 887 | 887 |
return OPTIMAL; |
| 888 | 888 |
//This also exists in later issues |
| 889 | 889 |
// case CPXMIP_UNBOUNDED: |
| 890 | 890 |
//return UNBOUNDED; |
| 891 | 891 |
case CPXMIP_INFEASIBLE: |
| 892 | 892 |
return INFEASIBLE; |
| 893 | 893 |
default: |
| 894 | 894 |
return UNDEFINED; |
| 895 | 895 |
} |
| 896 | 896 |
//Unboundedness not treated well: the following is from cplex 9.0 doc |
| 897 | 897 |
// About Unboundedness |
| 898 | 898 |
|
| 899 | 899 |
// The treatment of models that are unbounded involves a few |
| 900 | 900 |
// subtleties. Specifically, a declaration of unboundedness means that |
| 901 | 901 |
// ILOG CPLEX has determined that the model has an unbounded |
| 902 | 902 |
// ray. Given any feasible solution x with objective z, a multiple of |
| 903 | 903 |
// the unbounded ray can be added to x to give a feasible solution |
| 904 | 904 |
// with objective z-1 (or z+1 for maximization models). Thus, if a |
| 905 | 905 |
// feasible solution exists, then the optimal objective is |
| 906 | 906 |
// unbounded. Note that ILOG CPLEX has not necessarily concluded that |
| 907 | 907 |
// a feasible solution exists. Users can call the routine CPXsolninfo |
| 908 | 908 |
// to determine whether ILOG CPLEX has also concluded that the model |
| 909 | 909 |
// has a feasible solution. |
| 910 | 910 |
} |
| 911 | 911 |
|
| 912 | 912 |
CplexMip::Value CplexMip::_getSol(int i) const {
|
| 913 | 913 |
Value x; |
| 914 | 914 |
CPXgetmipx(cplexEnv(), _prob, &x, i, i); |
| 915 | 915 |
return x; |
| 916 | 916 |
} |
| 917 | 917 |
|
| 918 | 918 |
CplexMip::Value CplexMip::_getSolValue() const {
|
| 919 | 919 |
Value objval; |
| 920 | 920 |
CPXgetmipobjval(cplexEnv(), _prob, &objval); |
| 921 | 921 |
return objval; |
| 922 | 922 |
} |
| 923 | 923 |
|
| 924 | 924 |
} //namespace lemon |
| 925 | 925 |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#ifndef LEMON_CPLEX_H |
| 20 | 20 |
#define LEMON_CPLEX_H |
| 21 | 21 |
|
| 22 | 22 |
///\file |
| 23 | 23 |
///\brief Header of the LEMON-CPLEX lp solver interface. |
| 24 | 24 |
|
| 25 | 25 |
#include <lemon/lp_base.h> |
| 26 | 26 |
|
| 27 | 27 |
struct cpxenv; |
| 28 | 28 |
struct cpxlp; |
| 29 | 29 |
|
| 30 | 30 |
namespace lemon {
|
| 31 | 31 |
|
| 32 | 32 |
/// \brief Reference counted wrapper around cpxenv pointer |
| 33 | 33 |
/// |
| 34 | 34 |
/// The cplex uses environment object which is responsible for |
| 35 | 35 |
/// checking the proper license usage. This class provides a simple |
| 36 | 36 |
/// interface for share the environment object between different |
| 37 | 37 |
/// problems. |
| 38 | 38 |
class CplexEnv {
|
| 39 | 39 |
friend class CplexBase; |
| 40 | 40 |
private: |
| 41 | 41 |
cpxenv* _env; |
| 42 | 42 |
mutable int* _cnt; |
| 43 | 43 |
|
| 44 | 44 |
public: |
| 45 | 45 |
|
| 46 | 46 |
/// \brief This exception is thrown when the license check is not |
| 47 | 47 |
/// sufficient |
| 48 | 48 |
class LicenseError : public Exception {
|
| 49 | 49 |
friend class CplexEnv; |
| 50 | 50 |
private: |
| 51 | 51 |
|
| 52 | 52 |
LicenseError(int status); |
| 53 | 53 |
char _message[510]; |
| 54 | 54 |
|
| 55 | 55 |
public: |
| 56 | 56 |
|
| 57 | 57 |
/// The short error message |
| 58 | 58 |
virtual const char* what() const throw() {
|
| 59 | 59 |
return _message; |
| 60 | 60 |
} |
| 61 | 61 |
}; |
| 62 | 62 |
|
| 63 | 63 |
/// Constructor |
| 64 | 64 |
CplexEnv(); |
| 65 | 65 |
/// Shallow copy constructor |
| 66 | 66 |
CplexEnv(const CplexEnv&); |
| 67 | 67 |
/// Shallow assignement |
| 68 | 68 |
CplexEnv& operator=(const CplexEnv&); |
| 69 | 69 |
/// Destructor |
| 70 | 70 |
virtual ~CplexEnv(); |
| 71 | 71 |
|
| 72 | 72 |
protected: |
| 73 | 73 |
|
| 74 | 74 |
cpxenv* cplexEnv() { return _env; }
|
| 75 | 75 |
const cpxenv* cplexEnv() const { return _env; }
|
| 76 | 76 |
}; |
| 77 | 77 |
|
| 78 | 78 |
/// \brief Base interface for the CPLEX LP and MIP solver |
| 79 | 79 |
/// |
| 80 | 80 |
/// This class implements the common interface of the CPLEX LP and |
| 81 | 81 |
/// MIP solvers. |
| 82 | 82 |
/// \ingroup lp_group |
| 83 | 83 |
class CplexBase : virtual public LpBase {
|
| 84 | 84 |
protected: |
| 85 | 85 |
|
| 86 | 86 |
CplexEnv _env; |
| 87 | 87 |
cpxlp* _prob; |
| 88 | 88 |
|
| 89 | 89 |
CplexBase(); |
| 90 | 90 |
CplexBase(const CplexEnv&); |
| 91 | 91 |
CplexBase(const CplexBase &); |
| 92 | 92 |
virtual ~CplexBase(); |
| 93 | 93 |
|
| 94 | 94 |
virtual int _addCol(); |
| 95 | 95 |
virtual int _addRow(); |
| 96 | 96 |
|
| 97 | 97 |
virtual void _eraseCol(int i); |
| 98 | 98 |
virtual void _eraseRow(int i); |
| 99 | 99 |
|
| 100 | 100 |
virtual void _eraseColId(int i); |
| 101 | 101 |
virtual void _eraseRowId(int i); |
| 102 | 102 |
|
| 103 | 103 |
virtual void _getColName(int col, std::string& name) const; |
| 104 | 104 |
virtual void _setColName(int col, const std::string& name); |
| 105 | 105 |
virtual int _colByName(const std::string& name) const; |
| 106 | 106 |
|
| 107 | 107 |
virtual void _getRowName(int row, std::string& name) const; |
| 108 | 108 |
virtual void _setRowName(int row, const std::string& name); |
| 109 | 109 |
virtual int _rowByName(const std::string& name) const; |
| 110 | 110 |
|
| 111 | 111 |
virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e); |
| 112 | 112 |
virtual void _getRowCoeffs(int i, InsertIterator b) const; |
| 113 | 113 |
|
| 114 | 114 |
virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e); |
| 115 | 115 |
virtual void _getColCoeffs(int i, InsertIterator b) const; |
| 116 | 116 |
|
| 117 | 117 |
virtual void _setCoeff(int row, int col, Value value); |
| 118 | 118 |
virtual Value _getCoeff(int row, int col) const; |
| 119 | 119 |
|
| 120 | 120 |
virtual void _setColLowerBound(int i, Value value); |
| 121 | 121 |
virtual Value _getColLowerBound(int i) const; |
| 122 | 122 |
|
| 123 | 123 |
virtual void _setColUpperBound(int i, Value value); |
| 124 | 124 |
virtual Value _getColUpperBound(int i) const; |
| 125 | 125 |
|
| 126 | 126 |
private: |
| 127 | 127 |
void _set_row_bounds(int i, Value lb, Value ub); |
| 128 | 128 |
protected: |
| 129 | 129 |
|
| 130 | 130 |
virtual void _setRowLowerBound(int i, Value value); |
| 131 | 131 |
virtual Value _getRowLowerBound(int i) const; |
| 132 | 132 |
|
| 133 | 133 |
virtual void _setRowUpperBound(int i, Value value); |
| 134 | 134 |
virtual Value _getRowUpperBound(int i) const; |
| 135 | 135 |
|
| 136 | 136 |
virtual void _setObjCoeffs(ExprIterator b, ExprIterator e); |
| 137 | 137 |
virtual void _getObjCoeffs(InsertIterator b) const; |
| 138 | 138 |
|
| 139 | 139 |
virtual void _setObjCoeff(int i, Value obj_coef); |
| 140 | 140 |
virtual Value _getObjCoeff(int i) const; |
| 141 | 141 |
|
| 142 | 142 |
virtual void _setSense(Sense sense); |
| 143 | 143 |
virtual Sense _getSense() const; |
| 144 | 144 |
|
| 145 | 145 |
virtual void _clear(); |
| 146 | 146 |
|
| 147 | 147 |
public: |
| 148 | 148 |
|
| 149 | 149 |
/// Returns the used \c CplexEnv instance |
| 150 | 150 |
const CplexEnv& env() const { return _env; }
|
| 151 | 151 |
/// |
| 152 | 152 |
const cpxenv* cplexEnv() const { return _env.cplexEnv(); }
|
| 153 | 153 |
|
| 154 | 154 |
cpxlp* cplexLp() { return _prob; }
|
| 155 | 155 |
const cpxlp* cplexLp() const { return _prob; }
|
| 156 | 156 |
|
| 157 | 157 |
}; |
| 158 | 158 |
|
| 159 | 159 |
/// \brief Interface for the CPLEX LP solver |
| 160 | 160 |
/// |
| 161 | 161 |
/// This class implements an interface for the CPLEX LP solver. |
| 162 | 162 |
///\ingroup lp_group |
| 163 | 163 |
class CplexLp : public LpSolver, public CplexBase {
|
| 164 | 164 |
public: |
| 165 | 165 |
/// \e |
| 166 | 166 |
CplexLp(); |
| 167 | 167 |
/// \e |
| 168 | 168 |
CplexLp(const CplexEnv&); |
| 169 | 169 |
/// \e |
| 170 | 170 |
CplexLp(const CplexLp&); |
| 171 | 171 |
/// \e |
| 172 | 172 |
virtual ~CplexLp(); |
| 173 | 173 |
|
| 174 | 174 |
/// \e |
| 175 | 175 |
virtual CplexLp* cloneSolver() const; |
| 176 | 176 |
/// \e |
| 177 | 177 |
virtual CplexLp* newSolver() const; |
| 178 | 178 |
|
| 179 | 179 |
private: |
| 180 | 180 |
|
| 181 | 181 |
// these values cannot retrieved element by element |
| 182 | 182 |
mutable std::vector<int> _col_status; |
| 183 | 183 |
mutable std::vector<int> _row_status; |
| 184 | 184 |
|
| 185 | 185 |
mutable std::vector<Value> _primal_ray; |
| 186 | 186 |
mutable std::vector<Value> _dual_ray; |
| 187 | 187 |
|
| 188 | 188 |
void _clear_temporals(); |
| 189 | 189 |
|
| 190 | 190 |
SolveExitStatus convertStatus(int status); |
| 191 | 191 |
|
| 192 | 192 |
protected: |
| 193 | 193 |
|
| 194 | 194 |
virtual const char* _solverName() const; |
| 195 | 195 |
|
| 196 | 196 |
virtual SolveExitStatus _solve(); |
| 197 | 197 |
virtual Value _getPrimal(int i) const; |
| 198 | 198 |
virtual Value _getDual(int i) const; |
| 199 | 199 |
virtual Value _getPrimalValue() const; |
| 200 | 200 |
|
| 201 | 201 |
virtual VarStatus _getColStatus(int i) const; |
| 202 | 202 |
virtual VarStatus _getRowStatus(int i) const; |
| 203 | 203 |
|
| 204 | 204 |
virtual Value _getPrimalRay(int i) const; |
| 205 | 205 |
virtual Value _getDualRay(int i) const; |
| 206 | 206 |
|
| 207 | 207 |
virtual ProblemType _getPrimalType() const; |
| 208 | 208 |
virtual ProblemType _getDualType() const; |
| 209 | 209 |
|
| 210 | 210 |
public: |
| 211 | 211 |
|
| 212 | 212 |
/// Solve with primal simplex method |
| 213 | 213 |
SolveExitStatus solvePrimal(); |
| 214 | 214 |
|
| 215 | 215 |
/// Solve with dual simplex method |
| 216 | 216 |
SolveExitStatus solveDual(); |
| 217 | 217 |
|
| 218 | 218 |
/// Solve with barrier method |
| 219 | 219 |
SolveExitStatus solveBarrier(); |
| 220 | 220 |
|
| 221 | 221 |
}; |
| 222 | 222 |
|
| 223 | 223 |
/// \brief Interface for the CPLEX MIP solver |
| 224 | 224 |
/// |
| 225 | 225 |
/// This class implements an interface for the CPLEX MIP solver. |
| 226 | 226 |
///\ingroup lp_group |
| 227 | 227 |
class CplexMip : public MipSolver, public CplexBase {
|
| 228 | 228 |
public: |
| 229 | 229 |
/// \e |
| 230 | 230 |
CplexMip(); |
| 231 | 231 |
/// \e |
| 232 | 232 |
CplexMip(const CplexEnv&); |
| 233 | 233 |
/// \e |
| 234 | 234 |
CplexMip(const CplexMip&); |
| 235 | 235 |
/// \e |
| 236 | 236 |
virtual ~CplexMip(); |
| 237 | 237 |
|
| 238 |
/// \e |
|
| 239 |
virtual CplexMip* cloneSolver() const; |
|
| 240 |
/// \e |
|
| 241 |
virtual CplexMip* newSolver() const; |
|
| 242 |
|
|
| 238 | 243 |
protected: |
| 239 | 244 |
|
| 240 |
virtual CplexMip* _cloneSolver() const; |
|
| 241 |
virtual CplexMip* _newSolver() const; |
|
| 242 | 245 |
|
| 243 | 246 |
virtual const char* _solverName() const; |
| 244 | 247 |
|
| 245 | 248 |
virtual ColTypes _getColType(int col) const; |
| 246 | 249 |
virtual void _setColType(int col, ColTypes col_type); |
| 247 | 250 |
|
| 248 | 251 |
virtual SolveExitStatus _solve(); |
| 249 | 252 |
virtual ProblemType _getType() const; |
| 250 | 253 |
virtual Value _getSol(int i) const; |
| 251 | 254 |
virtual Value _getSolValue() const; |
| 252 | 255 |
|
| 253 | 256 |
}; |
| 254 | 257 |
|
| 255 | 258 |
} //END OF NAMESPACE LEMON |
| 256 | 259 |
|
| 257 | 260 |
#endif //LEMON_CPLEX_H |
| 258 | 261 |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
///\file |
| 20 | 20 |
///\brief Implementation of the LEMON GLPK LP and MIP solver interface. |
| 21 | 21 |
|
| 22 | 22 |
#include <lemon/glpk.h> |
| 23 | 23 |
#include <glpk.h> |
| 24 | 24 |
|
| 25 | 25 |
#include <lemon/assert.h> |
| 26 | 26 |
|
| 27 | 27 |
namespace lemon {
|
| 28 | 28 |
|
| 29 | 29 |
// GlpkBase members |
| 30 | 30 |
|
| 31 | 31 |
GlpkBase::GlpkBase() : LpBase() {
|
| 32 | 32 |
lp = glp_create_prob(); |
| 33 | 33 |
glp_create_index(lp); |
| 34 | 34 |
} |
| 35 | 35 |
|
| 36 | 36 |
GlpkBase::GlpkBase(const GlpkBase &other) : LpBase() {
|
| 37 | 37 |
lp = glp_create_prob(); |
| 38 | 38 |
glp_copy_prob(lp, other.lp, GLP_ON); |
| 39 | 39 |
glp_create_index(lp); |
| 40 | 40 |
rows = other.rows; |
| 41 | 41 |
cols = other.cols; |
| 42 | 42 |
} |
| 43 | 43 |
|
| 44 | 44 |
GlpkBase::~GlpkBase() {
|
| 45 | 45 |
glp_delete_prob(lp); |
| 46 | 46 |
} |
| 47 | 47 |
|
| 48 | 48 |
int GlpkBase::_addCol() {
|
| 49 | 49 |
int i = glp_add_cols(lp, 1); |
| 50 | 50 |
glp_set_col_bnds(lp, i, GLP_FR, 0.0, 0.0); |
| 51 | 51 |
return i; |
| 52 | 52 |
} |
| 53 | 53 |
|
| 54 | 54 |
int GlpkBase::_addRow() {
|
| 55 | 55 |
int i = glp_add_rows(lp, 1); |
| 56 | 56 |
glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0); |
| 57 | 57 |
return i; |
| 58 | 58 |
} |
| 59 | 59 |
|
| 60 | 60 |
void GlpkBase::_eraseCol(int i) {
|
| 61 | 61 |
int ca[2]; |
| 62 | 62 |
ca[1] = i; |
| 63 | 63 |
glp_del_cols(lp, 1, ca); |
| 64 | 64 |
} |
| 65 | 65 |
|
| 66 | 66 |
void GlpkBase::_eraseRow(int i) {
|
| 67 | 67 |
int ra[2]; |
| 68 | 68 |
ra[1] = i; |
| 69 | 69 |
glp_del_rows(lp, 1, ra); |
| 70 | 70 |
} |
| 71 | 71 |
|
| 72 | 72 |
void GlpkBase::_eraseColId(int i) {
|
| 73 | 73 |
cols.eraseIndex(i); |
| 74 | 74 |
cols.shiftIndices(i); |
| 75 | 75 |
} |
| 76 | 76 |
|
| 77 | 77 |
void GlpkBase::_eraseRowId(int i) {
|
| 78 | 78 |
rows.eraseIndex(i); |
| 79 | 79 |
rows.shiftIndices(i); |
| 80 | 80 |
} |
| 81 | 81 |
|
| 82 | 82 |
void GlpkBase::_getColName(int c, std::string& name) const {
|
| 83 | 83 |
const char *str = glp_get_col_name(lp, c); |
| 84 | 84 |
if (str) name = str; |
| 85 | 85 |
else name.clear(); |
| 86 | 86 |
} |
| 87 | 87 |
|
| 88 | 88 |
void GlpkBase::_setColName(int c, const std::string & name) {
|
| 89 | 89 |
glp_set_col_name(lp, c, const_cast<char*>(name.c_str())); |
| 90 | 90 |
|
| 91 | 91 |
} |
| 92 | 92 |
|
| 93 | 93 |
int GlpkBase::_colByName(const std::string& name) const {
|
| 94 | 94 |
int k = glp_find_col(lp, const_cast<char*>(name.c_str())); |
| 95 | 95 |
return k > 0 ? k : -1; |
| 96 | 96 |
} |
| 97 | 97 |
|
| 98 | 98 |
void GlpkBase::_getRowName(int r, std::string& name) const {
|
| 99 | 99 |
const char *str = glp_get_row_name(lp, r); |
| 100 | 100 |
if (str) name = str; |
| 101 | 101 |
else name.clear(); |
| 102 | 102 |
} |
| 103 | 103 |
|
| 104 | 104 |
void GlpkBase::_setRowName(int r, const std::string & name) {
|
| 105 | 105 |
glp_set_row_name(lp, r, const_cast<char*>(name.c_str())); |
| 106 | 106 |
|
| 107 | 107 |
} |
| 108 | 108 |
|
| 109 | 109 |
int GlpkBase::_rowByName(const std::string& name) const {
|
| 110 | 110 |
int k = glp_find_row(lp, const_cast<char*>(name.c_str())); |
| 111 | 111 |
return k > 0 ? k : -1; |
| 112 | 112 |
} |
| 113 | 113 |
|
| 114 | 114 |
void GlpkBase::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
|
| 115 | 115 |
std::vector<int> indexes; |
| 116 | 116 |
std::vector<Value> values; |
| 117 | 117 |
|
| 118 | 118 |
indexes.push_back(0); |
| 119 | 119 |
values.push_back(0); |
| 120 | 120 |
|
| 121 | 121 |
for(ExprIterator it = b; it != e; ++it) {
|
| 122 | 122 |
indexes.push_back(it->first); |
| 123 | 123 |
values.push_back(it->second); |
| 124 | 124 |
} |
| 125 | 125 |
|
| 126 | 126 |
glp_set_mat_row(lp, i, values.size() - 1, |
| 127 | 127 |
&indexes.front(), &values.front()); |
| 128 | 128 |
} |
| 129 | 129 |
|
| 130 | 130 |
void GlpkBase::_getRowCoeffs(int ix, InsertIterator b) const {
|
| 131 | 131 |
int length = glp_get_mat_row(lp, ix, 0, 0); |
| 132 | 132 |
|
| 133 | 133 |
std::vector<int> indexes(length + 1); |
| 134 | 134 |
std::vector<Value> values(length + 1); |
| 135 | 135 |
|
| 136 | 136 |
glp_get_mat_row(lp, ix, &indexes.front(), &values.front()); |
| 137 | 137 |
|
| 138 | 138 |
for (int i = 1; i <= length; ++i) {
|
| 139 | 139 |
*b = std::make_pair(indexes[i], values[i]); |
| 140 | 140 |
++b; |
| 141 | 141 |
} |
| 142 | 142 |
} |
| 143 | 143 |
|
| 144 | 144 |
void GlpkBase::_setColCoeffs(int ix, ExprIterator b, |
| 145 | 145 |
ExprIterator e) {
|
| 146 | 146 |
|
| 147 | 147 |
std::vector<int> indexes; |
| 148 | 148 |
std::vector<Value> values; |
| 149 | 149 |
|
| 150 | 150 |
indexes.push_back(0); |
| 151 | 151 |
values.push_back(0); |
| 152 | 152 |
|
| 153 | 153 |
for(ExprIterator it = b; it != e; ++it) {
|
| 154 | 154 |
indexes.push_back(it->first); |
| 155 | 155 |
values.push_back(it->second); |
| 156 | 156 |
} |
| 157 | 157 |
|
| 158 | 158 |
glp_set_mat_col(lp, ix, values.size() - 1, |
| 159 | 159 |
&indexes.front(), &values.front()); |
| 160 | 160 |
} |
| 161 | 161 |
|
| 162 | 162 |
void GlpkBase::_getColCoeffs(int ix, InsertIterator b) const {
|
| 163 | 163 |
int length = glp_get_mat_col(lp, ix, 0, 0); |
| 164 | 164 |
|
| 165 | 165 |
std::vector<int> indexes(length + 1); |
| 166 | 166 |
std::vector<Value> values(length + 1); |
| 167 | 167 |
|
| 168 | 168 |
glp_get_mat_col(lp, ix, &indexes.front(), &values.front()); |
| 169 | 169 |
|
| 170 | 170 |
for (int i = 1; i <= length; ++i) {
|
| 171 | 171 |
*b = std::make_pair(indexes[i], values[i]); |
| 172 | 172 |
++b; |
| 173 | 173 |
} |
| 174 | 174 |
} |
| 175 | 175 |
|
| 176 | 176 |
void GlpkBase::_setCoeff(int ix, int jx, Value value) {
|
| 177 | 177 |
|
| 178 | 178 |
if (glp_get_num_cols(lp) < glp_get_num_rows(lp)) {
|
| 179 | 179 |
|
| 180 | 180 |
int length = glp_get_mat_row(lp, ix, 0, 0); |
| 181 | 181 |
|
| 182 | 182 |
std::vector<int> indexes(length + 2); |
| 183 | 183 |
std::vector<Value> values(length + 2); |
| 184 | 184 |
|
| 185 | 185 |
glp_get_mat_row(lp, ix, &indexes.front(), &values.front()); |
| 186 | 186 |
|
| 187 | 187 |
//The following code does not suppose that the elements of the |
| 188 | 188 |
//array indexes are sorted |
| 189 | 189 |
bool found = false; |
| 190 | 190 |
for (int i = 1; i <= length; ++i) {
|
| 191 | 191 |
if (indexes[i] == jx) {
|
| 192 | 192 |
found = true; |
| 193 | 193 |
values[i] = value; |
| 194 | 194 |
break; |
| 195 | 195 |
} |
| 196 | 196 |
} |
| 197 | 197 |
if (!found) {
|
| 198 | 198 |
++length; |
| 199 | 199 |
indexes[length] = jx; |
| 200 | 200 |
values[length] = value; |
| 201 | 201 |
} |
| 202 | 202 |
|
| 203 | 203 |
glp_set_mat_row(lp, ix, length, &indexes.front(), &values.front()); |
| 204 | 204 |
|
| 205 | 205 |
} else {
|
| 206 | 206 |
|
| 207 | 207 |
int length = glp_get_mat_col(lp, jx, 0, 0); |
| 208 | 208 |
|
| 209 | 209 |
std::vector<int> indexes(length + 2); |
| 210 | 210 |
std::vector<Value> values(length + 2); |
| 211 | 211 |
|
| 212 | 212 |
glp_get_mat_col(lp, jx, &indexes.front(), &values.front()); |
| 213 | 213 |
|
| 214 | 214 |
//The following code does not suppose that the elements of the |
| 215 | 215 |
//array indexes are sorted |
| 216 | 216 |
bool found = false; |
| 217 | 217 |
for (int i = 1; i <= length; ++i) {
|
| 218 | 218 |
if (indexes[i] == ix) {
|
| 219 | 219 |
found = true; |
| 220 | 220 |
values[i] = value; |
| 221 | 221 |
break; |
| 222 | 222 |
} |
| 223 | 223 |
} |
| 224 | 224 |
if (!found) {
|
| 225 | 225 |
++length; |
| 226 | 226 |
indexes[length] = ix; |
| 227 | 227 |
values[length] = value; |
| 228 | 228 |
} |
| 229 | 229 |
|
| 230 | 230 |
glp_set_mat_col(lp, jx, length, &indexes.front(), &values.front()); |
| 231 | 231 |
} |
| 232 | 232 |
|
| 233 | 233 |
} |
| 234 | 234 |
|
| 235 | 235 |
GlpkBase::Value GlpkBase::_getCoeff(int ix, int jx) const {
|
| 236 | 236 |
|
| 237 | 237 |
int length = glp_get_mat_row(lp, ix, 0, 0); |
| 238 | 238 |
|
| 239 | 239 |
std::vector<int> indexes(length + 1); |
| 240 | 240 |
std::vector<Value> values(length + 1); |
| 241 | 241 |
|
| 242 | 242 |
glp_get_mat_row(lp, ix, &indexes.front(), &values.front()); |
| 243 | 243 |
|
| 244 | 244 |
for (int i = 1; i <= length; ++i) {
|
| 245 | 245 |
if (indexes[i] == jx) {
|
| 246 | 246 |
return values[i]; |
| 247 | 247 |
} |
| 248 | 248 |
} |
| 249 | 249 |
|
| 250 | 250 |
return 0; |
| 251 | 251 |
} |
| 252 | 252 |
|
| 253 | 253 |
void GlpkBase::_setColLowerBound(int i, Value lo) {
|
| 254 | 254 |
LEMON_ASSERT(lo != INF, "Invalid bound"); |
| 255 | 255 |
|
| 256 | 256 |
int b = glp_get_col_type(lp, i); |
| 257 | 257 |
double up = glp_get_col_ub(lp, i); |
| 258 | 258 |
if (lo == -INF) {
|
| 259 | 259 |
switch (b) {
|
| 260 | 260 |
case GLP_FR: |
| 261 | 261 |
case GLP_LO: |
| 262 | 262 |
glp_set_col_bnds(lp, i, GLP_FR, lo, up); |
| 263 | 263 |
break; |
| 264 | 264 |
case GLP_UP: |
| 265 | 265 |
break; |
| 266 | 266 |
case GLP_DB: |
| 267 | 267 |
case GLP_FX: |
| 268 | 268 |
glp_set_col_bnds(lp, i, GLP_UP, lo, up); |
| 269 | 269 |
break; |
| 270 | 270 |
default: |
| 271 | 271 |
break; |
| 272 | 272 |
} |
| 273 | 273 |
} else {
|
| 274 | 274 |
switch (b) {
|
| 275 | 275 |
case GLP_FR: |
| 276 | 276 |
case GLP_LO: |
| 277 | 277 |
glp_set_col_bnds(lp, i, GLP_LO, lo, up); |
| 278 | 278 |
break; |
| 279 | 279 |
case GLP_UP: |
| 280 | 280 |
case GLP_DB: |
| 281 | 281 |
case GLP_FX: |
| 282 | 282 |
if (lo == up) |
| 283 | 283 |
glp_set_col_bnds(lp, i, GLP_FX, lo, up); |
| 284 | 284 |
else |
| 285 | 285 |
glp_set_col_bnds(lp, i, GLP_DB, lo, up); |
| 286 | 286 |
break; |
| 287 | 287 |
default: |
| 288 | 288 |
break; |
| 289 | 289 |
} |
| 290 | 290 |
} |
| 291 | 291 |
} |
| 292 | 292 |
|
| 293 | 293 |
GlpkBase::Value GlpkBase::_getColLowerBound(int i) const {
|
| 294 | 294 |
int b = glp_get_col_type(lp, i); |
| 295 | 295 |
switch (b) {
|
| 296 | 296 |
case GLP_LO: |
| 297 | 297 |
case GLP_DB: |
| 298 | 298 |
case GLP_FX: |
| 299 | 299 |
return glp_get_col_lb(lp, i); |
| 300 | 300 |
default: |
| 301 | 301 |
return -INF; |
| 302 | 302 |
} |
| 303 | 303 |
} |
| 304 | 304 |
|
| 305 | 305 |
void GlpkBase::_setColUpperBound(int i, Value up) {
|
| 306 | 306 |
LEMON_ASSERT(up != -INF, "Invalid bound"); |
| 307 | 307 |
|
| 308 | 308 |
int b = glp_get_col_type(lp, i); |
| 309 | 309 |
double lo = glp_get_col_lb(lp, i); |
| 310 | 310 |
if (up == INF) {
|
| 311 | 311 |
switch (b) {
|
| 312 | 312 |
case GLP_FR: |
| 313 | 313 |
case GLP_LO: |
| 314 | 314 |
break; |
| 315 | 315 |
case GLP_UP: |
| 316 | 316 |
glp_set_col_bnds(lp, i, GLP_FR, lo, up); |
| 317 | 317 |
break; |
| 318 | 318 |
case GLP_DB: |
| 319 | 319 |
case GLP_FX: |
| 320 | 320 |
glp_set_col_bnds(lp, i, GLP_LO, lo, up); |
| 321 | 321 |
break; |
| 322 | 322 |
default: |
| 323 | 323 |
break; |
| 324 | 324 |
} |
| 325 | 325 |
} else {
|
| 326 | 326 |
switch (b) {
|
| 327 | 327 |
case GLP_FR: |
| 328 | 328 |
glp_set_col_bnds(lp, i, GLP_UP, lo, up); |
| 329 | 329 |
break; |
| 330 | 330 |
case GLP_UP: |
| 331 | 331 |
glp_set_col_bnds(lp, i, GLP_UP, lo, up); |
| 332 | 332 |
break; |
| 333 | 333 |
case GLP_LO: |
| 334 | 334 |
case GLP_DB: |
| 335 | 335 |
case GLP_FX: |
| 336 | 336 |
if (lo == up) |
| 337 | 337 |
glp_set_col_bnds(lp, i, GLP_FX, lo, up); |
| 338 | 338 |
else |
| 339 | 339 |
glp_set_col_bnds(lp, i, GLP_DB, lo, up); |
| 340 | 340 |
break; |
| 341 | 341 |
default: |
| 342 | 342 |
break; |
| 343 | 343 |
} |
| 344 | 344 |
} |
| 345 | 345 |
|
| 346 | 346 |
} |
| 347 | 347 |
|
| 348 | 348 |
GlpkBase::Value GlpkBase::_getColUpperBound(int i) const {
|
| 349 | 349 |
int b = glp_get_col_type(lp, i); |
| 350 | 350 |
switch (b) {
|
| 351 | 351 |
case GLP_UP: |
| 352 | 352 |
case GLP_DB: |
| 353 | 353 |
case GLP_FX: |
| 354 | 354 |
return glp_get_col_ub(lp, i); |
| 355 | 355 |
default: |
| 356 | 356 |
return INF; |
| 357 | 357 |
} |
| 358 | 358 |
} |
| 359 | 359 |
|
| 360 | 360 |
void GlpkBase::_setRowLowerBound(int i, Value lo) {
|
| 361 | 361 |
LEMON_ASSERT(lo != INF, "Invalid bound"); |
| 362 | 362 |
|
| 363 | 363 |
int b = glp_get_row_type(lp, i); |
| 364 | 364 |
double up = glp_get_row_ub(lp, i); |
| 365 | 365 |
if (lo == -INF) {
|
| 366 | 366 |
switch (b) {
|
| 367 | 367 |
case GLP_FR: |
| 368 | 368 |
case GLP_LO: |
| 369 | 369 |
glp_set_row_bnds(lp, i, GLP_FR, lo, up); |
| 370 | 370 |
break; |
| 371 | 371 |
case GLP_UP: |
| 372 | 372 |
break; |
| 373 | 373 |
case GLP_DB: |
| 374 | 374 |
case GLP_FX: |
| 375 | 375 |
glp_set_row_bnds(lp, i, GLP_UP, lo, up); |
| 376 | 376 |
break; |
| 377 | 377 |
default: |
| 378 | 378 |
break; |
| 379 | 379 |
} |
| 380 | 380 |
} else {
|
| 381 | 381 |
switch (b) {
|
| 382 | 382 |
case GLP_FR: |
| 383 | 383 |
case GLP_LO: |
| 384 | 384 |
glp_set_row_bnds(lp, i, GLP_LO, lo, up); |
| 385 | 385 |
break; |
| 386 | 386 |
case GLP_UP: |
| 387 | 387 |
case GLP_DB: |
| 388 | 388 |
case GLP_FX: |
| 389 | 389 |
if (lo == up) |
| 390 | 390 |
glp_set_row_bnds(lp, i, GLP_FX, lo, up); |
| 391 | 391 |
else |
| 392 | 392 |
glp_set_row_bnds(lp, i, GLP_DB, lo, up); |
| 393 | 393 |
break; |
| 394 | 394 |
default: |
| 395 | 395 |
break; |
| 396 | 396 |
} |
| 397 | 397 |
} |
| 398 | 398 |
|
| 399 | 399 |
} |
| 400 | 400 |
|
| 401 | 401 |
GlpkBase::Value GlpkBase::_getRowLowerBound(int i) const {
|
| 402 | 402 |
int b = glp_get_row_type(lp, i); |
| 403 | 403 |
switch (b) {
|
| 404 | 404 |
case GLP_LO: |
| 405 | 405 |
case GLP_DB: |
| 406 | 406 |
case GLP_FX: |
| 407 | 407 |
return glp_get_row_lb(lp, i); |
| 408 | 408 |
default: |
| 409 | 409 |
return -INF; |
| 410 | 410 |
} |
| 411 | 411 |
} |
| 412 | 412 |
|
| 413 | 413 |
void GlpkBase::_setRowUpperBound(int i, Value up) {
|
| 414 | 414 |
LEMON_ASSERT(up != -INF, "Invalid bound"); |
| 415 | 415 |
|
| 416 | 416 |
int b = glp_get_row_type(lp, i); |
| 417 | 417 |
double lo = glp_get_row_lb(lp, i); |
| 418 | 418 |
if (up == INF) {
|
| 419 | 419 |
switch (b) {
|
| 420 | 420 |
case GLP_FR: |
| 421 | 421 |
case GLP_LO: |
| 422 | 422 |
break; |
| 423 | 423 |
case GLP_UP: |
| 424 | 424 |
glp_set_row_bnds(lp, i, GLP_FR, lo, up); |
| 425 | 425 |
break; |
| 426 | 426 |
case GLP_DB: |
| 427 | 427 |
case GLP_FX: |
| 428 | 428 |
glp_set_row_bnds(lp, i, GLP_LO, lo, up); |
| 429 | 429 |
break; |
| 430 | 430 |
default: |
| 431 | 431 |
break; |
| 432 | 432 |
} |
| 433 | 433 |
} else {
|
| 434 | 434 |
switch (b) {
|
| 435 | 435 |
case GLP_FR: |
| 436 | 436 |
glp_set_row_bnds(lp, i, GLP_UP, lo, up); |
| 437 | 437 |
break; |
| 438 | 438 |
case GLP_UP: |
| 439 | 439 |
glp_set_row_bnds(lp, i, GLP_UP, lo, up); |
| 440 | 440 |
break; |
| 441 | 441 |
case GLP_LO: |
| 442 | 442 |
case GLP_DB: |
| 443 | 443 |
case GLP_FX: |
| 444 | 444 |
if (lo == up) |
| 445 | 445 |
glp_set_row_bnds(lp, i, GLP_FX, lo, up); |
| 446 | 446 |
else |
| 447 | 447 |
glp_set_row_bnds(lp, i, GLP_DB, lo, up); |
| 448 | 448 |
break; |
| 449 | 449 |
default: |
| 450 | 450 |
break; |
| 451 | 451 |
} |
| 452 | 452 |
} |
| 453 | 453 |
} |
| 454 | 454 |
|
| 455 | 455 |
GlpkBase::Value GlpkBase::_getRowUpperBound(int i) const {
|
| 456 | 456 |
int b = glp_get_row_type(lp, i); |
| 457 | 457 |
switch (b) {
|
| 458 | 458 |
case GLP_UP: |
| 459 | 459 |
case GLP_DB: |
| 460 | 460 |
case GLP_FX: |
| 461 | 461 |
return glp_get_row_ub(lp, i); |
| 462 | 462 |
default: |
| 463 | 463 |
return INF; |
| 464 | 464 |
} |
| 465 | 465 |
} |
| 466 | 466 |
|
| 467 | 467 |
void GlpkBase::_setObjCoeffs(ExprIterator b, ExprIterator e) {
|
| 468 | 468 |
for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
|
| 469 | 469 |
glp_set_obj_coef(lp, i, 0.0); |
| 470 | 470 |
} |
| 471 | 471 |
for (ExprIterator it = b; it != e; ++it) {
|
| 472 | 472 |
glp_set_obj_coef(lp, it->first, it->second); |
| 473 | 473 |
} |
| 474 | 474 |
} |
| 475 | 475 |
|
| 476 | 476 |
void GlpkBase::_getObjCoeffs(InsertIterator b) const {
|
| 477 | 477 |
for (int i = 1; i <= glp_get_num_cols(lp); ++i) {
|
| 478 | 478 |
Value val = glp_get_obj_coef(lp, i); |
| 479 | 479 |
if (val != 0.0) {
|
| 480 | 480 |
*b = std::make_pair(i, val); |
| 481 | 481 |
++b; |
| 482 | 482 |
} |
| 483 | 483 |
} |
| 484 | 484 |
} |
| 485 | 485 |
|
| 486 | 486 |
void GlpkBase::_setObjCoeff(int i, Value obj_coef) {
|
| 487 | 487 |
//i = 0 means the constant term (shift) |
| 488 | 488 |
glp_set_obj_coef(lp, i, obj_coef); |
| 489 | 489 |
} |
| 490 | 490 |
|
| 491 | 491 |
GlpkBase::Value GlpkBase::_getObjCoeff(int i) const {
|
| 492 | 492 |
//i = 0 means the constant term (shift) |
| 493 | 493 |
return glp_get_obj_coef(lp, i); |
| 494 | 494 |
} |
| 495 | 495 |
|
| 496 | 496 |
void GlpkBase::_setSense(GlpkBase::Sense sense) {
|
| 497 | 497 |
switch (sense) {
|
| 498 | 498 |
case MIN: |
| 499 | 499 |
glp_set_obj_dir(lp, GLP_MIN); |
| 500 | 500 |
break; |
| 501 | 501 |
case MAX: |
| 502 | 502 |
glp_set_obj_dir(lp, GLP_MAX); |
| 503 | 503 |
break; |
| 504 | 504 |
} |
| 505 | 505 |
} |
| 506 | 506 |
|
| 507 | 507 |
GlpkBase::Sense GlpkBase::_getSense() const {
|
| 508 | 508 |
switch(glp_get_obj_dir(lp)) {
|
| 509 | 509 |
case GLP_MIN: |
| 510 | 510 |
return MIN; |
| 511 | 511 |
case GLP_MAX: |
| 512 | 512 |
return MAX; |
| 513 | 513 |
default: |
| 514 | 514 |
LEMON_ASSERT(false, "Wrong sense"); |
| 515 | 515 |
return GlpkBase::Sense(); |
| 516 | 516 |
} |
| 517 | 517 |
} |
| 518 | 518 |
|
| 519 | 519 |
void GlpkBase::_clear() {
|
| 520 | 520 |
glp_erase_prob(lp); |
| 521 | 521 |
rows.clear(); |
| 522 | 522 |
cols.clear(); |
| 523 | 523 |
} |
| 524 | 524 |
|
| 525 | 525 |
void GlpkBase::freeEnv() {
|
| 526 | 526 |
glp_free_env(); |
| 527 | 527 |
} |
| 528 | 528 |
|
| 529 | 529 |
GlpkBase::FreeEnvHelper GlpkBase::freeEnvHelper; |
| 530 | 530 |
|
| 531 | 531 |
// GlpkLp members |
| 532 | 532 |
|
| 533 | 533 |
GlpkLp::GlpkLp() |
| 534 |
: LpBase(), |
|
| 534 |
: LpBase(), LpSolver(), GlpkBase() {
|
|
| 535 | 535 |
messageLevel(MESSAGE_NO_OUTPUT); |
| 536 | 536 |
} |
| 537 | 537 |
|
| 538 | 538 |
GlpkLp::GlpkLp(const GlpkLp& other) |
| 539 |
: LpBase(other), |
|
| 539 |
: LpBase(other), LpSolver(other), GlpkBase(other) {
|
|
| 540 | 540 |
messageLevel(MESSAGE_NO_OUTPUT); |
| 541 | 541 |
} |
| 542 | 542 |
|
| 543 | 543 |
GlpkLp* GlpkLp::newSolver() const { return new GlpkLp; }
|
| 544 | 544 |
GlpkLp* GlpkLp::cloneSolver() const { return new GlpkLp(*this); }
|
| 545 | 545 |
|
| 546 | 546 |
const char* GlpkLp::_solverName() const { return "GlpkLp"; }
|
| 547 | 547 |
|
| 548 | 548 |
void GlpkLp::_clear_temporals() {
|
| 549 | 549 |
_primal_ray.clear(); |
| 550 | 550 |
_dual_ray.clear(); |
| 551 | 551 |
} |
| 552 | 552 |
|
| 553 | 553 |
GlpkLp::SolveExitStatus GlpkLp::_solve() {
|
| 554 | 554 |
return solvePrimal(); |
| 555 | 555 |
} |
| 556 | 556 |
|
| 557 | 557 |
GlpkLp::SolveExitStatus GlpkLp::solvePrimal() {
|
| 558 | 558 |
_clear_temporals(); |
| 559 | 559 |
|
| 560 | 560 |
glp_smcp smcp; |
| 561 | 561 |
glp_init_smcp(&smcp); |
| 562 | 562 |
|
| 563 | 563 |
switch (_message_level) {
|
| 564 | 564 |
case MESSAGE_NO_OUTPUT: |
| 565 | 565 |
smcp.msg_lev = GLP_MSG_OFF; |
| 566 | 566 |
break; |
| 567 | 567 |
case MESSAGE_ERROR_MESSAGE: |
| 568 | 568 |
smcp.msg_lev = GLP_MSG_ERR; |
| 569 | 569 |
break; |
| 570 | 570 |
case MESSAGE_NORMAL_OUTPUT: |
| 571 | 571 |
smcp.msg_lev = GLP_MSG_ON; |
| 572 | 572 |
break; |
| 573 | 573 |
case MESSAGE_FULL_OUTPUT: |
| 574 | 574 |
smcp.msg_lev = GLP_MSG_ALL; |
| 575 | 575 |
break; |
| 576 | 576 |
} |
| 577 | 577 |
|
| 578 | 578 |
if (glp_simplex(lp, &smcp) != 0) return UNSOLVED; |
| 579 | 579 |
return SOLVED; |
| 580 | 580 |
} |
| 581 | 581 |
|
| 582 | 582 |
GlpkLp::SolveExitStatus GlpkLp::solveDual() {
|
| 583 | 583 |
_clear_temporals(); |
| 584 | 584 |
|
| 585 | 585 |
glp_smcp smcp; |
| 586 | 586 |
glp_init_smcp(&smcp); |
| 587 | 587 |
|
| 588 | 588 |
switch (_message_level) {
|
| 589 | 589 |
case MESSAGE_NO_OUTPUT: |
| 590 | 590 |
smcp.msg_lev = GLP_MSG_OFF; |
| 591 | 591 |
break; |
| 592 | 592 |
case MESSAGE_ERROR_MESSAGE: |
| 593 | 593 |
smcp.msg_lev = GLP_MSG_ERR; |
| 594 | 594 |
break; |
| 595 | 595 |
case MESSAGE_NORMAL_OUTPUT: |
| 596 | 596 |
smcp.msg_lev = GLP_MSG_ON; |
| 597 | 597 |
break; |
| 598 | 598 |
case MESSAGE_FULL_OUTPUT: |
| 599 | 599 |
smcp.msg_lev = GLP_MSG_ALL; |
| 600 | 600 |
break; |
| 601 | 601 |
} |
| 602 | 602 |
smcp.meth = GLP_DUAL; |
| 603 | 603 |
|
| 604 | 604 |
if (glp_simplex(lp, &smcp) != 0) return UNSOLVED; |
| 605 | 605 |
return SOLVED; |
| 606 | 606 |
} |
| 607 | 607 |
|
| 608 | 608 |
GlpkLp::Value GlpkLp::_getPrimal(int i) const {
|
| 609 | 609 |
return glp_get_col_prim(lp, i); |
| 610 | 610 |
} |
| 611 | 611 |
|
| 612 | 612 |
GlpkLp::Value GlpkLp::_getDual(int i) const {
|
| 613 | 613 |
return glp_get_row_dual(lp, i); |
| 614 | 614 |
} |
| 615 | 615 |
|
| 616 | 616 |
GlpkLp::Value GlpkLp::_getPrimalValue() const {
|
| 617 | 617 |
return glp_get_obj_val(lp); |
| 618 | 618 |
} |
| 619 | 619 |
|
| 620 | 620 |
GlpkLp::VarStatus GlpkLp::_getColStatus(int i) const {
|
| 621 | 621 |
switch (glp_get_col_stat(lp, i)) {
|
| 622 | 622 |
case GLP_BS: |
| 623 | 623 |
return BASIC; |
| 624 | 624 |
case GLP_UP: |
| 625 | 625 |
return UPPER; |
| 626 | 626 |
case GLP_LO: |
| 627 | 627 |
return LOWER; |
| 628 | 628 |
case GLP_NF: |
| 629 | 629 |
return FREE; |
| 630 | 630 |
case GLP_NS: |
| 631 | 631 |
return FIXED; |
| 632 | 632 |
default: |
| 633 | 633 |
LEMON_ASSERT(false, "Wrong column status"); |
| 634 | 634 |
return GlpkLp::VarStatus(); |
| 635 | 635 |
} |
| 636 | 636 |
} |
| 637 | 637 |
|
| 638 | 638 |
GlpkLp::VarStatus GlpkLp::_getRowStatus(int i) const {
|
| 639 | 639 |
switch (glp_get_row_stat(lp, i)) {
|
| 640 | 640 |
case GLP_BS: |
| 641 | 641 |
return BASIC; |
| 642 | 642 |
case GLP_UP: |
| 643 | 643 |
return UPPER; |
| 644 | 644 |
case GLP_LO: |
| 645 | 645 |
return LOWER; |
| 646 | 646 |
case GLP_NF: |
| 647 | 647 |
return FREE; |
| 648 | 648 |
case GLP_NS: |
| 649 | 649 |
return FIXED; |
| 650 | 650 |
default: |
| 651 | 651 |
LEMON_ASSERT(false, "Wrong row status"); |
| 652 | 652 |
return GlpkLp::VarStatus(); |
| 653 | 653 |
} |
| 654 | 654 |
} |
| 655 | 655 |
|
| 656 | 656 |
GlpkLp::Value GlpkLp::_getPrimalRay(int i) const {
|
| 657 | 657 |
if (_primal_ray.empty()) {
|
| 658 | 658 |
int row_num = glp_get_num_rows(lp); |
| 659 | 659 |
int col_num = glp_get_num_cols(lp); |
| 660 | 660 |
|
| 661 | 661 |
_primal_ray.resize(col_num + 1, 0.0); |
| 662 | 662 |
|
| 663 | 663 |
int index = glp_get_unbnd_ray(lp); |
| 664 | 664 |
if (index != 0) {
|
| 665 | 665 |
// The primal ray is found in primal simplex second phase |
| 666 | 666 |
LEMON_ASSERT((index <= row_num ? glp_get_row_stat(lp, index) : |
| 667 | 667 |
glp_get_col_stat(lp, index - row_num)) != GLP_BS, |
| 668 | 668 |
"Wrong primal ray"); |
| 669 | 669 |
|
| 670 | 670 |
bool negate = glp_get_obj_dir(lp) == GLP_MAX; |
| 671 | 671 |
|
| 672 | 672 |
if (index > row_num) {
|
| 673 | 673 |
_primal_ray[index - row_num] = 1.0; |
| 674 | 674 |
if (glp_get_col_dual(lp, index - row_num) > 0) {
|
| 675 | 675 |
negate = !negate; |
| 676 | 676 |
} |
| 677 | 677 |
} else {
|
| 678 | 678 |
if (glp_get_row_dual(lp, index) > 0) {
|
| 679 | 679 |
negate = !negate; |
| 680 | 680 |
} |
| 681 | 681 |
} |
| 682 | 682 |
|
| 683 | 683 |
std::vector<int> ray_indexes(row_num + 1); |
| 684 | 684 |
std::vector<Value> ray_values(row_num + 1); |
| 685 | 685 |
int ray_length = glp_eval_tab_col(lp, index, &ray_indexes.front(), |
| 686 | 686 |
&ray_values.front()); |
| 687 | 687 |
|
| 688 | 688 |
for (int i = 1; i <= ray_length; ++i) {
|
| 689 | 689 |
if (ray_indexes[i] > row_num) {
|
| 690 | 690 |
_primal_ray[ray_indexes[i] - row_num] = ray_values[i]; |
| 691 | 691 |
} |
| 692 | 692 |
} |
| 693 | 693 |
|
| 694 | 694 |
if (negate) {
|
| 695 | 695 |
for (int i = 1; i <= col_num; ++i) {
|
| 696 | 696 |
_primal_ray[i] = - _primal_ray[i]; |
| 697 | 697 |
} |
| 698 | 698 |
} |
| 699 | 699 |
} else {
|
| 700 | 700 |
for (int i = 1; i <= col_num; ++i) {
|
| 701 | 701 |
_primal_ray[i] = glp_get_col_prim(lp, i); |
| 702 | 702 |
} |
| 703 | 703 |
} |
| 704 | 704 |
} |
| 705 | 705 |
return _primal_ray[i]; |
| 706 | 706 |
} |
| 707 | 707 |
|
| 708 | 708 |
GlpkLp::Value GlpkLp::_getDualRay(int i) const {
|
| 709 | 709 |
if (_dual_ray.empty()) {
|
| 710 | 710 |
int row_num = glp_get_num_rows(lp); |
| 711 | 711 |
|
| 712 | 712 |
_dual_ray.resize(row_num + 1, 0.0); |
| 713 | 713 |
|
| 714 | 714 |
int index = glp_get_unbnd_ray(lp); |
| 715 | 715 |
if (index != 0) {
|
| 716 | 716 |
// The dual ray is found in dual simplex second phase |
| 717 | 717 |
LEMON_ASSERT((index <= row_num ? glp_get_row_stat(lp, index) : |
| 718 | 718 |
glp_get_col_stat(lp, index - row_num)) == GLP_BS, |
| 719 | 719 |
|
| 720 | 720 |
"Wrong dual ray"); |
| 721 | 721 |
|
| 722 | 722 |
int idx; |
| 723 | 723 |
bool negate = false; |
| 724 | 724 |
|
| 725 | 725 |
if (index > row_num) {
|
| 726 | 726 |
idx = glp_get_col_bind(lp, index - row_num); |
| 727 | 727 |
if (glp_get_col_prim(lp, index - row_num) > |
| 728 | 728 |
glp_get_col_ub(lp, index - row_num)) {
|
| 729 | 729 |
negate = true; |
| 730 | 730 |
} |
| 731 | 731 |
} else {
|
| 732 | 732 |
idx = glp_get_row_bind(lp, index); |
| 733 | 733 |
if (glp_get_row_prim(lp, index) > glp_get_row_ub(lp, index)) {
|
| 734 | 734 |
negate = true; |
| 735 | 735 |
} |
| 736 | 736 |
} |
| 737 | 737 |
|
| 738 | 738 |
_dual_ray[idx] = negate ? - 1.0 : 1.0; |
| 739 | 739 |
|
| 740 | 740 |
glp_btran(lp, &_dual_ray.front()); |
| 741 | 741 |
} else {
|
| 742 | 742 |
double eps = 1e-7; |
| 743 | 743 |
// The dual ray is found in primal simplex first phase |
| 744 | 744 |
// We assume that the glpk minimizes the slack to get feasible solution |
| 745 | 745 |
for (int i = 1; i <= row_num; ++i) {
|
| 746 | 746 |
int index = glp_get_bhead(lp, i); |
| 747 | 747 |
if (index <= row_num) {
|
| 748 | 748 |
double res = glp_get_row_prim(lp, index); |
| 749 | 749 |
if (res > glp_get_row_ub(lp, index) + eps) {
|
| 750 | 750 |
_dual_ray[i] = -1; |
| 751 | 751 |
} else if (res < glp_get_row_lb(lp, index) - eps) {
|
| 752 | 752 |
_dual_ray[i] = 1; |
| 753 | 753 |
} else {
|
| 754 | 754 |
_dual_ray[i] = 0; |
| 755 | 755 |
} |
| 756 | 756 |
_dual_ray[i] *= glp_get_rii(lp, index); |
| 757 | 757 |
} else {
|
| 758 | 758 |
double res = glp_get_col_prim(lp, index - row_num); |
| 759 | 759 |
if (res > glp_get_col_ub(lp, index - row_num) + eps) {
|
| 760 | 760 |
_dual_ray[i] = -1; |
| 761 | 761 |
} else if (res < glp_get_col_lb(lp, index - row_num) - eps) {
|
| 762 | 762 |
_dual_ray[i] = 1; |
| 763 | 763 |
} else {
|
| 764 | 764 |
_dual_ray[i] = 0; |
| 765 | 765 |
} |
| 766 | 766 |
_dual_ray[i] /= glp_get_sjj(lp, index - row_num); |
| 767 | 767 |
} |
| 768 | 768 |
} |
| 769 | 769 |
|
| 770 | 770 |
glp_btran(lp, &_dual_ray.front()); |
| 771 | 771 |
|
| 772 | 772 |
for (int i = 1; i <= row_num; ++i) {
|
| 773 | 773 |
_dual_ray[i] /= glp_get_rii(lp, i); |
| 774 | 774 |
} |
| 775 | 775 |
} |
| 776 | 776 |
} |
| 777 | 777 |
return _dual_ray[i]; |
| 778 | 778 |
} |
| 779 | 779 |
|
| 780 | 780 |
GlpkLp::ProblemType GlpkLp::_getPrimalType() const {
|
| 781 | 781 |
if (glp_get_status(lp) == GLP_OPT) |
| 782 | 782 |
return OPTIMAL; |
| 783 | 783 |
switch (glp_get_prim_stat(lp)) {
|
| 784 | 784 |
case GLP_UNDEF: |
| 785 | 785 |
return UNDEFINED; |
| 786 | 786 |
case GLP_FEAS: |
| 787 | 787 |
case GLP_INFEAS: |
| 788 | 788 |
if (glp_get_dual_stat(lp) == GLP_NOFEAS) {
|
| 789 | 789 |
return UNBOUNDED; |
| 790 | 790 |
} else {
|
| 791 | 791 |
return UNDEFINED; |
| 792 | 792 |
} |
| 793 | 793 |
case GLP_NOFEAS: |
| 794 | 794 |
return INFEASIBLE; |
| 795 | 795 |
default: |
| 796 | 796 |
LEMON_ASSERT(false, "Wrong primal type"); |
| 797 | 797 |
return GlpkLp::ProblemType(); |
| 798 | 798 |
} |
| 799 | 799 |
} |
| 800 | 800 |
|
| 801 | 801 |
GlpkLp::ProblemType GlpkLp::_getDualType() const {
|
| 802 | 802 |
if (glp_get_status(lp) == GLP_OPT) |
| 803 | 803 |
return OPTIMAL; |
| 804 | 804 |
switch (glp_get_dual_stat(lp)) {
|
| 805 | 805 |
case GLP_UNDEF: |
| 806 | 806 |
return UNDEFINED; |
| 807 | 807 |
case GLP_FEAS: |
| 808 | 808 |
case GLP_INFEAS: |
| 809 | 809 |
if (glp_get_prim_stat(lp) == GLP_NOFEAS) {
|
| 810 | 810 |
return UNBOUNDED; |
| 811 | 811 |
} else {
|
| 812 | 812 |
return UNDEFINED; |
| 813 | 813 |
} |
| 814 | 814 |
case GLP_NOFEAS: |
| 815 | 815 |
return INFEASIBLE; |
| 816 | 816 |
default: |
| 817 | 817 |
LEMON_ASSERT(false, "Wrong primal type"); |
| 818 | 818 |
return GlpkLp::ProblemType(); |
| 819 | 819 |
} |
| 820 | 820 |
} |
| 821 | 821 |
|
| 822 | 822 |
void GlpkLp::presolver(bool b) {
|
| 823 | 823 |
lpx_set_int_parm(lp, LPX_K_PRESOL, b ? 1 : 0); |
| 824 | 824 |
} |
| 825 | 825 |
|
| 826 | 826 |
void GlpkLp::messageLevel(MessageLevel m) {
|
| 827 | 827 |
_message_level = m; |
| 828 | 828 |
} |
| 829 | 829 |
|
| 830 | 830 |
// GlpkMip members |
| 831 | 831 |
|
| 832 | 832 |
GlpkMip::GlpkMip() |
| 833 |
: LpBase(), |
|
| 833 |
: LpBase(), MipSolver(), GlpkBase() {
|
|
| 834 | 834 |
messageLevel(MESSAGE_NO_OUTPUT); |
| 835 | 835 |
} |
| 836 | 836 |
|
| 837 | 837 |
GlpkMip::GlpkMip(const GlpkMip& other) |
| 838 |
: LpBase(), |
|
| 838 |
: LpBase(), MipSolver(), GlpkBase(other) {
|
|
| 839 | 839 |
messageLevel(MESSAGE_NO_OUTPUT); |
| 840 | 840 |
} |
| 841 | 841 |
|
| 842 | 842 |
void GlpkMip::_setColType(int i, GlpkMip::ColTypes col_type) {
|
| 843 | 843 |
switch (col_type) {
|
| 844 | 844 |
case INTEGER: |
| 845 | 845 |
glp_set_col_kind(lp, i, GLP_IV); |
| 846 | 846 |
break; |
| 847 | 847 |
case REAL: |
| 848 | 848 |
glp_set_col_kind(lp, i, GLP_CV); |
| 849 | 849 |
break; |
| 850 | 850 |
} |
| 851 | 851 |
} |
| 852 | 852 |
|
| 853 | 853 |
GlpkMip::ColTypes GlpkMip::_getColType(int i) const {
|
| 854 | 854 |
switch (glp_get_col_kind(lp, i)) {
|
| 855 | 855 |
case GLP_IV: |
| 856 | 856 |
case GLP_BV: |
| 857 | 857 |
return INTEGER; |
| 858 | 858 |
default: |
| 859 | 859 |
return REAL; |
| 860 | 860 |
} |
| 861 | 861 |
|
| 862 | 862 |
} |
| 863 | 863 |
|
| 864 | 864 |
GlpkMip::SolveExitStatus GlpkMip::_solve() {
|
| 865 | 865 |
glp_smcp smcp; |
| 866 | 866 |
glp_init_smcp(&smcp); |
| 867 | 867 |
|
| 868 | 868 |
switch (_message_level) {
|
| 869 | 869 |
case MESSAGE_NO_OUTPUT: |
| 870 | 870 |
smcp.msg_lev = GLP_MSG_OFF; |
| 871 | 871 |
break; |
| 872 | 872 |
case MESSAGE_ERROR_MESSAGE: |
| 873 | 873 |
smcp.msg_lev = GLP_MSG_ERR; |
| 874 | 874 |
break; |
| 875 | 875 |
case MESSAGE_NORMAL_OUTPUT: |
| 876 | 876 |
smcp.msg_lev = GLP_MSG_ON; |
| 877 | 877 |
break; |
| 878 | 878 |
case MESSAGE_FULL_OUTPUT: |
| 879 | 879 |
smcp.msg_lev = GLP_MSG_ALL; |
| 880 | 880 |
break; |
| 881 | 881 |
} |
| 882 | 882 |
smcp.meth = GLP_DUAL; |
| 883 | 883 |
|
| 884 | 884 |
if (glp_simplex(lp, &smcp) != 0) return UNSOLVED; |
| 885 | 885 |
if (glp_get_status(lp) != GLP_OPT) return SOLVED; |
| 886 | 886 |
|
| 887 | 887 |
glp_iocp iocp; |
| 888 | 888 |
glp_init_iocp(&iocp); |
| 889 | 889 |
|
| 890 | 890 |
switch (_message_level) {
|
| 891 | 891 |
case MESSAGE_NO_OUTPUT: |
| 892 | 892 |
iocp.msg_lev = GLP_MSG_OFF; |
| 893 | 893 |
break; |
| 894 | 894 |
case MESSAGE_ERROR_MESSAGE: |
| 895 | 895 |
iocp.msg_lev = GLP_MSG_ERR; |
| 896 | 896 |
break; |
| 897 | 897 |
case MESSAGE_NORMAL_OUTPUT: |
| 898 | 898 |
iocp.msg_lev = GLP_MSG_ON; |
| 899 | 899 |
break; |
| 900 | 900 |
case MESSAGE_FULL_OUTPUT: |
| 901 | 901 |
iocp.msg_lev = GLP_MSG_ALL; |
| 902 | 902 |
break; |
| 903 | 903 |
} |
| 904 | 904 |
|
| 905 | 905 |
if (glp_intopt(lp, &iocp) != 0) return UNSOLVED; |
| 906 | 906 |
return SOLVED; |
| 907 | 907 |
} |
| 908 | 908 |
|
| 909 | 909 |
|
| 910 | 910 |
GlpkMip::ProblemType GlpkMip::_getType() const {
|
| 911 | 911 |
switch (glp_get_status(lp)) {
|
| 912 | 912 |
case GLP_OPT: |
| 913 | 913 |
switch (glp_mip_status(lp)) {
|
| 914 | 914 |
case GLP_UNDEF: |
| 915 | 915 |
return UNDEFINED; |
| 916 | 916 |
case GLP_NOFEAS: |
| 917 | 917 |
return INFEASIBLE; |
| 918 | 918 |
case GLP_FEAS: |
| 919 | 919 |
return FEASIBLE; |
| 920 | 920 |
case GLP_OPT: |
| 921 | 921 |
return OPTIMAL; |
| 922 | 922 |
default: |
| 923 | 923 |
LEMON_ASSERT(false, "Wrong problem type."); |
| 924 | 924 |
return GlpkMip::ProblemType(); |
| 925 | 925 |
} |
| 926 | 926 |
case GLP_NOFEAS: |
| 927 | 927 |
return INFEASIBLE; |
| 928 | 928 |
case GLP_INFEAS: |
| 929 | 929 |
case GLP_FEAS: |
| 930 | 930 |
if (glp_get_dual_stat(lp) == GLP_NOFEAS) {
|
| 931 | 931 |
return UNBOUNDED; |
| 932 | 932 |
} else {
|
| 933 | 933 |
return UNDEFINED; |
| 934 | 934 |
} |
| 935 | 935 |
default: |
| 936 | 936 |
LEMON_ASSERT(false, "Wrong problem type."); |
| 937 | 937 |
return GlpkMip::ProblemType(); |
| 938 | 938 |
} |
| 939 | 939 |
} |
| 940 | 940 |
|
| 941 | 941 |
GlpkMip::Value GlpkMip::_getSol(int i) const {
|
| 942 | 942 |
return glp_mip_col_val(lp, i); |
| 943 | 943 |
} |
| 944 | 944 |
|
| 945 | 945 |
GlpkMip::Value GlpkMip::_getSolValue() const {
|
| 946 | 946 |
return glp_mip_obj_val(lp); |
| 947 | 947 |
} |
| 948 | 948 |
|
| 949 | 949 |
GlpkMip* GlpkMip::newSolver() const { return new GlpkMip; }
|
| 950 | 950 |
GlpkMip* GlpkMip::cloneSolver() const {return new GlpkMip(*this); }
|
| 951 | 951 |
|
| 952 | 952 |
const char* GlpkMip::_solverName() const { return "GlpkMip"; }
|
| 953 | 953 |
|
| 954 | 954 |
void GlpkMip::messageLevel(MessageLevel m) {
|
| 955 | 955 |
_message_level = m; |
| 956 | 956 |
} |
| 957 | 957 |
|
| 958 | 958 |
} //END OF NAMESPACE LEMON |
| 1 | 1 |
#!/bin/bash |
| 2 | 2 |
|
| 3 | 3 |
YEAR=`date +2003-%Y` |
| 4 | 4 |
HGROOT=`hg root` |
| 5 | 5 |
|
| 6 | 6 |
# file enumaration modes |
| 7 | 7 |
|
| 8 | 8 |
function all_files() {
|
| 9 | 9 |
hg status -a -m -c | |
| 10 | 10 |
cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | |
| 11 | 11 |
while read file; do echo $HGROOT/$file; done |
| 12 | 12 |
} |
| 13 | 13 |
|
| 14 | 14 |
function modified_files() {
|
| 15 | 15 |
hg status -a -m | |
| 16 | 16 |
cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | |
| 17 | 17 |
while read file; do echo $HGROOT/$file; done |
| 18 | 18 |
} |
| 19 | 19 |
|
| 20 | 20 |
function changed_files() {
|
| 21 | 21 |
{
|
| 22 | 22 |
if [ -n "$HG_PARENT1" ] |
| 23 | 23 |
then |
| 24 | 24 |
hg status --rev $HG_PARENT1:$HG_NODE -a -m |
| 25 | 25 |
fi |
| 26 | 26 |
if [ -n "$HG_PARENT2" ] |
| 27 | 27 |
then |
| 28 | 28 |
hg status --rev $HG_PARENT2:$HG_NODE -a -m |
| 29 | 29 |
fi |
| 30 | 30 |
} | cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' | |
| 31 | 31 |
sort | uniq | |
| 32 | 32 |
while read file; do echo $HGROOT/$file; done |
| 33 | 33 |
} |
| 34 | 34 |
|
| 35 | 35 |
function given_files() {
|
| 36 | 36 |
for file in $GIVEN_FILES |
| 37 | 37 |
do |
| 38 | 38 |
echo $file |
| 39 | 39 |
done |
| 40 | 40 |
} |
| 41 | 41 |
|
| 42 | 42 |
# actions |
| 43 | 43 |
|
| 44 | 44 |
function update_action() {
|
| 45 | 45 |
if ! diff -q $1 $2 >/dev/null |
| 46 | 46 |
then |
| 47 | 47 |
echo -n " [$3 updated]" |
| 48 | 48 |
rm $2 |
| 49 | 49 |
mv $1 $2 |
| 50 | 50 |
CHANGED=YES |
| 51 | 51 |
fi |
| 52 | 52 |
} |
| 53 | 53 |
|
| 54 | 54 |
function update_warning() {
|
| 55 | 55 |
echo -n " [$2 warning]" |
| 56 | 56 |
WARNED=YES |
| 57 | 57 |
} |
| 58 | 58 |
|
| 59 | 59 |
function update_init() {
|
| 60 | 60 |
echo Update source files... |
| 61 | 61 |
TOTAL_FILES=0 |
| 62 | 62 |
CHANGED_FILES=0 |
| 63 | 63 |
WARNED_FILES=0 |
| 64 | 64 |
} |
| 65 | 65 |
|
| 66 | 66 |
function update_done() {
|
| 67 | 67 |
echo $CHANGED_FILES out of $TOTAL_FILES files has been changed. |
| 68 | 68 |
echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings. |
| 69 | 69 |
} |
| 70 | 70 |
|
| 71 | 71 |
function update_begin() {
|
| 72 | 72 |
((TOTAL_FILES++)) |
| 73 | 73 |
CHANGED=NO |
| 74 | 74 |
WARNED=NO |
| 75 | 75 |
} |
| 76 | 76 |
|
| 77 | 77 |
function update_end() {
|
| 78 | 78 |
if [ $CHANGED == YES ] |
| 79 | 79 |
then |
| 80 | 80 |
((++CHANGED_FILES)) |
| 81 | 81 |
fi |
| 82 | 82 |
if [ $WARNED == YES ] |
| 83 | 83 |
then |
| 84 | 84 |
((++WARNED_FILES)) |
| 85 | 85 |
fi |
| 86 | 86 |
} |
| 87 | 87 |
|
| 88 | 88 |
function check_action() {
|
| 89 | 89 |
if [ "$3" == 'tabs' ] |
| 90 | 90 |
then |
| 91 |
if echo $2 | grep -q -v -E 'Makefile\.am$' |
|
| 92 |
then |
|
| 91 | 93 |
PATTERN=$(echo -e '\t') |
| 94 |
else |
|
| 95 |
PATTERN=' ' |
|
| 96 |
fi |
|
| 92 | 97 |
elif [ "$3" == 'trailing spaces' ] |
| 93 | 98 |
then |
| 94 | 99 |
PATTERN='\ +$' |
| 95 | 100 |
else |
| 96 | 101 |
PATTERN='*' |
| 97 | 102 |
fi |
| 98 | 103 |
|
| 99 | 104 |
if ! diff -q $1 $2 >/dev/null |
| 100 | 105 |
then |
| 101 | 106 |
if [ "$PATTERN" == '*' ] |
| 102 | 107 |
then |
| 103 | 108 |
diff $1 $2 | grep '^[0-9]' | sed "s|^\(.*\)c.*$|$2:\1: check failed: $3|g" | |
| 104 | 109 |
sed "s/:\([0-9]*\),\([0-9]*\):\(.*\)$/:\1:\3 (until line \2)/g" |
| 105 | 110 |
else |
| 106 | 111 |
grep -n -E "$PATTERN" $2 | sed "s|^\([0-9]*\):.*$|$2:\1: check failed: $3|g" |
| 107 | 112 |
fi |
| 108 | 113 |
FAILED=YES |
| 109 | 114 |
fi |
| 110 | 115 |
} |
| 111 | 116 |
|
| 112 | 117 |
function check_warning() {
|
| 113 | 118 |
if [ "$2" == 'long lines' ] |
| 114 | 119 |
then |
| 115 | 120 |
grep -n -E '.{81,}' $1 | sed "s|^\([0-9]*\):.*$|$1:\1: warning: $2|g"
|
| 116 | 121 |
else |
| 117 | 122 |
echo "$1: warning: $2" |
| 118 | 123 |
fi |
| 119 | 124 |
WARNED=YES |
| 120 | 125 |
} |
| 121 | 126 |
|
| 122 | 127 |
function check_init() {
|
| 123 | 128 |
echo Check source files... |
| 124 | 129 |
FAILED_FILES=0 |
| 125 | 130 |
WARNED_FILES=0 |
| 126 | 131 |
TOTAL_FILES=0 |
| 127 | 132 |
} |
| 128 | 133 |
|
| 129 | 134 |
function check_done() {
|
| 130 | 135 |
echo $FAILED_FILES out of $TOTAL_FILES files has been failed. |
| 131 | 136 |
echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings. |
| 132 | 137 |
|
| 133 | 138 |
if [ $WARNED_FILES -gt 0 -o $FAILED_FILES -gt 0 ] |
| 134 | 139 |
then |
| 135 | 140 |
if [ "$WARNING" == 'INTERACTIVE' ] |
| 136 | 141 |
then |
| 137 | 142 |
echo -n "Are the files with errors/warnings acceptable? (yes/no) " |
| 138 | 143 |
while read answer |
| 139 | 144 |
do |
| 140 | 145 |
if [ "$answer" == 'yes' ] |
| 141 | 146 |
then |
| 142 | 147 |
return 0 |
| 143 | 148 |
elif [ "$answer" == 'no' ] |
| 144 | 149 |
then |
| 145 | 150 |
return 1 |
| 146 | 151 |
fi |
| 147 | 152 |
echo -n "Are the files with errors/warnings acceptable? (yes/no) " |
| 148 | 153 |
done |
| 149 | 154 |
elif [ "$WARNING" == 'WERROR' ] |
| 150 | 155 |
then |
| 151 | 156 |
return 1 |
| 152 | 157 |
fi |
| 153 | 158 |
fi |
| 154 | 159 |
} |
| 155 | 160 |
|
| 156 | 161 |
function check_begin() {
|
| 157 | 162 |
((TOTAL_FILES++)) |
| 158 | 163 |
FAILED=NO |
| 159 | 164 |
WARNED=NO |
| 160 | 165 |
} |
| 161 | 166 |
|
| 162 | 167 |
function check_end() {
|
| 163 | 168 |
if [ $FAILED == YES ] |
| 164 | 169 |
then |
| 165 | 170 |
((++FAILED_FILES)) |
| 166 | 171 |
fi |
| 167 | 172 |
if [ $WARNED == YES ] |
| 168 | 173 |
then |
| 169 | 174 |
((++WARNED_FILES)) |
| 170 | 175 |
fi |
| 171 | 176 |
} |
| 172 | 177 |
|
| 173 | 178 |
|
| 174 | 179 |
|
| 175 | 180 |
# checks |
| 176 | 181 |
|
| 177 | 182 |
function header_check() {
|
| 178 | 183 |
if echo $1 | grep -q -E 'Makefile\.am$' |
| 179 | 184 |
then |
| 180 | 185 |
return |
| 181 | 186 |
fi |
| 182 | 187 |
|
| 183 | 188 |
TMP_FILE=`mktemp` |
| 184 | 189 |
|
| 185 | 190 |
(echo "/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 186 | 191 |
* |
| 187 | 192 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 188 | 193 |
* |
| 189 | 194 |
* Copyright (C) "$YEAR" |
| 190 | 195 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 191 | 196 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 192 | 197 |
* |
| 193 | 198 |
* Permission to use, modify and distribute this software is granted |
| 194 | 199 |
* provided that this copyright notice appears in all copies. For |
| 195 | 200 |
* precise terms see the accompanying LICENSE file. |
| 196 | 201 |
* |
| 197 | 202 |
* This software is provided \"AS IS\" with no warranty of any kind, |
| 198 | 203 |
* express or implied, and with no claim as to its suitability for any |
| 199 | 204 |
* purpose. |
| 200 | 205 |
* |
| 201 | 206 |
*/ |
| 202 | 207 |
" |
| 203 | 208 |
awk 'BEGIN { pm=0; }
|
| 204 | 209 |
pm==3 { print }
|
| 205 | 210 |
/\/\* / && pm==0 { pm=1;}
|
| 206 | 211 |
/[^:blank:]/ && (pm==0 || pm==2) { pm=3; print;}
|
| 207 | 212 |
/\*\// && pm==1 { pm=2;}
|
| 208 | 213 |
' $1 |
| 209 | 214 |
) >$TMP_FILE |
| 210 | 215 |
|
| 211 | 216 |
"$ACTION"_action "$TMP_FILE" "$1" header |
| 212 | 217 |
} |
| 213 | 218 |
|
| 214 | 219 |
function tabs_check() {
|
| 215 | 220 |
if echo $1 | grep -q -v -E 'Makefile\.am$' |
| 216 | 221 |
then |
| 217 | 222 |
OLD_PATTERN=$(echo -e '\t') |
| 218 | 223 |
NEW_PATTERN=' ' |
| 219 | 224 |
else |
| 220 | 225 |
OLD_PATTERN=' ' |
| 221 | 226 |
NEW_PATTERN=$(echo -e '\t') |
| 222 | 227 |
fi |
| 223 | 228 |
TMP_FILE=`mktemp` |
| 224 | 229 |
cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE |
| 225 | 230 |
|
| 226 | 231 |
"$ACTION"_action "$TMP_FILE" "$1" 'tabs' |
| 227 | 232 |
} |
| 228 | 233 |
|
| 229 | 234 |
function spaces_check() {
|
| 230 | 235 |
TMP_FILE=`mktemp` |
| 231 | 236 |
cat $1 | sed -e 's/ \+$//g' >$TMP_FILE |
| 232 | 237 |
|
| 233 | 238 |
"$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces' |
| 234 | 239 |
} |
| 235 | 240 |
|
| 236 | 241 |
function long_lines_check() {
|
| 237 | 242 |
if cat $1 | grep -q -E '.{81,}'
|
| 238 | 243 |
then |
| 239 | 244 |
"$ACTION"_warning $1 'long lines' |
| 240 | 245 |
fi |
| 241 | 246 |
} |
| 242 | 247 |
|
| 243 | 248 |
# process the file |
| 244 | 249 |
|
| 245 | 250 |
function process_file() {
|
| 246 | 251 |
if [ "$ACTION" == 'update' ] |
| 247 | 252 |
then |
| 248 | 253 |
echo -n " $ACTION $1..." |
| 249 | 254 |
else |
| 250 | 255 |
echo " $ACTION $1..." |
| 251 | 256 |
fi |
| 252 | 257 |
|
| 253 | 258 |
CHECKING="header tabs spaces long_lines" |
| 254 | 259 |
|
| 255 | 260 |
"$ACTION"_begin $1 |
| 256 | 261 |
for check in $CHECKING |
| 257 | 262 |
do |
| 258 | 263 |
"$check"_check $1 |
| 259 | 264 |
done |
| 260 | 265 |
"$ACTION"_end $1 |
| 261 | 266 |
if [ "$ACTION" == 'update' ] |
| 262 | 267 |
then |
| 263 | 268 |
echo |
| 264 | 269 |
fi |
| 265 | 270 |
} |
| 266 | 271 |
|
| 267 | 272 |
function process_all {
|
| 268 | 273 |
"$ACTION"_init |
| 269 | 274 |
while read file |
| 270 | 275 |
do |
| 271 | 276 |
process_file $file |
| 272 | 277 |
done < <($FILES) |
| 273 | 278 |
"$ACTION"_done |
| 274 | 279 |
} |
| 275 | 280 |
|
| 276 | 281 |
while [ $# -gt 0 ] |
| 277 | 282 |
do |
| 278 | 283 |
|
| 279 | 284 |
if [ "$1" == '--help' ] || [ "$1" == '-h' ] |
| 280 | 285 |
then |
| 281 | 286 |
echo -n \ |
| 282 | 287 |
"Usage: |
| 283 | 288 |
$0 [OPTIONS] [files] |
| 284 | 289 |
Options: |
| 285 | 290 |
--dry-run|-n |
| 286 | 291 |
Check the files, but do not modify them. |
| 287 | 292 |
--interactive|-i |
| 288 | 293 |
If --dry-run is specified and the checker emits warnings, |
| 289 | 294 |
then the user is asked if the warnings should be considered |
| 290 | 295 |
errors. |
| 291 | 296 |
--werror|-w |
| 292 | 297 |
Make all warnings into errors. |
| 293 | 298 |
--all|-a |
| 294 | 299 |
Check all source files in the repository. |
| 295 | 300 |
--modified|-m |
| 296 | 301 |
Check only the modified (and new) source files. This option is |
| 297 | 302 |
useful to check the modification before making a commit. |
| 298 | 303 |
--changed|-c |
| 299 | 304 |
Check only the changed source files compared to the parent(s) of |
| 300 | 305 |
the current hg node. This option is useful as hg hook script. |
| 301 | 306 |
To automatically check all your changes before making a commit, |
| 302 | 307 |
add the following section to the appropriate .hg/hgrc file. |
| 303 | 308 |
|
| 304 | 309 |
[hooks] |
| 305 | 310 |
pretxncommit.checksources = scripts/unify-sources.sh -c -n -i |
| 306 | 311 |
|
| 307 | 312 |
--help|-h |
| 308 | 313 |
Print this help message. |
| 309 | 314 |
files |
| 310 | 315 |
The files to check/unify. If no file names are given, the modified |
| 311 | 316 |
source files will be checked/unified (just like using the |
| 312 | 317 |
--modified|-m option). |
| 313 | 318 |
" |
| 314 | 319 |
exit 0 |
| 315 | 320 |
elif [ "$1" == '--dry-run' ] || [ "$1" == '-n' ] |
| 316 | 321 |
then |
| 317 | 322 |
[ -n "$ACTION" ] && echo "Conflicting action options" >&2 && exit 1 |
| 318 | 323 |
ACTION=check |
| 319 | 324 |
elif [ "$1" == "--all" ] || [ "$1" == '-a' ] |
| 320 | 325 |
then |
| 321 | 326 |
[ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 |
| 322 | 327 |
FILES=all_files |
| 323 | 328 |
elif [ "$1" == "--changed" ] || [ "$1" == '-c' ] |
| 324 | 329 |
then |
| 325 | 330 |
[ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 |
| 326 | 331 |
FILES=changed_files |
| 327 | 332 |
elif [ "$1" == "--modified" ] || [ "$1" == '-m' ] |
| 328 | 333 |
then |
| 329 | 334 |
[ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1 |
| 330 | 335 |
FILES=modified_files |
| 331 | 336 |
elif [ "$1" == "--interactive" ] || [ "$1" == "-i" ] |
| 332 | 337 |
then |
| 333 | 338 |
[ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1 |
| 334 | 339 |
WARNING='INTERACTIVE' |
| 335 | 340 |
elif [ "$1" == "--werror" ] || [ "$1" == "-w" ] |
| 336 | 341 |
then |
| 337 | 342 |
[ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1 |
| 338 | 343 |
WARNING='WERROR' |
| 339 | 344 |
elif [ $(echo x$1 | cut -c 2) == '-' ] |
| 340 | 345 |
then |
| 341 | 346 |
echo "Invalid option $1" >&2 && exit 1 |
| 342 | 347 |
else |
| 343 | 348 |
[ -n "$FILES" ] && echo "Invalid option $1" >&2 && exit 1 |
| 344 | 349 |
GIVEN_FILES=$@ |
| 345 | 350 |
FILES=given_files |
| 346 | 351 |
break |
| 347 | 352 |
fi |
| 348 | 353 |
|
| 349 | 354 |
shift |
| 350 | 355 |
done |
| 351 | 356 |
|
| 352 | 357 |
if [ -z $FILES ] |
| 353 | 358 |
then |
| 354 | 359 |
FILES=modified_files |
| 355 | 360 |
fi |
| 356 | 361 |
|
| 357 | 362 |
if [ -z $ACTION ] |
| 358 | 363 |
then |
| 359 | 364 |
ACTION=update |
| 360 | 365 |
fi |
| 361 | 366 |
|
| 362 | 367 |
process_all |
| 1 | 1 |
INCLUDE_DIRECTORIES( |
| 2 |
${CMAKE_SOURCE_DIR}
|
|
| 3 |
${CMAKE_BINARY_DIR}
|
|
| 2 |
${PROJECT_SOURCE_DIR}
|
|
| 3 |
${PROJECT_BINARY_DIR}
|
|
| 4 | 4 |
) |
| 5 | 5 |
|
| 6 | 6 |
IF(HAVE_GLPK) |
| 7 | 7 |
INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
|
| 8 | 8 |
ENDIF(HAVE_GLPK) |
| 9 | 9 |
|
| 10 |
LINK_DIRECTORIES(${
|
|
| 10 |
LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
|
|
| 11 | 11 |
|
| 12 | 12 |
SET(TESTS |
| 13 | 13 |
adaptors_test |
| 14 | 14 |
bfs_test |
| 15 | 15 |
circulation_test |
| 16 | 16 |
counter_test |
| 17 | 17 |
dfs_test |
| 18 | 18 |
digraph_test |
| 19 | 19 |
dijkstra_test |
| 20 | 20 |
dim_test |
| 21 | 21 |
edge_set_test |
| 22 | 22 |
error_test |
| 23 | 23 |
euler_test |
| 24 | 24 |
gomory_hu_test |
| 25 | 25 |
graph_copy_test |
| 26 | 26 |
graph_test |
| 27 | 27 |
graph_utils_test |
| 28 | 28 |
hao_orlin_test |
| 29 | 29 |
heap_test |
| 30 | 30 |
kruskal_test |
| 31 | 31 |
maps_test |
| 32 | 32 |
max_matching_test |
| 33 | 33 |
min_cost_arborescence_test |
| 34 | 34 |
path_test |
| 35 | 35 |
preflow_test |
| 36 | 36 |
radix_sort_test |
| 37 | 37 |
random_test |
| 38 | 38 |
suurballe_test |
| 39 | 39 |
time_measure_test |
| 40 | 40 |
unionfind_test) |
| 41 | 41 |
|
| 42 | 42 |
IF(HAVE_LP) |
| 43 | 43 |
ADD_EXECUTABLE(lp_test lp_test.cc) |
| 44 | 44 |
IF(HAVE_GLPK) |
| 45 | 45 |
TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES})
|
| 46 | 46 |
ENDIF(HAVE_GLPK) |
| 47 | 47 |
ADD_TEST(lp_test lp_test) |
| 48 | 48 |
|
| 49 | 49 |
IF(WIN32 AND HAVE_GLPK) |
| 50 | 50 |
GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION) |
| 51 | 51 |
GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
|
| 52 | 52 |
ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD |
| 53 | 53 |
COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
|
| 54 | 54 |
COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
|
| 55 | 55 |
COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
|
| 56 | 56 |
) |
| 57 | 57 |
ENDIF(WIN32 AND HAVE_GLPK) |
| 58 | 58 |
ENDIF(HAVE_LP) |
| 59 | 59 |
|
| 60 | 60 |
IF(HAVE_MIP) |
| 61 | 61 |
ADD_EXECUTABLE(mip_test mip_test.cc) |
| 62 | 62 |
IF(HAVE_GLPK) |
| 63 | 63 |
TARGET_LINK_LIBRARIES(mip_test lemon ${GLPK_LIBRARIES})
|
| 64 | 64 |
ENDIF(HAVE_GLPK) |
| 65 | 65 |
ADD_TEST(mip_test mip_test) |
| 66 | 66 |
|
| 67 | 67 |
IF(WIN32 AND HAVE_GLPK) |
| 68 | 68 |
GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION) |
| 69 | 69 |
GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
|
| 70 | 70 |
ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD |
| 71 | 71 |
COMMAND cmake -E copy ${GLPK_BIN_DIR}/glpk.dll ${TARGET_PATH}
|
| 72 | 72 |
COMMAND cmake -E copy ${GLPK_BIN_DIR}/libltdl3.dll ${TARGET_PATH}
|
| 73 | 73 |
COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
|
| 74 | 74 |
) |
| 75 | 75 |
ENDIF(WIN32 AND HAVE_GLPK) |
| 76 | 76 |
ENDIF(HAVE_MIP) |
| 77 | 77 |
|
| 78 | 78 |
FOREACH(TEST_NAME ${TESTS})
|
| 79 | 79 |
ADD_EXECUTABLE(${TEST_NAME} ${TEST_NAME}.cc)
|
| 80 | 80 |
TARGET_LINK_LIBRARIES(${TEST_NAME} lemon)
|
| 81 | 81 |
ADD_TEST(${TEST_NAME} ${TEST_NAME})
|
| 82 | 82 |
ENDFOREACH(TEST_NAME) |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 | 5 |
* Copyright (C) 2003-2009 |
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/counter.h> |
| 20 | 20 |
#include <vector> |
| 21 |
#include <sstream> |
|
| 22 |
|
|
| 23 |
#include "test/test_tools.h" |
|
| 21 | 24 |
|
| 22 | 25 |
using namespace lemon; |
| 23 | 26 |
|
| 24 | 27 |
template <typename T> |
| 25 | 28 |
void bubbleSort(std::vector<T>& v) {
|
| 26 |
Counter op("Bubble Sort - Operations: ");
|
|
| 27 |
Counter::NoSubCounter as(op, "Assignments: "); |
|
| 28 |
|
|
| 29 |
std::stringstream s1, s2, s3; |
|
| 30 |
{
|
|
| 31 |
Counter op("Bubble Sort - Operations: ", s1);
|
|
| 32 |
Counter::SubCounter as(op, "Assignments: ", s2); |
|
| 33 |
Counter::SubCounter co(op, "Comparisons: ", s3); |
|
| 29 | 34 |
for (int i = v.size()-1; i > 0; --i) {
|
| 30 | 35 |
for (int j = 0; j < i; ++j) {
|
| 31 | 36 |
if (v[j] > v[j+1]) {
|
| 32 | 37 |
T tmp = v[j]; |
| 33 | 38 |
v[j] = v[j+1]; |
| 34 | 39 |
v[j+1] = tmp; |
| 35 | 40 |
as += 3; |
| 36 | 41 |
} |
| 37 | 42 |
++co; |
| 38 | 43 |
} |
| 39 | 44 |
} |
| 40 | 45 |
} |
| 46 |
check(s1.str() == "Bubble Sort - Operations: 102\n", "Wrong counter"); |
|
| 47 |
check(s2.str() == "Assignments: 57\n", "Wrong subcounter"); |
|
| 48 |
check(s3.str() == "Comparisons: 45\n", "Wrong subcounter"); |
|
| 49 |
} |
|
| 41 | 50 |
|
| 42 | 51 |
template <typename T> |
| 43 | 52 |
void insertionSort(std::vector<T>& v) {
|
| 44 |
Counter op("Insertion Sort - Operations: ");
|
|
| 45 |
Counter::NoSubCounter as(op, "Assignments: "); |
|
| 46 |
|
|
| 53 |
std::stringstream s1, s2, s3; |
|
| 54 |
{
|
|
| 55 |
Counter op("Insertion Sort - Operations: ", s1);
|
|
| 56 |
Counter::SubCounter as(op, "Assignments: ", s2); |
|
| 57 |
Counter::SubCounter co(op, "Comparisons: ", s3); |
|
| 47 | 58 |
for (int i = 1; i < int(v.size()); ++i) {
|
| 48 | 59 |
T value = v[i]; |
| 49 | 60 |
++as; |
| 50 | 61 |
int j = i; |
| 51 | 62 |
while (j > 0 && v[j-1] > value) {
|
| 52 | 63 |
v[j] = v[j-1]; |
| 53 | 64 |
--j; |
| 54 | 65 |
++co; ++as; |
| 55 | 66 |
} |
| 56 | 67 |
v[j] = value; |
| 57 | 68 |
++as; |
| 58 | 69 |
} |
| 59 | 70 |
} |
| 71 |
check(s1.str() == "Insertion Sort - Operations: 56\n", "Wrong counter"); |
|
| 72 |
check(s2.str() == "Assignments: 37\n", "Wrong subcounter"); |
|
| 73 |
check(s3.str() == "Comparisons: 19\n", "Wrong subcounter"); |
|
| 74 |
} |
|
| 60 | 75 |
|
| 61 | 76 |
template <typename MyCounter> |
| 62 |
void counterTest() {
|
|
| 63 |
MyCounter c("Main Counter: ");
|
|
| 77 |
void counterTest(bool output) {
|
|
| 78 |
std::stringstream s1, s2, s3; |
|
| 79 |
{
|
|
| 80 |
MyCounter c("Main Counter: ", s1);
|
|
| 64 | 81 |
c++; |
| 65 |
typename MyCounter::SubCounter d(c, "SubCounter: "); |
|
| 82 |
typename MyCounter::SubCounter d(c, "SubCounter: ", s2); |
|
| 66 | 83 |
d++; |
| 67 |
typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: "); |
|
| 84 |
typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ", s3); |
|
| 68 | 85 |
e++; |
| 69 | 86 |
d+=3; |
| 70 | 87 |
c-=4; |
| 71 | 88 |
e-=2; |
| 72 | 89 |
c.reset(2); |
| 73 | 90 |
c.reset(); |
| 74 | 91 |
} |
| 92 |
if (output) {
|
|
| 93 |
check(s1.str() == "Main Counter: 3\n", "Wrong Counter"); |
|
| 94 |
check(s2.str() == "SubCounter: 3\n", "Wrong SubCounter"); |
|
| 95 |
check(s3.str() == "", "Wrong NoSubCounter"); |
|
| 96 |
} else {
|
|
| 97 |
check(s1.str() == "", "Wrong NoCounter"); |
|
| 98 |
check(s2.str() == "", "Wrong SubCounter"); |
|
| 99 |
check(s3.str() == "", "Wrong NoSubCounter"); |
|
| 100 |
} |
|
| 101 |
} |
|
| 75 | 102 |
|
| 76 | 103 |
void init(std::vector<int>& v) {
|
| 77 | 104 |
v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100; |
| 78 | 105 |
v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70; |
| 79 | 106 |
} |
| 80 | 107 |
|
| 81 | 108 |
int main() |
| 82 | 109 |
{
|
| 83 |
counterTest<Counter>(); |
|
| 84 |
counterTest<NoCounter>(); |
|
| 110 |
counterTest<Counter>(true); |
|
| 111 |
counterTest<NoCounter>(false); |
|
| 85 | 112 |
|
| 86 | 113 |
std::vector<int> x(10); |
| 87 | 114 |
init(x); bubbleSort(x); |
| 88 | 115 |
init(x); insertionSort(x); |
| 89 | 116 |
|
| 90 | 117 |
return 0; |
| 91 | 118 |
} |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include <sstream> |
| 20 | 20 |
#include <lemon/lp_skeleton.h> |
| 21 | 21 |
#include "test_tools.h" |
| 22 | 22 |
#include <lemon/tolerance.h> |
| 23 | 23 |
|
| 24 | 24 |
#ifdef HAVE_CONFIG_H |
| 25 | 25 |
#include <lemon/config.h> |
| 26 | 26 |
#endif |
| 27 | 27 |
|
| 28 | 28 |
#ifdef HAVE_GLPK |
| 29 | 29 |
#include <lemon/glpk.h> |
| 30 | 30 |
#endif |
| 31 | 31 |
|
| 32 | 32 |
#ifdef HAVE_CPLEX |
| 33 | 33 |
#include <lemon/cplex.h> |
| 34 | 34 |
#endif |
| 35 | 35 |
|
| 36 | 36 |
#ifdef HAVE_SOPLEX |
| 37 | 37 |
#include <lemon/soplex.h> |
| 38 | 38 |
#endif |
| 39 | 39 |
|
| 40 | 40 |
#ifdef HAVE_CLP |
| 41 | 41 |
#include <lemon/clp.h> |
| 42 | 42 |
#endif |
| 43 | 43 |
|
| 44 | 44 |
using namespace lemon; |
| 45 | 45 |
|
| 46 | 46 |
void lpTest(LpSolver& lp) |
| 47 | 47 |
{
|
| 48 | 48 |
|
| 49 | 49 |
typedef LpSolver LP; |
| 50 | 50 |
|
| 51 | 51 |
std::vector<LP::Col> x(10); |
| 52 | 52 |
// for(int i=0;i<10;i++) x.push_back(lp.addCol()); |
| 53 | 53 |
lp.addColSet(x); |
| 54 | 54 |
lp.colLowerBound(x,1); |
| 55 | 55 |
lp.colUpperBound(x,1); |
| 56 | 56 |
lp.colBounds(x,1,2); |
| 57 | 57 |
|
| 58 | 58 |
std::vector<LP::Col> y(10); |
| 59 | 59 |
lp.addColSet(y); |
| 60 | 60 |
|
| 61 | 61 |
lp.colLowerBound(y,1); |
| 62 | 62 |
lp.colUpperBound(y,1); |
| 63 | 63 |
lp.colBounds(y,1,2); |
| 64 | 64 |
|
| 65 | 65 |
std::map<int,LP::Col> z; |
| 66 | 66 |
|
| 67 | 67 |
z.insert(std::make_pair(12,INVALID)); |
| 68 | 68 |
z.insert(std::make_pair(2,INVALID)); |
| 69 | 69 |
z.insert(std::make_pair(7,INVALID)); |
| 70 | 70 |
z.insert(std::make_pair(5,INVALID)); |
| 71 | 71 |
|
| 72 | 72 |
lp.addColSet(z); |
| 73 | 73 |
|
| 74 | 74 |
lp.colLowerBound(z,1); |
| 75 | 75 |
lp.colUpperBound(z,1); |
| 76 | 76 |
lp.colBounds(z,1,2); |
| 77 | 77 |
|
| 78 | 78 |
{
|
| 79 | 79 |
LP::Expr e,f,g; |
| 80 | 80 |
LP::Col p1,p2,p3,p4,p5; |
| 81 | 81 |
LP::Constr c; |
| 82 | 82 |
|
| 83 | 83 |
p1=lp.addCol(); |
| 84 | 84 |
p2=lp.addCol(); |
| 85 | 85 |
p3=lp.addCol(); |
| 86 | 86 |
p4=lp.addCol(); |
| 87 | 87 |
p5=lp.addCol(); |
| 88 | 88 |
|
| 89 | 89 |
e[p1]=2; |
| 90 | 90 |
*e=12; |
| 91 | 91 |
e[p1]+=2; |
| 92 | 92 |
*e+=12; |
| 93 | 93 |
e[p1]-=2; |
| 94 | 94 |
*e-=12; |
| 95 | 95 |
|
| 96 | 96 |
e=2; |
| 97 | 97 |
e=2.2; |
| 98 | 98 |
e=p1; |
| 99 | 99 |
e=f; |
| 100 | 100 |
|
| 101 | 101 |
e+=2; |
| 102 | 102 |
e+=2.2; |
| 103 | 103 |
e+=p1; |
| 104 | 104 |
e+=f; |
| 105 | 105 |
|
| 106 | 106 |
e-=2; |
| 107 | 107 |
e-=2.2; |
| 108 | 108 |
e-=p1; |
| 109 | 109 |
e-=f; |
| 110 | 110 |
|
| 111 | 111 |
e*=2; |
| 112 | 112 |
e*=2.2; |
| 113 | 113 |
e/=2; |
| 114 | 114 |
e/=2.2; |
| 115 | 115 |
|
| 116 | 116 |
e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+ |
| 117 | 117 |
(f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+ |
| 118 | 118 |
(f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+ |
| 119 | 119 |
2.2*f+f*2.2+f/2.2+ |
| 120 | 120 |
2*f+f*2+f/2+ |
| 121 | 121 |
2.2*p1+p1*2.2+p1/2.2+ |
| 122 | 122 |
2*p1+p1*2+p1/2 |
| 123 | 123 |
); |
| 124 | 124 |
|
| 125 | 125 |
|
| 126 | 126 |
c = (e <= f ); |
| 127 | 127 |
c = (e <= 2.2); |
| 128 | 128 |
c = (e <= 2 ); |
| 129 | 129 |
c = (e <= p1 ); |
| 130 | 130 |
c = (2.2<= f ); |
| 131 | 131 |
c = (2 <= f ); |
| 132 | 132 |
c = (p1 <= f ); |
| 133 | 133 |
c = (p1 <= p2 ); |
| 134 | 134 |
c = (p1 <= 2.2); |
| 135 | 135 |
c = (p1 <= 2 ); |
| 136 | 136 |
c = (2.2<= p2 ); |
| 137 | 137 |
c = (2 <= p2 ); |
| 138 | 138 |
|
| 139 | 139 |
c = (e >= f ); |
| 140 | 140 |
c = (e >= 2.2); |
| 141 | 141 |
c = (e >= 2 ); |
| 142 | 142 |
c = (e >= p1 ); |
| 143 | 143 |
c = (2.2>= f ); |
| 144 | 144 |
c = (2 >= f ); |
| 145 | 145 |
c = (p1 >= f ); |
| 146 | 146 |
c = (p1 >= p2 ); |
| 147 | 147 |
c = (p1 >= 2.2); |
| 148 | 148 |
c = (p1 >= 2 ); |
| 149 | 149 |
c = (2.2>= p2 ); |
| 150 | 150 |
c = (2 >= p2 ); |
| 151 | 151 |
|
| 152 | 152 |
c = (e == f ); |
| 153 | 153 |
c = (e == 2.2); |
| 154 | 154 |
c = (e == 2 ); |
| 155 | 155 |
c = (e == p1 ); |
| 156 | 156 |
c = (2.2== f ); |
| 157 | 157 |
c = (2 == f ); |
| 158 | 158 |
c = (p1 == f ); |
| 159 | 159 |
//c = (p1 == p2 ); |
| 160 | 160 |
c = (p1 == 2.2); |
| 161 | 161 |
c = (p1 == 2 ); |
| 162 | 162 |
c = (2.2== p2 ); |
| 163 | 163 |
c = (2 == p2 ); |
| 164 | 164 |
|
| 165 | 165 |
c = ((2 <= e) <= 3); |
| 166 | 166 |
c = ((2 <= p1) <= 3); |
| 167 | 167 |
|
| 168 | 168 |
c = ((2 >= e) >= 3); |
| 169 | 169 |
c = ((2 >= p1) >= 3); |
| 170 | 170 |
|
| 171 | 171 |
e[x[3]]=2; |
| 172 | 172 |
e[x[3]]=4; |
| 173 | 173 |
e[x[3]]=1; |
| 174 | 174 |
*e=12; |
| 175 | 175 |
|
| 176 | 176 |
lp.addRow(-LP::INF,e,23); |
| 177 | 177 |
lp.addRow(-LP::INF,3.0*(x[1]+x[2]/2)-x[3],23); |
| 178 | 178 |
lp.addRow(-LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23); |
| 179 | 179 |
|
| 180 | 180 |
lp.addRow(x[1]+x[3]<=x[5]-3); |
| 181 | 181 |
lp.addRow((-7<=x[1]+x[3]-12)<=3); |
| 182 | 182 |
lp.addRow(x[1]<=x[5]); |
| 183 | 183 |
|
| 184 | 184 |
std::ostringstream buf; |
| 185 | 185 |
|
| 186 | 186 |
|
| 187 | 187 |
e=((p1+p2)+(p1-0.99*p2)); |
| 188 | 188 |
//e.prettyPrint(std::cout); |
| 189 | 189 |
//(e<=2).prettyPrint(std::cout); |
| 190 | 190 |
double tolerance=0.001; |
| 191 | 191 |
e.simplify(tolerance); |
| 192 | 192 |
buf << "Coeff. of p2 should be 0.01"; |
| 193 | 193 |
check(e[p2]>0, buf.str()); |
| 194 | 194 |
|
| 195 | 195 |
tolerance=0.02; |
| 196 | 196 |
e.simplify(tolerance); |
| 197 | 197 |
buf << "Coeff. of p2 should be 0"; |
| 198 | 198 |
check(const_cast<const LpSolver::Expr&>(e)[p2]==0, buf.str()); |
| 199 | 199 |
|
| 200 | 200 |
//Test for clone/new |
| 201 | 201 |
LP* lpnew = lp.newSolver(); |
| 202 | 202 |
LP* lpclone = lp.cloneSolver(); |
| 203 | 203 |
delete lpnew; |
| 204 | 204 |
delete lpclone; |
| 205 | 205 |
|
| 206 | 206 |
} |
| 207 | 207 |
|
| 208 | 208 |
{
|
| 209 | 209 |
LP::DualExpr e,f,g; |
| 210 | 210 |
LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID, |
| 211 | 211 |
p4 = INVALID, p5 = INVALID; |
| 212 | 212 |
|
| 213 | 213 |
e[p1]=2; |
| 214 | 214 |
e[p1]+=2; |
| 215 | 215 |
e[p1]-=2; |
| 216 | 216 |
|
| 217 | 217 |
e=p1; |
| 218 | 218 |
e=f; |
| 219 | 219 |
|
| 220 | 220 |
e+=p1; |
| 221 | 221 |
e+=f; |
| 222 | 222 |
|
| 223 | 223 |
e-=p1; |
| 224 | 224 |
e-=f; |
| 225 | 225 |
|
| 226 | 226 |
e*=2; |
| 227 | 227 |
e*=2.2; |
| 228 | 228 |
e/=2; |
| 229 | 229 |
e/=2.2; |
| 230 | 230 |
|
| 231 | 231 |
e=((p1+p2)+(p1-p2)+ |
| 232 | 232 |
(p1+f)+(f+p1)+(f+g)+ |
| 233 | 233 |
(p1-f)+(f-p1)+(f-g)+ |
| 234 | 234 |
2.2*f+f*2.2+f/2.2+ |
| 235 | 235 |
2*f+f*2+f/2+ |
| 236 | 236 |
2.2*p1+p1*2.2+p1/2.2+ |
| 237 | 237 |
2*p1+p1*2+p1/2 |
| 238 | 238 |
); |
| 239 | 239 |
} |
| 240 | 240 |
|
| 241 | 241 |
} |
| 242 | 242 |
|
| 243 | 243 |
void solveAndCheck(LpSolver& lp, LpSolver::ProblemType stat, |
| 244 | 244 |
double exp_opt) {
|
| 245 | 245 |
using std::string; |
| 246 | 246 |
lp.solve(); |
| 247 | 247 |
|
| 248 | 248 |
std::ostringstream buf; |
| 249 | 249 |
buf << "PrimalType should be: " << int(stat) << int(lp.primalType()); |
| 250 | 250 |
|
| 251 | 251 |
check(lp.primalType()==stat, buf.str()); |
| 252 | 252 |
|
| 253 | 253 |
if (stat == LpSolver::OPTIMAL) {
|
| 254 | 254 |
std::ostringstream sbuf; |
| 255 | 255 |
sbuf << "Wrong optimal value (" << lp.primal() <<") with "
|
| 256 | 256 |
<< lp.solverName() <<"\n the right optimum is " << exp_opt; |
| 257 | 257 |
check(std::abs(lp.primal()-exp_opt) < 1e-3, sbuf.str()); |
| 258 | 258 |
} |
| 259 | 259 |
} |
| 260 | 260 |
|
| 261 | 261 |
void aTest(LpSolver & lp) |
| 262 | 262 |
{
|
| 263 | 263 |
typedef LpSolver LP; |
| 264 | 264 |
|
| 265 | 265 |
//The following example is very simple |
| 266 | 266 |
|
| 267 | 267 |
typedef LpSolver::Row Row; |
| 268 | 268 |
typedef LpSolver::Col Col; |
| 269 | 269 |
|
| 270 | 270 |
|
| 271 | 271 |
Col x1 = lp.addCol(); |
| 272 | 272 |
Col x2 = lp.addCol(); |
| 273 | 273 |
|
| 274 | 274 |
|
| 275 | 275 |
//Constraints |
| 276 | 276 |
Row upright=lp.addRow(x1+2*x2 <=1); |
| 277 | 277 |
lp.addRow(x1+x2 >=-1); |
| 278 | 278 |
lp.addRow(x1-x2 <=1); |
| 279 | 279 |
lp.addRow(x1-x2 >=-1); |
| 280 | 280 |
//Nonnegativity of the variables |
| 281 | 281 |
lp.colLowerBound(x1, 0); |
| 282 | 282 |
lp.colLowerBound(x2, 0); |
| 283 | 283 |
//Objective function |
| 284 | 284 |
lp.obj(x1+x2); |
| 285 | 285 |
|
| 286 | 286 |
lp.sense(lp.MAX); |
| 287 | 287 |
|
| 288 | 288 |
//Testing the problem retrieving routines |
| 289 | 289 |
check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!"); |
| 290 | 290 |
check(lp.sense() == lp.MAX,"This is a maximization!"); |
| 291 | 291 |
check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!"); |
| 292 | 292 |
check(lp.colLowerBound(x1)==0, |
| 293 | 293 |
"The lower bound for variable x1 should be 0."); |
| 294 | 294 |
check(lp.colUpperBound(x1)==LpSolver::INF, |
| 295 | 295 |
"The upper bound for variable x1 should be infty."); |
| 296 | 296 |
check(lp.rowLowerBound(upright) == -LpSolver::INF, |
| 297 | 297 |
"The lower bound for the first row should be -infty."); |
| 298 | 298 |
check(lp.rowUpperBound(upright)==1, |
| 299 | 299 |
"The upper bound for the first row should be 1."); |
| 300 | 300 |
LpSolver::Expr e = lp.row(upright); |
| 301 | 301 |
check(e[x1] == 1, "The first coefficient should 1."); |
| 302 | 302 |
check(e[x2] == 2, "The second coefficient should 1."); |
| 303 | 303 |
|
| 304 | 304 |
lp.row(upright, x1+x2 <=1); |
| 305 | 305 |
e = lp.row(upright); |
| 306 | 306 |
check(e[x1] == 1, "The first coefficient should 1."); |
| 307 | 307 |
check(e[x2] == 1, "The second coefficient should 1."); |
| 308 | 308 |
|
| 309 | 309 |
LpSolver::DualExpr de = lp.col(x1); |
| 310 | 310 |
check( de[upright] == 1, "The first coefficient should 1."); |
| 311 | 311 |
|
| 312 | 312 |
LpSolver* clp = lp.cloneSolver(); |
| 313 | 313 |
|
| 314 | 314 |
//Testing the problem retrieving routines |
| 315 | 315 |
check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!"); |
| 316 | 316 |
check(clp->sense() == clp->MAX,"This is a maximization!"); |
| 317 | 317 |
check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!"); |
| 318 | 318 |
// std::cout<<lp.colLowerBound(x1)<<std::endl; |
| 319 | 319 |
check(clp->colLowerBound(x1)==0, |
| 320 | 320 |
"The lower bound for variable x1 should be 0."); |
| 321 | 321 |
check(clp->colUpperBound(x1)==LpSolver::INF, |
| 322 | 322 |
"The upper bound for variable x1 should be infty."); |
| 323 | 323 |
|
| 324 | 324 |
check(lp.rowLowerBound(upright)==-LpSolver::INF, |
| 325 | 325 |
"The lower bound for the first row should be -infty."); |
| 326 | 326 |
check(lp.rowUpperBound(upright)==1, |
| 327 | 327 |
"The upper bound for the first row should be 1."); |
| 328 | 328 |
e = clp->row(upright); |
| 329 | 329 |
check(e[x1] == 1, "The first coefficient should 1."); |
| 330 | 330 |
check(e[x2] == 1, "The second coefficient should 1."); |
| 331 | 331 |
|
| 332 | 332 |
de = clp->col(x1); |
| 333 | 333 |
check(de[upright] == 1, "The first coefficient should 1."); |
| 334 | 334 |
|
| 335 | 335 |
delete clp; |
| 336 | 336 |
|
| 337 | 337 |
//Maximization of x1+x2 |
| 338 | 338 |
//over the triangle with vertices (0,0) (0,1) (1,0) |
| 339 | 339 |
double expected_opt=1; |
| 340 | 340 |
solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt); |
| 341 | 341 |
|
| 342 | 342 |
//Minimization |
| 343 | 343 |
lp.sense(lp.MIN); |
| 344 | 344 |
expected_opt=0; |
| 345 | 345 |
solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt); |
| 346 | 346 |
|
| 347 | 347 |
//Vertex (-1,0) instead of (0,0) |
| 348 | 348 |
lp.colLowerBound(x1, -LpSolver::INF); |
| 349 | 349 |
expected_opt=-1; |
| 350 | 350 |
solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt); |
| 351 | 351 |
|
| 352 | 352 |
//Erase one constraint and return to maximization |
| 353 | 353 |
lp.erase(upright); |
| 354 | 354 |
lp.sense(lp.MAX); |
| 355 | 355 |
expected_opt=LpSolver::INF; |
| 356 | 356 |
solveAndCheck(lp, LpSolver::UNBOUNDED, expected_opt); |
| 357 | 357 |
|
| 358 | 358 |
//Infeasibilty |
| 359 | 359 |
lp.addRow(x1+x2 <=-2); |
| 360 | 360 |
solveAndCheck(lp, LpSolver::INFEASIBLE, expected_opt); |
| 361 | 361 |
|
| 362 | 362 |
} |
| 363 | 363 |
|
| 364 | 364 |
template<class LP> |
| 365 | 365 |
void cloneTest() |
| 366 | 366 |
{
|
| 367 | 367 |
//Test for clone/new |
| 368 | 368 |
|
| 369 | 369 |
LP* lp = new LP(); |
| 370 | 370 |
LP* lpnew = lp->newSolver(); |
| 371 | 371 |
LP* lpclone = lp->cloneSolver(); |
| 372 | 372 |
delete lp; |
| 373 | 373 |
delete lpnew; |
| 374 | 374 |
delete lpclone; |
| 375 | 375 |
} |
| 376 | 376 |
|
| 377 | 377 |
int main() |
| 378 | 378 |
{
|
| 379 | 379 |
LpSkeleton lp_skel; |
| 380 | 380 |
lpTest(lp_skel); |
| 381 | 381 |
|
| 382 | 382 |
#ifdef HAVE_GLPK |
| 383 | 383 |
{
|
| 384 | 384 |
GlpkLp lp_glpk1,lp_glpk2; |
| 385 | 385 |
lpTest(lp_glpk1); |
| 386 | 386 |
aTest(lp_glpk2); |
| 387 | 387 |
cloneTest<GlpkLp>(); |
| 388 | 388 |
} |
| 389 | 389 |
#endif |
| 390 | 390 |
|
| 391 | 391 |
#ifdef HAVE_CPLEX |
| 392 | 392 |
try {
|
| 393 | 393 |
CplexLp lp_cplex1,lp_cplex2; |
| 394 | 394 |
lpTest(lp_cplex1); |
| 395 | 395 |
aTest(lp_cplex2); |
| 396 |
cloneTest<CplexLp>(); |
|
| 396 | 397 |
} catch (CplexEnv::LicenseError& error) {
|
| 397 | 398 |
#ifdef LEMON_FORCE_CPLEX_CHECK |
| 398 | 399 |
check(false, error.what()); |
| 399 | 400 |
#else |
| 400 | 401 |
std::cerr << error.what() << std::endl; |
| 401 | 402 |
std::cerr << "Cplex license check failed, lp check skipped" << std::endl; |
| 402 | 403 |
#endif |
| 403 | 404 |
} |
| 404 |
cloneTest<CplexLp>(); |
|
| 405 | 405 |
#endif |
| 406 | 406 |
|
| 407 | 407 |
#ifdef HAVE_SOPLEX |
| 408 | 408 |
{
|
| 409 | 409 |
SoplexLp lp_soplex1,lp_soplex2; |
| 410 | 410 |
lpTest(lp_soplex1); |
| 411 | 411 |
aTest(lp_soplex2); |
| 412 | 412 |
cloneTest<SoplexLp>(); |
| 413 | 413 |
} |
| 414 | 414 |
#endif |
| 415 | 415 |
|
| 416 | 416 |
#ifdef HAVE_CLP |
| 417 | 417 |
{
|
| 418 | 418 |
ClpLp lp_clp1,lp_clp2; |
| 419 | 419 |
lpTest(lp_clp1); |
| 420 | 420 |
aTest(lp_clp2); |
| 421 | 421 |
cloneTest<ClpLp>(); |
| 422 | 422 |
} |
| 423 | 423 |
#endif |
| 424 | 424 |
|
| 425 | 425 |
return 0; |
| 426 | 426 |
} |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 |
* Copyright (C) 2003- |
|
| 5 |
* Copyright (C) 2003-2009 |
|
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include "test_tools.h" |
| 20 | 20 |
|
| 21 | 21 |
|
| 22 | 22 |
#ifdef HAVE_CONFIG_H |
| 23 | 23 |
#include <lemon/config.h> |
| 24 | 24 |
#endif |
| 25 | 25 |
|
| 26 | 26 |
#ifdef HAVE_CPLEX |
| 27 | 27 |
#include <lemon/cplex.h> |
| 28 | 28 |
#endif |
| 29 | 29 |
|
| 30 | 30 |
#ifdef HAVE_GLPK |
| 31 | 31 |
#include <lemon/glpk.h> |
| 32 | 32 |
#endif |
| 33 | 33 |
|
| 34 | 34 |
|
| 35 | 35 |
using namespace lemon; |
| 36 | 36 |
|
| 37 | 37 |
void solveAndCheck(MipSolver& mip, MipSolver::ProblemType stat, |
| 38 | 38 |
double exp_opt) {
|
| 39 | 39 |
using std::string; |
| 40 | 40 |
|
| 41 | 41 |
mip.solve(); |
| 42 | 42 |
//int decimal,sign; |
| 43 | 43 |
std::ostringstream buf; |
| 44 | 44 |
buf << "Type should be: " << int(stat)<<" and it is "<<int(mip.type()); |
| 45 | 45 |
|
| 46 | 46 |
|
| 47 | 47 |
// itoa(stat,buf1, 10); |
| 48 | 48 |
check(mip.type()==stat, buf.str()); |
| 49 | 49 |
|
| 50 | 50 |
if (stat == MipSolver::OPTIMAL) {
|
| 51 | 51 |
std::ostringstream sbuf; |
| 52 | 52 |
buf << "Wrong optimal value: the right optimum is " << exp_opt; |
| 53 | 53 |
check(std::abs(mip.solValue()-exp_opt) < 1e-3, sbuf.str()); |
| 54 | 54 |
//+ecvt(exp_opt,2) |
| 55 | 55 |
} |
| 56 | 56 |
} |
| 57 | 57 |
|
| 58 | 58 |
void aTest(MipSolver& mip) |
| 59 | 59 |
{
|
| 60 | 60 |
//The following example is very simple |
| 61 | 61 |
|
| 62 | 62 |
|
| 63 | 63 |
typedef MipSolver::Row Row; |
| 64 | 64 |
typedef MipSolver::Col Col; |
| 65 | 65 |
|
| 66 | 66 |
|
| 67 | 67 |
|
| 68 | 68 |
Col x1 = mip.addCol(); |
| 69 | 69 |
Col x2 = mip.addCol(); |
| 70 | 70 |
|
| 71 | 71 |
|
| 72 | 72 |
//Objective function |
| 73 | 73 |
mip.obj(x1); |
| 74 | 74 |
|
| 75 | 75 |
mip.max(); |
| 76 | 76 |
|
| 77 | 77 |
|
| 78 | 78 |
//Unconstrained optimization |
| 79 | 79 |
mip.solve(); |
| 80 | 80 |
//Check it out! |
| 81 | 81 |
|
| 82 | 82 |
//Constraints |
| 83 | 83 |
mip.addRow(2*x1+x2 <=2); |
| 84 | 84 |
mip.addRow(x1-2*x2 <=0); |
| 85 | 85 |
|
| 86 | 86 |
//Nonnegativity of the variable x1 |
| 87 | 87 |
mip.colLowerBound(x1, 0); |
| 88 | 88 |
|
| 89 | 89 |
//Maximization of x1 |
| 90 | 90 |
//over the triangle with vertices (0,0),(4/5,2/5),(0,2) |
| 91 | 91 |
double expected_opt=4.0/5.0; |
| 92 | 92 |
solveAndCheck(mip, MipSolver::OPTIMAL, expected_opt); |
| 93 | 93 |
|
| 94 | 94 |
//Restrict x2 to integer |
| 95 | 95 |
mip.colType(x2,MipSolver::INTEGER); |
| 96 | 96 |
expected_opt=1.0/2.0; |
| 97 | 97 |
solveAndCheck(mip, MipSolver::OPTIMAL, expected_opt); |
| 98 | 98 |
|
| 99 | 99 |
|
| 100 | 100 |
//Restrict both to integer |
| 101 | 101 |
mip.colType(x1,MipSolver::INTEGER); |
| 102 | 102 |
expected_opt=0; |
| 103 | 103 |
solveAndCheck(mip, MipSolver::OPTIMAL, expected_opt); |
| 104 | 104 |
|
| 105 | 105 |
|
| 106 | 106 |
|
| 107 | 107 |
} |
| 108 | 108 |
|
| 109 | 109 |
template<class MIP> |
| 110 | 110 |
void cloneTest() |
| 111 | 111 |
{
|
| 112 | 112 |
|
| 113 | 113 |
MIP* mip = new MIP(); |
| 114 | 114 |
MIP* mipnew = mip->newSolver(); |
| 115 | 115 |
MIP* mipclone = mip->cloneSolver(); |
| 116 | 116 |
delete mip; |
| 117 | 117 |
delete mipnew; |
| 118 | 118 |
delete mipclone; |
| 119 | 119 |
} |
| 120 | 120 |
|
| 121 | 121 |
int main() |
| 122 | 122 |
{
|
| 123 | 123 |
|
| 124 | 124 |
#ifdef HAVE_GLPK |
| 125 | 125 |
{
|
| 126 | 126 |
GlpkMip mip1; |
| 127 | 127 |
aTest(mip1); |
| 128 | 128 |
cloneTest<GlpkMip>(); |
| 129 | 129 |
} |
| 130 | 130 |
#endif |
| 131 | 131 |
|
| 132 | 132 |
#ifdef HAVE_CPLEX |
| 133 | 133 |
try {
|
| 134 | 134 |
CplexMip mip2; |
| 135 | 135 |
aTest(mip2); |
| 136 |
cloneTest<CplexMip>(); |
|
| 136 | 137 |
} catch (CplexEnv::LicenseError& error) {
|
| 137 | 138 |
#ifdef LEMON_FORCE_CPLEX_CHECK |
| 138 | 139 |
check(false, error.what()); |
| 139 | 140 |
#else |
| 140 | 141 |
std::cerr << error.what() << std::endl; |
| 141 | 142 |
std::cerr << "Cplex license check failed, lp check skipped" << std::endl; |
| 142 | 143 |
#endif |
| 143 | 144 |
} |
| 144 |
cloneTest<CplexMip>(); |
|
| 145 | 145 |
#endif |
| 146 | 146 |
|
| 147 | 147 |
return 0; |
| 148 | 148 |
|
| 149 | 149 |
} |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 | 5 |
* Copyright (C) 2003-2009 |
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/time_measure.h> |
| 20 | 20 |
|
| 21 | 21 |
using namespace lemon; |
| 22 | 22 |
|
| 23 | 23 |
void f() |
| 24 | 24 |
{
|
| 25 | 25 |
double d=0; |
| 26 | 26 |
for(int i=0;i<1000;i++) |
| 27 | 27 |
d+=0.1; |
| 28 | 28 |
} |
| 29 | 29 |
|
| 30 | 30 |
void g() |
| 31 | 31 |
{
|
| 32 | 32 |
static Timer T; |
| 33 | 33 |
|
| 34 | 34 |
for(int i=0;i<1000;i++) |
| 35 | 35 |
TimeStamp x(T); |
| 36 | 36 |
} |
| 37 | 37 |
|
| 38 | 38 |
int main() |
| 39 | 39 |
{
|
| 40 | 40 |
Timer T; |
| 41 | 41 |
unsigned int n; |
| 42 |
for(n=0;T.realTime()< |
|
| 42 |
for(n=0;T.realTime()<0.1;n++) ; |
|
| 43 | 43 |
std::cout << T << " (" << n << " time queries)\n";
|
| 44 |
T.restart(); |
|
| 45 |
while(T.realTime()<2.0) ; |
|
| 46 |
|
|
| 44 |
|
|
| 47 | 45 |
TimeStamp full; |
| 48 | 46 |
TimeStamp t; |
| 49 |
t=runningTimeTest(f,1,&n,&full); |
|
| 47 |
t=runningTimeTest(f,0.1,&n,&full); |
|
| 50 | 48 |
std::cout << t << " (" << n << " tests)\n";
|
| 51 | 49 |
std::cout << "Total: " << full << "\n"; |
| 52 | 50 |
|
| 53 |
t=runningTimeTest(g,1,&n,&full); |
|
| 51 |
t=runningTimeTest(g,0.1,&n,&full); |
|
| 54 | 52 |
std::cout << t << " (" << n << " tests)\n";
|
| 55 | 53 |
std::cout << "Total: " << full << "\n"; |
| 56 | 54 |
|
| 57 | 55 |
return 0; |
| 58 | 56 |
} |
| 1 | 1 |
INCLUDE_DIRECTORIES( |
| 2 |
${CMAKE_SOURCE_DIR}
|
|
| 3 |
${CMAKE_BINARY_DIR}
|
|
| 2 |
${PROJECT_SOURCE_DIR}
|
|
| 3 |
${PROJECT_BINARY_DIR}
|
|
| 4 | 4 |
) |
| 5 | 5 |
|
| 6 |
LINK_DIRECTORIES(${
|
|
| 6 |
LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
|
|
| 7 | 7 |
|
| 8 | 8 |
ADD_EXECUTABLE(lgf-gen lgf-gen.cc) |
| 9 | 9 |
TARGET_LINK_LIBRARIES(lgf-gen lemon) |
| 10 | 10 |
|
| 11 | 11 |
ADD_EXECUTABLE(dimacs-to-lgf dimacs-to-lgf.cc) |
| 12 | 12 |
TARGET_LINK_LIBRARIES(dimacs-to-lgf lemon) |
| 13 | 13 |
|
| 14 | 14 |
ADD_EXECUTABLE(dimacs-solver dimacs-solver.cc) |
| 15 | 15 |
TARGET_LINK_LIBRARIES(dimacs-solver lemon) |
| 16 | 16 |
|
| 17 | 17 |
INSTALL( |
| 18 | 18 |
TARGETS lgf-gen dimacs-to-lgf dimacs-solver |
| 19 | 19 |
RUNTIME DESTINATION bin |
| 20 | 20 |
COMPONENT bin |
| 21 | 21 |
) |
| 22 | 22 |
|
| 23 | 23 |
IF(NOT WIN32) |
| 24 | 24 |
INSTALL( |
| 25 |
FILES ${CMAKE_CURRENT_SOURCE_DIR}/lemon-0.x-to-1.x.sh
|
|
| 26 |
RUNTIME DESTINATION bin |
|
| 25 |
PROGRAMS ${CMAKE_CURRENT_SOURCE_DIR}/lemon-0.x-to-1.x.sh
|
|
| 26 |
DESTINATION bin |
|
| 27 | 27 |
COMPONENT bin) |
| 28 | 28 |
ENDIF(NOT WIN32) |
| 1 | 1 |
#!/bin/bash |
| 2 | 2 |
|
| 3 | 3 |
set -e |
| 4 | 4 |
|
| 5 | 5 |
if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then |
| 6 | 6 |
echo "Usage:" |
| 7 | 7 |
echo " $0 source-file(s)" |
| 8 | 8 |
exit |
| 9 | 9 |
fi |
| 10 | 10 |
|
| 11 | 11 |
for i in $@ |
| 12 | 12 |
do |
| 13 | 13 |
echo Update $i... |
| 14 | 14 |
TMP=`mktemp` |
| 15 | 15 |
sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\ |
| 16 | 16 |
-e "s/\<undirected graphs\>/_gr_aph_label_s/g"\ |
| 17 | 17 |
-e "s/\<undirected edge\>/_ed_ge_label_/g"\ |
| 18 | 18 |
-e "s/\<undirected edges\>/_ed_ge_label_s/g"\ |
| 19 | 19 |
-e "s/\<directed graph\>/_digr_aph_label_/g"\ |
| 20 | 20 |
-e "s/\<directed graphs\>/_digr_aph_label_s/g"\ |
| 21 | 21 |
-e "s/\<directed edge\>/_ar_c_label_/g"\ |
| 22 | 22 |
-e "s/\<directed edges\>/_ar_c_label_s/g"\ |
| 23 | 23 |
-e "s/UGraph/_Gr_aph_label_/g"\ |
| 24 | 24 |
-e "s/u[Gg]raph/_gr_aph_label_/g"\ |
| 25 |
-e "s/ |
|
| 25 |
-e "s/Graph\>/_Digr_aph_label_/g"\ |
|
| 26 | 26 |
-e "s/\<graph\>/_digr_aph_label_/g"\ |
| 27 |
-e "s/ |
|
| 27 |
-e "s/Graphs\>/_Digr_aph_label_s/g"\ |
|
| 28 | 28 |
-e "s/\<graphs\>/_digr_aph_label_s/g"\ |
| 29 |
-e "s/_Graph/__Gr_aph_label_/g"\ |
|
| 30 |
-e "s/\([Gg]\)raph\([a-z_]\)/_\1r_aph_label_\2/g"\ |
|
| 29 |
-e "s/\([Gg]\)raph\([a-z]\)/_\1r_aph_label_\2/g"\ |
|
| 31 | 30 |
-e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\ |
| 32 | 31 |
-e "s/Graph/_Digr_aph_label_/g"\ |
| 33 | 32 |
-e "s/graph/_digr_aph_label_/g"\ |
| 34 | 33 |
-e "s/UEdge/_Ed_ge_label_/g"\ |
| 35 | 34 |
-e "s/u[Ee]dge/_ed_ge_label_/g"\ |
| 36 | 35 |
-e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\ |
| 37 |
-e "s/ |
|
| 36 |
-e "s/Edge\>/_Ar_c_label_/g"\ |
|
| 38 | 37 |
-e "s/\<edge\>/_ar_c_label_/g"\ |
| 39 |
-e "s/ |
|
| 38 |
-e "s/_edge\>/_ar_c_label_/g"\ |
|
| 39 |
-e "s/Edges\>/_Ar_c_label_s/g"\ |
|
| 40 | 40 |
-e "s/\<edges\>/_ar_c_label_s/g"\ |
| 41 |
-e "s/_Edge/__Ed_ge_label_/g"\ |
|
| 42 |
-e "s/Edge\([a-z_]\)/_Ed_ge_label_\1/g"\ |
|
| 43 |
-e "s/edge\([a-z_]\)/_ed_ge_label_\1/g"\ |
|
| 44 |
-e "s/\([a-z_]\)edge/\1_ed_ge_label_/g"\ |
|
| 41 |
-e "s/_edges\>/_ar_c_label_s/g"\ |
|
| 42 |
-e "s/\([Ee]\)dge\([a-z]\)/_\1d_ge_label_\2/g"\ |
|
| 43 |
-e "s/\([a-z]\)edge/\1_ed_ge_label_/g"\ |
|
| 45 | 44 |
-e "s/Edge/_Ar_c_label_/g"\ |
| 46 | 45 |
-e "s/edge/_ar_c_label_/g"\ |
| 47 | 46 |
-e "s/A[Nn]ode/_Re_d_label_/g"\ |
| 48 | 47 |
-e "s/B[Nn]ode/_Blu_e_label_/g"\ |
| 49 | 48 |
-e "s/A-[Nn]ode/_Re_d_label_/g"\ |
| 50 | 49 |
-e "s/B-[Nn]ode/_Blu_e_label_/g"\ |
| 51 | 50 |
-e "s/a[Nn]ode/_re_d_label_/g"\ |
| 52 | 51 |
-e "s/b[Nn]ode/_blu_e_label_/g"\ |
| 53 | 52 |
-e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\ |
| 54 | 53 |
-e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\ |
| 55 | 54 |
-e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\ |
| 56 | 55 |
-e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\ |
| 57 | 56 |
-e "s/_Digr_aph_label_/Digraph/g"\ |
| 58 | 57 |
-e "s/_digr_aph_label_/digraph/g"\ |
| 59 | 58 |
-e "s/_Gr_aph_label_/Graph/g"\ |
| 60 | 59 |
-e "s/_gr_aph_label_/graph/g"\ |
| 61 | 60 |
-e "s/_Ar_c_label_/Arc/g"\ |
| 62 | 61 |
-e "s/_ar_c_label_/arc/g"\ |
| 63 | 62 |
-e "s/_Ed_ge_label_/Edge/g"\ |
| 64 | 63 |
-e "s/_ed_ge_label_/edge/g"\ |
| 65 | 64 |
-e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\ |
| 66 | 65 |
-e "s/_Re_d_label_/Red/g"\ |
| 67 | 66 |
-e "s/_Blu_e_label_/Blue/g"\ |
| 68 | 67 |
-e "s/_re_d_label_/red/g"\ |
| 69 | 68 |
-e "s/_blu_e_label_/blue/g"\ |
| 70 | 69 |
-e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\ |
| 71 | 70 |
-e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\ |
| 72 | 71 |
-e "s/DigraphToEps/GraphToEps/g"\ |
| 73 | 72 |
-e "s/digraphToEps/graphToEps/g"\ |
| 74 | 73 |
-e "s/\<DefPredMap\>/SetPredMap/g"\ |
| 75 | 74 |
-e "s/\<DefDistMap\>/SetDistMap/g"\ |
| 76 | 75 |
-e "s/\<DefReachedMap\>/SetReachedMap/g"\ |
| 77 | 76 |
-e "s/\<DefProcessedMap\>/SetProcessedMap/g"\ |
| 78 | 77 |
-e "s/\<DefHeap\>/SetHeap/g"\ |
| 79 | 78 |
-e "s/\<DefStandardHeap\>/SetStandradHeap/g"\ |
| 80 | 79 |
-e "s/\<DefOperationTraits\>/SetOperationTraits/g"\ |
| 81 | 80 |
-e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\ |
| 82 | 81 |
-e "s/\<copyGraph\>/graphCopy/g"\ |
| 83 | 82 |
-e "s/\<copyDigraph\>/digraphCopy/g"\ |
| 84 | 83 |
-e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\ |
| 85 | 84 |
-e "s/\<IntegerMap\>/RangeMap/g"\ |
| 86 | 85 |
-e "s/\<integerMap\>/rangeMap/g"\ |
| 87 | 86 |
-e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\ |
| 88 | 87 |
-e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\ |
| 89 | 88 |
-e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\ |
| 90 | 89 |
-e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\ |
| 91 | 90 |
-e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\ |
| 92 | 91 |
-e "s/\<storeBoolMap\>/loggerBoolMap/g"\ |
| 93 | 92 |
-e "s/\<BoundingBox\>/Box/g"\ |
| 94 | 93 |
-e "s/\<readNauty\>/readNautyGraph/g"\ |
| 95 | 94 |
-e "s/\<RevDigraphAdaptor\>/ReverseDigraph/g"\ |
| 96 | 95 |
-e "s/\<revDigraphAdaptor\>/reverseDigraph/g"\ |
| 97 | 96 |
-e "s/\<SubDigraphAdaptor\>/SubDigraph/g"\ |
| 98 | 97 |
-e "s/\<subDigraphAdaptor\>/subDigraph/g"\ |
| 99 | 98 |
-e "s/\<SubGraphAdaptor\>/SubGraph/g"\ |
| 100 | 99 |
-e "s/\<subGraphAdaptor\>/subGraph/g"\ |
| 101 | 100 |
-e "s/\<NodeSubDigraphAdaptor\>/FilterNodes/g"\ |
| 102 | 101 |
-e "s/\<nodeSubDigraphAdaptor\>/filterNodes/g"\ |
| 103 | 102 |
-e "s/\<ArcSubDigraphAdaptor\>/FilterArcs/g"\ |
| 104 | 103 |
-e "s/\<arcSubDigraphAdaptor\>/filterArcs/g"\ |
| 105 | 104 |
-e "s/\<UndirDigraphAdaptor\>/Undirector/g"\ |
| 106 | 105 |
-e "s/\<undirDigraphAdaptor\>/undirector/g"\ |
| 107 | 106 |
-e "s/\<ResDigraphAdaptor\>/ResidualDigraph/g"\ |
| 108 | 107 |
-e "s/\<resDigraphAdaptor\>/residualDigraph/g"\ |
| 109 | 108 |
-e "s/\<SplitDigraphAdaptor\>/SplitNodes/g"\ |
| 110 | 109 |
-e "s/\<splitDigraphAdaptor\>/splitNodes/g"\ |
| 111 | 110 |
-e "s/\<SubGraphAdaptor\>/SubGraph/g"\ |
| 112 | 111 |
-e "s/\<subGraphAdaptor\>/subGraph/g"\ |
| 113 | 112 |
-e "s/\<NodeSubGraphAdaptor\>/FilterNodes/g"\ |
| 114 | 113 |
-e "s/\<nodeSubGraphAdaptor\>/filterNodes/g"\ |
| 115 | 114 |
-e "s/\<ArcSubGraphAdaptor\>/FilterEdges/g"\ |
| 116 | 115 |
-e "s/\<arcSubGraphAdaptor\>/filterEdges/g"\ |
| 117 | 116 |
-e "s/\<DirGraphAdaptor\>/Orienter/g"\ |
| 118 | 117 |
-e "s/\<dirGraphAdaptor\>/orienter/g"\ |
| 118 |
-e "s/\<LpCplex\>/CplexLp/g"\ |
|
| 119 |
-e "s/\<MipCplex\>/CplexMip/g"\ |
|
| 120 |
-e "s/\<LpGlpk\>/GlpkLp/g"\ |
|
| 121 |
-e "s/\<MipGlpk\>/GlpkMip/g"\ |
|
| 122 |
-e "s/\<LpSoplex\>/SoplexLp/g"\ |
|
| 119 | 123 |
<$i > $TMP |
| 120 | 124 |
mv $TMP $i |
| 121 | 125 |
done |
0 comments (0 inline)