Home

Basic Features - Lehigh University

1. The SYMPHONY Framework for Mixed Integer Linear Programming Basic Features TED RALPHS ISE Department OR COR L Lab C L Lehigh University COME PUTATIONAL OPTIMIZATION tkralphs lehigh edu DIMACS Workshop on COIN OR July 19 2006 T K Ralphs SYMPHONY Outline Introduction 9 Overview e Downloading e Building Q The SYMPHONY Black Box Solver Interactive Shell e Command Line Q The SYMPHONY Callable Library e Linking with the Library Using the C Callable Library Using the OSI Interface Q Example e The Matching Problem Thanks to Mike Trick 9 A Basic Solver T K Ralphs SYMPHONY Introduction 5 Overview Brief Overview of SYMPHONY SYMPHONY is an open source software package for solving and analyzing mixed integer linear programs MILPs SYMPHONY can be used in three distinct modes e Black box solver From the command line or shell e Callable library From a C C code e Framework Develop a customized solver or callable library Advanced features e Warm starting e Sensitivity analysis e Bicriteria solve e Parallel execution T K Ralphs SYMPHONY Introduction z Overview Basic Algorithm Core solution methodology is Default search strategy is a hybrid depth first best first strategy Default branching scheme is strong branching Uses two of Cbc s simple primal heuristics to generate new solutions Cuts can be gener
2. The SYMPHONY Directory Applications Other Directories 9 CNRP 9 Common 9 Datasets 9 MATCH 9 CutGen 9 Examples 9 MCKP 9 CutPool 9 include 9 MPP LP 9 scripts 9 SPP 9 Master 9 SPP CUTS 9 TreeManager 9 USER 9 WIN32 9 VRP T K Ralphs SYMPHONY Introduction Building Building the Default Solver and Library e SYMPHONY does not yet build with the GNU autotools soon Building in Unix Linux CYGWIN MinGW The following commands should build everything on most architectures configure make make install cd SYMPHONY make e The result will be the symphony sequential executable and the callable library libsym x To customize the build process edit the SyMPHONY config file see next slide T K Ralphs SYMPHONY Introduction Overview Downloading Building Customizing the Configuration Configuration Variables er i Architecture detected automatically 9 N If other than c SYMPHONY LIBTYPE SHARED or STAT LP SOL pom Osi solver e INE TRUE Or FALSE eU E Or FALSE COMM PROTOCOL NONE or P 9 cc Compiler name 9 OI level SYM Which modules to compile together SENSITIVITY ANALYSIS TRUE FALSE T K Ralphs SYMPHONY Building Using an IDE in Windows e MSVC 6 0 e Open the workspace file SYMPHONY WIN32 symphony dsw e Build other COIN libraries a
3. for i 0 i lt m LFE saecu 1 1 sym_explicit_load_problem env n m matbeg matind matval lb ub is int obj 0 sense rhs rngval true return FUNCTION TERMINATED NORMALLY PHONY T K Ralphs A Basic Solver Example The Main Function Here we put it all together to get a basic solver int main int argc char argv int termcode char infile Create a SYMPHONY environment sym environment xenv sym open environment Create the data structure for storing the problem instance user problem prob user problem calloc 1 sizeof user problem CALL FUNCTION sym set user data env void prob CALL FUNCTION sym parse command line env argc argv CALL FUNCTION sym get str param env infile name amp infile CALL FUNCTION match read data prob infile CALL FUNCTION match load problem env prob CALL FUNCTION sym solve env CALL FUNCTION sym close environment env return 0 In the talk on advanced features we will show how to customize the solver with callbacks T K Ralphs
4. user problem prob int i j index n m nz matbeg matind double matval lb ub obj rhs rngval char sense is int set up the initial LP data n prob gt numnodes prob numnodes 1 2 m 2 prob numnodes nz 2 n Allocate the arrays matbeg int malloc n 1 ISIZE matind int malloc nz ISIZE matval double malloc nz DSIZE obj double malloc n DSIZE 15 double calloc n DSIZE ub double malloc n DSIZE rhs double malloc m DSIZE sense char malloc m CSIZE rngval double calloc m DSIZE is_int char malloc n CSIZE T K Ralphs PHONY he Matching Problem A Basic Solver Example Constructing the Problem Description Here we construct the problem description and load it for i i lt prob numnodes i for j itl j lt prob gt numnodes j prob matchl index i The first component of assignment index prob gt match2 index j The second component of assignment index prob index i j prob index j i index To recover the index later obj index prob cost i j Cost of assignment i j is int index TRUE matbeg index 2 index t matval 2 index matval 2 index 1 1 matind 2 index matind 2 index 1 ub index 1 0 index i EE matbeg n 2 n
5. NY OSI Interface e The COIN OR Open Solver Interface is a standard C class for accessing solvers for mathematical programs Each solver has its own derived class that translates OSI calls into those of the solver s library e For each method in OSI SYMPHONY has a corresponding method e The OSI interface is implemented as wrapped C calls e The constructor calls sym open environment the destructor calls sym c1os ironment e The OSI initialSolve method calls sym_solve e The OSI ve method calls s resolve To use the SPD OSI interface make the SYMPHONY OSI library T K Ralphs SYMPHONY The SYMPHONY Callable Library Using TA EE Implementation with the OSI Interface Below is the implementation of a simple solver using the SYMPHONY OSI interface Again the code is the same for any configuration or architecture sequential or parallel include OsiSolverInterface hpp include OsiSymSolverInterface hpp int main int argc char OsiSymSolverInterface si si parseCommandLine argc argv si loadProblem si branchAndBound T K Ralphs SYMPHONY The Matching Problem Thanks to Mike Trick Solving the Matching Problem Given an undirected graph G V E the Matching Problem is that of selecting a minimum weight set of disjoint edges e The problem can be formulated as follows The Matching Problem min xD CoXe e
6. ated using the Cut Generator Library e Clique e Odd Hole e Flow Cover e Probing e Gomory e Simple Rounding e Knapsack Cover e Reduce and Split e Lift and Project e Two slope MIR e Mixed Integer Rounding T K Ralphs SYMPHONY Introduction Overview anic ing Basic Design To enable parallel execution SYMPHONY is functionally divided into five independent modules that communicate through shared or distributed memory SYMPHONY Modules 9 Maintains static data between solves spawns parallel processes performs I O 9 TM Controls overall execution by tracking growth of the tree and dispatching subproblems to the LP solvers 9 NP Perform processing and branching operations CG Generates cuts 9 CP Acts as an auxiliary cut generator by maintaining a list of the most effective cuts found so far T K Ralphs SYMPHONY Introduction 7 Overview Downloading Building SYMPHONY Configurations Each module can be compiled as an independent executable for parallel execution e The modules can also be combined any number of different ways to yield other parallel configurations If all modules are combined together we get either e A with a standard compiler e A with an OpenMP aware compiler e The most common is to have two executables e Combined NP CG executable e Combined Master TM CP executable Storing and distributing generated data subproble
7. cE Xe 1 VieV 1 jJEV e ij EE 2 X 2 Ve E 9 x is a binary variable that takes value 1 if edge e is selected and 0 otherwise T K Ralphs SYMPHONY A Basic Solver First we need a data structure for storing the problem data User Data for Matching Solver typedef struct MATCH int numnodes int cost MAXNODES MAXNODES int endpointl1 MAXNODES x MAXNODES 1 2 2 int endpoint2 MAXNODES MAXNODES 1 2 int index MAXNODES MAXNODES jmatch data T K Ralphs SYMPHONY A Basic Solver Example Reading in the Data Next we need to read in the data int match_read_data user_problem prob char infile Mine i j FILE f NULL if f fopen infile r NULL printf match read data user file s can t be opened n infile return ERROR USER Read in the costs fscanf f d amp prob gt numnodes for 8 i lt prob numnodes 1 for j 0 lt prob numnodes fscanf f d amp gt i 3 return FUNCTION TERMINATED NORMALLY Note that this could be implemented within a callback but it is unnecessary T K Ralphs A Basic Solver Example Setting up Arrays Finally we load the problem Here we are declaring the arrays int match load problem sym environment env
8. ere is a sample Makefile in the Examples directory MSVC Library is in the SYMPHONY WIN32 Debug directory To link just add the symphony library to your project T K Ralphs SYMPHONY Linking with the Library Using the C Callable Library Using the OSI Interface The SYMPHONY Callable Library T K Ralphs SYMPHONY The SYMPHONY Callable Library API Overview cont iliary subroutines Accessing and modifying problem data e sym set xxx 9 sym xxx Accessing and modifying parameters sym set xxx param sym get Xxx param Accessing results and solver status sym get sol solution sym get obj val Advanced functions T K Ralphs SYMPHONY inking witt brary Using the C Callable Library The SYMPHONY Callable Library Implementing a Basic MILP Solver We only need a few lines to implement a basic solver e The default command line parser can be invoked The code is exactly the same for all architectures even parallel e Command line would be symphony F model mps include symphony_api h int main int argc char sym environment env sym_open_environment sym_parse_command_line env argc argv sym_load_problem env sym solve env sym close environment env T K Ralphs SYMPHONY Linking with the Library Using the C Callable Library The SYMPHONY Callable Library Using the OSI Interface The SYMPHO
9. m descriptions and cuts T K Ralphs SYMPHONY Overview vnic What s Available Packaged releases from www branchandcut org old e Current source at SVN on projects coin or org An extensive user s manual on line and in PDF 9 A tutorial illustrating the development of a custom solver e Configuration and compilation files e Examples and Applications SYMPHONY Solvers T K Ralphs SYMPHONY Introduction Downloading ildi Downloading SYMPHONY e Download packaged source releases from www branchandcut org out of date e Download a source tarball from www coin or org Tarballs e Download source using SVN e Windows GUI Use TortoiseSVN e Unix Linux CYGWIN MinGW Use svn from the command line https projects coin or org svn SYMPHONY e Pre compiled binaries coming soon Note that you may also consider checking out herpe e The rest of this presentation is based on the current version SYMPHONY 5 1 T K Ralphs SYMPHONY Introduction Downloading Top Level Directory Structure After checking out the code or unpacking the archive you should see the following at the top level Directories eie Clp CoinUtils Og SYMPHONY configure script and other related files This also applies if you check out CoinAl11 except that there will be additional top level directories T K Ralphs SYMPHONY Downloading
10. nd set the paths to them e Build the symphony project e Eclipse e Install CYGWIN or MinGW e Download and build the code as above e Create an Eclipse Project e Dev C T K Ralphs SYMPHONY Building Using an IDE in Linux Linux IDEs e Eclipse e Download and build the code as above e Create an Eclipse Project e KDevelop T K Ralphs SYMPHONY The SYMPHONY Black Box Solver Interactive Shell Using the Interactive Shell Woody COIN SYMPHONY gt bin CYGWIN OSI_CLP symphony exe OK KK CK EK CK CK CK ICI E ICICI ICICI ICICI ISIC I ICI ok A ae This is SYMPHONY Version 5 lalpha Copyright 2000 2005 Ted Ralphs All Rights Reserved Distributed under the Common Public License 1 0 FOCI IG ICI ICI I ISI II ISI ICI II IG IOI TC IOI TOI III IIA x WELCOME TO SYMPHONY INTERACTIVE MIP SOLVER xxx Please type help to see the main commands SYMPHONY help List of main commands load read a problem in mps or ampl format solve solve the problem lpsolve solve the lp relaxation of the problem set set a parameter display display optimization results and stats reset restart the optimizer help show the available commands params options quit exit leave the optimizer SYMPHONY load Datasets sample mps T K Ralphs Introduction The SYMPHONY Black Box Solver J The SYMPHONY Ca ry Command Li
11. ne Calling from the Command Line e Read and solve a model in MPS format Linux Unix CYGWIN MinGW Shell SYMPHONY bin ARCH LP SOLVER symphony F Datasets sample mps DOS Shell SYMPHONY WIN32 Debug symphony exe F Datasets sample mps e Read and solve a model in GMPL AMPL format Linux Unix CYGWIN MinGW Shell SYMPHONY bin ARCH LP SOLVER symphony F Datasets sample mod D Datasets sample dat DOS Shell SYMPHONY WIN32 Debug symphony exe F Datasets sample mod D Datasets sample dat T K Ralphs SYMPHONY Intro on The SYMPHONY Black Box I The SYM Y Callat SYM Command Line Setting Parameters e Command line parameters are set Unix style to get a list invoke SYMPHONY with n symphony t 1800 v 3 u 100 F sample mps To set other parameters specify a parameter file with par patr e The lines of the parameter file are pairs of keys and values Parameters are listed in the user s manual Example Parameter File time limit 1800 strong branching cand num max 5 max presolve iter 50 T K Ralphs SYMPHONY The SYMPHONY E The SYMPHONY Linking with the Library ing the llable Libra Linking to the Callable Library The SYMPHONY library is built along with the executable Unix Linux CYWIN MinGW e Library is in the SYMPHONY 1ib ARCH LP SOLVI e To link to it just include 1 PATE an time ER directory d 1 sym at link e Th

Basic Features - Lehigh University

Contents

Download Pdf Manuals

Related Search

Related Contents