Summary

We covered the following topics in this tutorial:

  • Basic IP in Java, good Java style
  • Callbacks to improve solver

    Callback Name

    Description

    LazyConstraintCallback

    Check integer solutions for violated constraints.

    UserCutCallback

    Check fractional solutions for violated valid inequalities.

    HeuristicCallback

    Use a user heuristic to convert fractional solutions into integer solutions.

    IncumbentCallback

    Monitor new incumbent integer solutions.
  • A methodology for solving tough IPs. With every feature added:
    • Implementation
      • Independent from existing code
      • Toggled on and off programatically
    • Test
    • Profile
      • Assess feature effectiveness
      • Determine new bottleneck

We used TSP a working example, and used the following somewhat elementary algorithmic techniques:

  • Polynomial time separation over the cutset polytope via max flow min cut
  • Solution construction via Christofides and a Christofides based heuristic
  • Solution improvement via two-opt

Future Directions

The first step taken should be to identify more valid inequalities that can be quickly separated over. The literature on this topic is vast.

  • Here provides a unified view of many classes of valid inequalities for TSP using lifting
  • Here provides a simple LP duality argument to compare various classes of valid inequalities for TSP. The paper also provides a good number of references on classes of valid inequalities and separation.

Here are a few more ideas:

  • Integrate two-opt with either cuts or branching, as once we have run two-opt on some tour , we know all future solutions will satisfy \[ \sum_{e \in E \setminus T} x_e \geq 2 \]
  • Use a "very large neighborhood search," a local search that checks an exponentially large neighborhood in polynomial time with an efficient algorithm see section 4 here.
  • Implement a more traditional improvement on two-opt, the Lin–Kernighan heuristic, as described both in the paper above and here.
  • Improve the efficiently of separating over the cutset constraints as previously described
  • Use better construction heuristics. For example, given a set of edges (with no cycles or nodes with degree above two), the problem of finding the optimal tour using all of these edges can be written as a small ATSP (with one node for each connected component in the subgraph using only the suggested edges). Since ATSP can be solved by solving a TSP that is twice as large, we can bootstrap our tour construction. Fixing a set of variables to be one and then solving the restricted problem is actually a general technique called diving, just in our special case, the diving has a special form.
  • Use parallelization (multithreading). Two options:
    • Within a callback
    • The CPLEX Solver

      Warning

      While CPLEX by default supports multithreading, it is automatically turned off when you use Control Callbacks. You can turn it back on, but first you must ensure that the code in your callbacks is "thread safe," meaning that if two threads are running at the same time and both enter a particular callback, they won't try and concurrently modify any state we maintain. For example:

      • In our incumbent callback, we maintain a queue of solutions waiting to be read in heuristic callback
      • In our user cut callback, we maintain a counter in the "Back Off Function" indicating how many more nodes we need to process until we attempt to separate again
      • Likewise for our heuristic callback
      • In our random user cut callback, we have a random number generator, which presumably maintains some state and thus will not be thread safe.
  • Distributed Computing (multiple compueters), next class!

Callback Caution

As we have already seen when applying two-opt to integer solutions generated by CPLEX heuristics, often CPLEX has already implemented some functionality we would want to accomplish with a Callback. This is particularly true with generating various classes of cuts or special branching instructions. Often, you can just instruct CPLEX to increase emphasis on something without writing a special callback. You should do this whenever possible, as it will reduce the chance of user error and likely be faster.

Complete Solutions

If something went wrong, you can download the complete solutions here!

  • No labels