Category archives: Advanced
Solving a TSP using lazy constraints
Posted on May 26, 2015 by Marcel HuntingLeave a replyThe famous travelling salesman problem (TSP) deals with the following problem: given a list of cities and the distances between each pair of cities, a salesman has to find the shortest possible route to visit each city exactly once while returning to the origin city. One way to formulate the TSP is as follows:
min sum( (i,j), c(i,j)*x(i,j) )
(1) s.t. sum( i, x(i,j) + x(j,i) ) = 1 for all j
x(i,j) binary for all i > j
Here x(i,j) equals 1 if the route from city i to city j is in the tour, and 0 otherwise. Note that this is the formulation for the symmetric TSP in which the distance from i to j equals the distance from j to i. This formulation is not complete as it allows for subtours. One way to exclude these subtours is by using subtour elimination constraints (SECs for short):
sum( (i,j) | i in S and not j in S, x(i,j) + x(j,i) ) >= 2 for all S, 1 < |S| < n
Here S is a subset of cities while n denotes the number of cities. This SEC enforces that at least one route is going from a city in set S to a city outside S.
Share this:
Monitoring identifiers for changes
Posted on April 10, 2013 by Guido DiepenLeave a reply
Whenever you changed the values of some identifiers and close your AIMMS project, the default behavior of AIMMS is that it will ask you whether you want to save the unchanged data. This behavior depends on which data categories and case type are currently active.
There can be situations where it is useful to not have this check based on a case type / data category, but just check whether a give subset of all identifiers in your model have been changed since the last time you checked. With AIMMS 3.12, we have introduced the data change monitor functionality which allows you to achieve exactly this.
Share this:
Automatic Benders’ decomposition: AIMMS beta version available
Posted on January 08, 2013 by Marcel HuntingLeave a replyBenders’ decomposition is an approach to solve complicated mathematical programming problems by splitting them into two, and thereby simplifying the solution process by (repeatedly) solving one master problem and one subproblem. If the problem contains integer variables then typically they become part of the master problem while the continuous variables become part of the subproblem. The classic approach of the Benders’ decomposition algorithm solves an alternating sequence of master problems and subproblems. Benders’ decomposition is mostly used for solving difficult MIP problems and stochastic programming problems.
We have developed a generic Benders’ decomposition module in AIMMS that is easy to use. A beta version of AIMMS 3.13 with Benders’ decomposition is now available for downloading. If you are interested to try it then we invite you to send an e-mail to our support.
Share this:
ROGO solver using constraint programming
Posted on December 18, 2012 by Chris KuipLeave a reply
The ROGO puzzle, rogopuzzle.co.nz, challenges players to find a good path on a board, pick up treasures, and avoid pitfalls. This puzzle, and its corresponding iPhone app, were originally developed in New Zealand. In this post, I’ll explain a method for solving ROGO puzzles using constraint programming in AIMMS.
Intro 6
Solution animated
Share this:
Scheduling for project planning
Posted on November 29, 2012 by Chris KuipLeave a reply
Golden Gate bridge taken by Guido Diepen
The identifier types ACTIVITIES and RESOURCES, and the scheduling intrinsic functions as part of the AIMMS constraint programming component are very useful in modeling construction projects and optimizing the makespan of those projects.
Several existing constraint programming languages use the Bridge Building example in the Ph.D Thesis of the late M. Bartusch to illustrate this, see for instance Oz and SAS.
Share this:
Get top n set elements for some criteria
Posted on October 12, 2012 by Guido DiepenLeave a reply
Top 3
Sometimes, you are not interested in just the first or last element, but in the first couple of elements of a set (based on some sort of order). Another set related function, that is less known, is the NBest operator in AIMMS. This operator allows you to achieve just this, namely obtain the first n elements of a set based on some sort criteria, which must be provided to the NBest operator as an additional argument.
Share this:
Local Binding vs. Default Binding
Posted on September 13, 2012 by Deanne ZhangLeave a reply
Assume there are two sets:
SET: identifier : RootSet index : i |
and
SET: identifier : MySubSet subset of : RootSet |
What is the difference between expression ( i in MySubSet ) and ( i | i in MySubSet ) ?
Share this:
Connect to Access database file via ODBC connection string
Posted on August 28, 2012 by Guido DiepenLeave a reply
Microsoft Access databases
For a long time, AIMMS already has the possibility to retrieve/store data from/into any ODBC or OLEDB datasource. Originally, you could provide a UDL file (in case of OLEDB) or a System/User/File DSN (in case of ODBC).
In case you deploy a project where the user of the project can actually choose which specific Access database file should be used, you either would have to generate the .dsn files based on this choice, or let the user choose the specific Access database file via the file selection wizards of the ODBC driver.
Since AIMMS 3.11, another possibility was introduced, namely generating the connection string within AIMMS itself. You could then base this connection string on some file that the end-user had selected. One very big advantage of creating such a connection string instead of using DSN files is that you don’t have to include the database password in the plain-text DSN file if your database requires a password: you can keep this password hidden in the code of your project.
These connection strings can be used in the Data Source attributes of all the database related identifiers AIMMS (e.g. tables, database procedures).
Share this:
Lazy Outer Approximation
Posted on August 20, 2012 by Marcel HuntingLeave a replyA somewhat hidden functionality in AIMMS is the implementation of the Quesada and Grossmann algorithm for solving convex Mixed Integer Nonlinear Programming (MINLP) problems. For AIMMS 3.13 the implementation of this algorithm will use the lazy constraint callback function that was introduced in CPLEX 12.3 and Gurobi 5.0, and has several advantages over the old implementation:
Share this:
Get platform/architecture information in AIMMS
Posted on July 28, 2012 by Guido DiepenLeave a reply
Get information about platform/architecture
In certain cases, as an AIMMS developer it is very useful to know details about the AIMMS version that is currently used for your project like:
- Is the project running under Linux or under Windows?
- Is the project running in 64 bit AIMMS or in 32 bit AIMMS?
- Is the project running in ASCII AIMMS or in Unicode AIMMS?
These details are especially useful if you are using external procedures in your project because you can’t use a 32 bit compiled DLL when running a 64 bit version of AIMMS.
