### Solving a TSP using lazy constraints

The 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.

First solution with subtours for instance ch130.

The problem with the SECs is that the number of these constraints is exponential in the number of cities. For a TSP with 50 cities the number of SECs exceeds $10^{15}$. Generating all SECs is therefore impossible.

Fortunately, we can use SECs as lazy constraints. Unlike normal constraints, lazy constraints are not generated upfront. Instead, they are only generated when needed. Typically lazy constraints are unlikely to be violated. In a TSP with 50 cities usually at most 100 SECs will be “active” which is only a fraction of the total number of SECs. Lazy constraints are supported by CPLEX and Gurobi.

The new AIMMS example TSP, which can be found on the examples page on the AIMMS website, uses the above formulation. The SECs are added as lazy constraints inside a callback. This callback is called whenever the solver finds a new candidate incumbent solution, i.e., a solution that satisfies formulation (1) plus the SECs that have been added before as lazy constraints. The callback procedure checks whether the candidate solution forms one tour. If it does, the solver found a true solution for the TSP and the solution is accepted; otherwise a SEC is added for each subtour. Finding a violated SEC, the so-called separation problem, can be solved in polynomial time despite the exponential number of SECs. The separation algorithm implemented in this example (inside the procedure DetermineSubtours) has a worst-case running time of $O(n^2)$.

The example comes with several symmetric instances from TSPLIB. More information on the TSP can be found on this very nice page maintained by William Cook.

Remark: SECs are often used as cutting planes in a branch-and-cut algorithm. In that case the separation problem is more difficult as it is applied to a fractional x. Currently its fastest separation algorithm has a worst-case running time of $O(nm + n^2 \log n)$ where m denotes the number of nonzero x in the fractional solution. In our case, using SECs as lazy constraints, the separation problem is applied to a binary x. Although the separation problem becomes easier if SECs are used as lazy constraints, it does not mean that TSPs are solved more efficiently that way.

This entry was posted in Advanced, Modeling .

### Progress Window Updating Changes

The progress window, which can be opened by pressing CTRL-P, allows you to monitor AIMMS during compilation, execution and solving. For example, while solving a MIP problem, AIMMS will display the number of iterations and nodes, the best bound and the best solution in the progress window. So far, progress updates during a solve have been based on the number of iterations used by the solver. By default, the progress window is updated every 100 iterations. This frequency is controlled by the general solvers option Progress Solution.

This entry was posted in Intermediate .

### How to protect the Intellectual Property in your AIMMS 4 model

Encryption is typically used to protect the intellectual property (IP) in your AIMMS model and libraries. Access to your application can also be restricted in both AIMMS 3 and AIMMS 4; though the methods differ between the two AIMMS versions.

In AIMMS 3, you had the option to encrypt your project in such a way that it was always stored encrypted, even during development. The benefit is that you could send everything you had to an end-user and you didn’t have to worry about them getting access to the source. Alternatively, you could send them just one or two encrypted libraries. Of course, the disadvantage in AIMMS 3 is that you had no option to do code comparison and/or version control.

As of AIMMS 4, all project sources are text-based. This allows you to use version control software. As a result, the model is no longer stored encrypted and explicit steps are needed to create encrypted code.

This blog posts illustrates how you can create an encrypted project out of the source. The steps required to create an encrypted library will be discussed here as well.

This entry was posted in AIMMS, Technical .

### Under control: managing errors and warnings within AIMMS

The goal of this article is to explain how you can control errors and warnings within AIMMS. Namely, we will walk you through some useful tips that can help you manage errors and warnings in the best possible way to create better models.

This entry was posted in Beginner, Modeling .

### Professionally Operating Your AIMMS PRO Platform

AIMMS started life as a desktop product. Users were mostly individually responsible for looking after their applications, managing the changes, making back-ups, etc. Unwanted incidents such as bugs, accidental project deletion and hardware failures usually had a very limited local impact. Of course mission-critical AIMMS applications were already managed more rigorously.

The advent of AIMMS PRO is introducing new application management challenges as many more users and/or business operations potentially depend on a single PRO platform for performing their tasks. We see our clients looking for ways to professionally operating their PRO platforms. Purpose of this blog post is to provide you with some aspects to consider in this context. We are not proposing anything novel, but merely pointing out some common practices of application management. Continue reading »

This entry was posted in AIMMS .

### Installing 32-bit and 64-bit Microsoft Access Drivers next to each other

Some years ago, before Microsoft Office 2010, life was – in some sense – easier for developers: Office was 32-bit, period. In our days, since the release of Microsoft Office 2010, things are a bit more complicated, as users can now have a machine with a 64-bit native version of Office installed as well. This means, for instance, that a 32-bit application using an ODBC driver to connect to an Access database might not work anymore, since the 32-bit ODBC driver might not exist on a machine with a 64-bit Office installation. In such a case, even though the user has a valid Office installation on his or her machine, the application may still display an error regarding the installation or the registration of the proper drivers on the local machine. Continue reading »

This entry was posted in Intermediate, Technical .

### Investigating infeasible nonlinear problems

The AIMMS webinar of August (2014) dealt with “Analyzing infeasible Problems in AIMMS”. In case you missed it, the recording can be found here. As shown in the webinar, one way to investigate an infeasible problem is by calculating an Irreducibly Inconsistent System (IIS). An IIS is a subset of all constraints and variables that contains an infeasibility. The “Irreducibly” part implies that the subset is as small as possible. Unfortunately, the IIS could only be calculated for linear (and quadratic) problems. So how about nonlinear problems?

AIMMS 4.1 introduces version 14 of BARON. BARON is a solver for solving non-convex optimization problems to global optimality. Version 14 can calculate an IIS for infeasible nonlinear problems including problems with integer variables. To let BARON calculate an IIS, the option Compute IIS should be switched on. BARON offers several algorithms for calculating an IIS, the fastest being a heuristic that “only” calculates an IS (as the infeasible system found could possibly be reduced further). BARON 14 also brings significant improvements in the handling of integer problems. Note that finding a global optimum takes more time than finding a local optimum like most nonlinear solvers do.

Another way to analyze an infeasible problem is by using the Display Infeasibility Analysis option of the AIMMS presolver. This also prints an infeasible set of constraints and variables. In previous versions of AIMMS this set could contain superfluous constraints and variables, but AIMMS 4.1 uses an algorithm to calculate an (almost) irreducible set. Note that the AIMMS presolver cannot always detect that an infeasible problem is indeed infeasible.

Both the Infeasibility Analysis and the IIS, as calculated by BARON, are printed in the listing file.

This entry was posted in Intermediate .

### AIMMS 4: model sources, version control and aimmspack files

In our current AIMMS 4.0 release we have introduced a number of fundamental, and sometimes breaking changes in managing the project sources, about which we got a lot of questions. In this blog post, I will describe these changes and also explain the rationale behind them.

## Binary versus text-only source files

In AIMMS 3, all project sources were stored in a binary format. Originally, we introduced these binary files in AIMMS 3 to reduce the total number of files associated with a project. However, over time it turned out that a major drawback of this approach was that the binary format made it very hard to effectively collaborate on an AIMMS 3 project, because the binary files make it really cumbersome to combine the changes made by multiple developers into a new version of the project. For many years, our larger customers have asked us to address this problem, and we partially mitigated it by introducing libraries in AIMMS 3. This allowed multiple developers to work on separate libraries, thus facilitating a limited form of collaboration. Continue reading »

This entry was posted in AIMMS, Intermediate, Technical .

### Formulas as Data

A mathematical formula is considered data within an application when it is read in as a string during the application’s runtime, and subsequently used in the construction of selected assignments and constraints. The concept “Formulas as Data” can be applied to several optimization apps, for instance those that deal with “Blending on Specification” and “Asset Management.” In these types of applications, the benefit of the end-users is that they do not have to share these formulas with anyone else, including the developers of the apps. For such apps, good formulas are expensive to develop and having good formulas provides a competitive edge to these end-users. In AIMMS, formulas can be used in the following way:

• String parameters – a formula is a sequence of characters, and such sequences can be stored and manipulated via string parameters. Such manipulation is executed at AIMMS run time.
• Macros – a formula is a mathematical expression and this expression is created during AIMMS compilation time.

The two identifier types, string parameter and macro, effective at different times as far as the AIMMS system is concerned, need to be combined in order to support the concept “Formulas as Data.” How do we go about this? Continue reading »

This entry was posted in Uncategorized .

### Repetitive Patterns captured by Model Query and Model Edit Functions

Der Maler – Honoré Daumier – from Rheims Museum of Fine Arts

When constructing AIMMS models, we are usually able to handle repetition and structure by adding indexes. For instance, if we have built a model for the conversion process of a single machine, we do not have to duplicate the relevant model code when given an extra machine. Instead, we can use an extra index over a set of machines. However, there are situations where adding an extra index is not an option. This blog post will provide an example of such a situation, illustrating how the issue can be tackled using the AIMMS Model Query and Model Edit functions. Continue reading »

This entry was posted in Intermediate, Technical .