A Matrix Puzzle

A question on Mathematics Stack Exchange, "Placing number blocks so that the resulting matrix is symmetric", revolves around a square matrix whose entries are partitioned into blocks (submatrices). The submatrices need to be rearranged so that the resulting matrix is symmetric around its main diagonal. The author of the question asked if it were possible to do this using linear programming. I think the answer is no, but we can certainly do it with either an integer linear program or a constraint program. The author posts two examples ($4\times 4$ and $5\times 5$). I cobbled together Java code for a MIP model (using CPLEX) and a CP model (using CP Optimizer) and had no trouble solving both problems.

There are a couple of generalizations worth noting. First, while the example matrices contain integers, there is nothing preventing the two models from being used with other content types (real numbers, complex numbers, text). Some variable definitions would need modification, but conceptually both methods would work. Second, the author of the post used only one-dimensional blocks (row vectors or column vectors), but my code allows for arbitrary rectangular blocks. The code assumes that the "parent matrix" is square, but that would be easy enough to relax, so the same models (with minor adjustments) would work with arbitrary rectangular matrices.

I think that the puzzle makes a good vehicle for comparing MIP and CP applications to logic problems. In optimization problems, I suspect that MIP models often do a better job of computing objective bounds than do CP models. That is a non-issue here, since the problem is just to find a feasible solution. For logic problems and similar things (particularly scheduling), I think CP models tend to be more expressive, meaning certain types of constraints or relationships can be expressed more naturally with CP than with MIP (where the relationships turn into rather arcane and complicated adventures with binary variables). That applies here, where the CP model exploits the ability to use integer variables as subscripts of other variables.

As described in the PDF file, though, that subscripting ability has its limits. CP Optimizer will let you index a one-dimensional vector of variables using an integer variable, but not a two-dimensional array. In other words, x[y] is fine but x[y, z] is not (where x, y and z are all variables). The workaround I used is to flatten a 2-D matrix into a 1-D matrix. So if $N\times N$ matrix $x$ is flattened into $N^2\times 1$ vector $\hat{x},$  $x_{y,z}$ becomes $\hat{x}_{N(y - 1) + z}.$

The models are a bit too verbose to squeeze into a blog post, so I wrote them up in a separate PDF file. My Java code (which requires recent versions of CPLEX and CP Optimizer) can be had from my code repository under a Creative Commons license.

Scheduling a Round-Robin Tournament

Once in a while I come across a scheduling problem, and of course my first reaction is to think "integer program". A while back, for example, I used an IP model to work out a schedule for a rotating duplicate bridge game (in which both teams and hosts rotated) at the request of a buddy. Most recently, I saw a question on OR Stack Exchange ("Doubles Round Robin Sorting Algorithm") related to tournament scheduling. 

The problem involves six players playing pickleball (so two players on each team, with two sitting out, for each game). Given six players, there are 15 possible teams (pairings). Twelve games are scheduled each week for four weeks, with two sets of six games per week. The author of the question correctly computed that there are 45 possible game configurations. Over the course of the four weeks, he wanted every possible game played at least once (which leaves the final three game slots to be filled arbitrarily). The following conditions must be met:

• within each set of six games, every player plays four games and sits out two;
• no player sits out two consecutive games within the same set;
• no two players are partners more than once per set.

The problem poses no criterion for selecting among feasible schedules; we just want to find any one schedule that works.

My IP formulation can be found in my answer to the OR SE question. I will just mention that it uses binary variables $x_{g,s}=1$ if game $g$ goes in slot $s$ and 0 if not. Games are enumerated up front and indexed from 1 to 15. Slots refer to positions in the schedule and are numbered from 1 to 48, with six slots per set and 12 slots per week. Since no criterion is specified, we just use the default (minimize 0).

I also tried a constraint programming model, using general integer variables $s_1,\dots,s_{48},$ where $s_j \in {1,\dots,15}$ is the index of the game played in slot $j$ of the schedule. My CP formulation uses the "all different" constraint (fairly ubiquitous among CP solvers) to ensure that the first 45 slots each contain a different game. It uses the CP Optimizer "distribute" constraint to ensure that no game is played more than twice and the CP Optimizer "count" constraint to ensure that each player plays exactly four times per set (and thus sits twice) and that no team plays more than once in a set. I'm not sure how common those types of constraints are among CP solvers because I don't have much experience with CP solvers.

As it turns out, both CPLEX (for the IP model) and CP Optimizer (for the CP model) produced feasible schedules in about a second or so on my desktop PC. My intuition was that a CP model would be better suited to this type of problem, because all variables are integer and a CP solver would not be doing much if any matrix arithmetic. As it turns out, it would take a much larger test case to tell whether that intuition has any merit.

If anyone wants to play with the models, my Java code is available from my university GitLab repository. Running it would require CPLEX and CP Optimizer (and not necessarily the most recent versions of either).

Tournament Scheduling: CPLEX v. CP Optimizer (Part 1)

 A recent question on Mathematics Stack Exchange asked about scheduling $N$ "pods" (players) in a tournament under the following conditions.

• There will be $N(N-1)/4$ games played sequentially (no games in parallel).
• Games pit teams of two pods each against each other. One team wears white and one team wears black.
  
• Each pod partners with every other pod once and plays against every other pod twice.
• No pod can play in consecutive games wearing different jersey colors.

The objective is find a schedule that minimizes the total number of times pods have to change their jersey color.

The question specifies $N=9$. Note that, since there are $N(N-1)/4$ games, a necessary condition for the problem to be feasible is that either $N$ or $N-1$ must be divisible by $4$. That condition is not, however, sufficient. An obvious counterexample is when $N=4$ and there are three games to be scheduled. The first game uses all four teams, as does the second game. Since no pod can be forced to wear different jerseys in consecutive games, all four teams would go into the second game wearing the same colors as in the first game ... which means being in the same teams, violating the rule about pods being teamed together exactly once.

I coded both an integer programming model (using CPLEX) and a constraint programming model (using CP Optimizer) in Java and tried to solve the tournament problem with $N=9$. Since everything is inherently integer and the constraints are more logical than arithmetic (the only real algebra is summing up the number of jersey changes), I had two initial expectations: that CPLEX would provide tighter lower bounds than CPO (because MIP models tend to do better with bounds than CP models); and that CPO would find feasible (and possibly optimal) schedules faster than CPLEX would, since the problem is inherently logic-based (and CP models often do better than MIP models on scheduling problems). I was half right. CPLEX did provide tighter lower bounds than CPO, at least within the time limits I was willing to use, although I don't think either came remotely close to a "tight" lower bound. CPO, however, struggled massively to find feasible schedules while CPLEX did not have too much trouble doing so.

Before going any further, I need to issue three caveats. First, the longest I ran the IP model was 30 minutes and the longest I ran the CP model was an hour. Second, while I am pretty familiar with formulating IP models, I am much less familiar running CP models, so I may have missed opportunities to make the CP model more efficient. Third, while CPLEX gives the user a fair amount of indirect control over the search process (by setting branching priorities, MIP emphasis, how frequently to try certain kinds of cuts and so on), CP Optimizer may offer the user even more flexibility in how to tailor searches I am not yet familiar enough to do anything beyond trying to indicate which variables should be the first candidates for branching (and I'm not sure I got that right).

I'll end this installment with a synopsis of some runs.

• In a 30 minute run using the new setting 5 for the MIP emphasis parameter (stressing use of heuristics to improve the incumbent, at the cost of not paying too much attention to the lower bound), CPLEX found a feasible schedule with 14 jersey changes and a lower bound of 2.97 (a 79% gap). It evaluated somewhere around 18,500 nodes.
  
• In a 30 minute run, CP Optimizer branched over 957 million times but never found a feasible schedule and ended with a best bound of 0.
• Finally, I tried running CPLEX for three minutes (in which it found an incumbent with 19 jersey changes) and then used that incumbent as a starting solution for a one hour run of CP Optimizer. CPO accepted the incumbent solution, did a bit over 1.55 billion branch operations, and failed to improve on it. The best bound was again 0. 

If you want to look at my code (which will make slightly more sense after my next couple of posts, where I will describe the models), it is available from my university GitLab repository.

A Group Selection Problem

Someone posted an interesting question about nonlinear integer programming with grouped binary variables on Stack Overflow, and it drew multiple responses. The problem is simple to state. You have 52 binary variables $x_i$ partitioned into 13 groups of four each, with a requirement that exactly one variable in each group take the value 1. So the constraints are quite simple:

\begin{align*} x_{1}+\dots+x_{4} & =1\\ x_{5}+\dots+x_{8} & =1\\ \vdots\\ x_{49}+\dots+x_{52} & =1. \end{align*}

The objective function is a cubic function of the form

\[ \left(\alpha\sum_{i}a_{i}x_{i}\right)\times\left(\beta\sum_{j}b_{j}x_{j}+\beta_{0}\right)\times\left(\gamma\sum_{k}c_{k}x_{k}+\gamma_{0}\right) \] where $\alpha = 1166/2000$, $\beta = 1/2100$, $\beta_0 = 0.05$, $\gamma = 1/1500$ and $\gamma_0 = 1.5$. (In the original post, there is a minus sign in front of the function and the author minimizes; for various reasons I am omitting the minus sign and maximizing here.) Not only is the objective nonlinear, it is nonconvex if minimizing (nonconcave if maximizing). The author of the question was working in R.

Fellow blogger Erwin Kalvelagen solved the problem with a variety of nonlinear optimizers, obtaining a solution with objective value -889.346. Alex Fleischer of IBM posted an answer with the same objective value, using a constraint programming model written in OPL and solved with CP Optimizer.

My initial thought was to linearize the objective function by introducing continuous variables $y_{ij} = x_i \cdot x_j$ and $z_{ijk} = x_i \cdot x_j \cdot x_k$ with domain [0,1]. Many of those variables can be eliminated, due in part to symmetry ($y_{ij} = y_{ji}$, $z_{ijk} = z_{ikj}=\dots=z_{kji}$ and in part due to the observation that $y_{ii}=z_{iii}=x_i$. Also useful is that for $i<j<k$ $z_{ijk}=x_i \cdot y_{jk}$. I have an R notebook that you can download, in which I build the model using standard linearizations for the product of two binarys, then try to solve it with CPLEX using the Rcplex package (and the Matrix package, which allows a sparse representation of the constraint matrix). The results were, shall we say, unspectacular. With a five minute time limit (much longer than what Erwin or Alex needed), CPLEX found an incumbent with value 886.8748 (not bad but not optimal) and a rather dismal optimality gap of 146.5% (due mainly to a loose and slow moving bound).

Out of curiosity, I took a second shot using a genetic algorithm and the GA package for R. I was geeked to see that the GA package includes both an island model (using parallel processing) and a permutation variant (which lets me use permutations of the indices 1 to 52 as chromosomes with no extra work on my part). The permutation approach allows me to treat a chromosome as a prioritization of the 52 binary variables, which I decode into a solution $x$ by scanning the $x_i$ in priority order and setting each to 1 if and only none of the other variables in its group of four has been set to 1. That R notebook is also available for download.

As a metaheuristic, the GA does not offer a proof of optimality, and in fact may or may not find the optimal solution. With my inspired choice of random number seed (123), I matched Erwin's and Alex's solution (889.3463). The settings I used resulted in a run time of about 36 seconds on my PC, more than half of which was spent after the best solution had been found. It's still slower than what Erwin and Alex achieved, but it is a "pure R" solution, meaning it requires nothing besides open-source R packages.

A CP Model for Toasting Bread

A question on Mathematics Stack Exchange deals with a problem (apparently from the book "Thinking Mathematically") about toasting bread on a grill. The grill can hold two slices at a time and can only toast one side of each at a time. You have three slices to toast, and the issue is to figure out how to do it in the minimum possible amount of time (what operations management people refer to as the makespan).

The questioner had a solution that I was able to prove is optimal, using a constraint programming (CP) model that I coded using the Java API to IBM's CPOptimizer (part of the CPLEX Studio product). I won't swear my model is elegant or efficient, since I'm pretty new to CPO, but I think it is correct. If anyone getting started with CPO and the Java API wants to see the source code, it is available in my repository. I'll describe a few key aspects below.

I assumed in my model that there is a single cook. The fundamental components of the model are CPO "interval variables" (instances of IloIntervalVar) for each task (inserting a slice, toasting one side, removing a slice, flipping a slice) along with a dummy task for being done and a placeholder task I called "reversing". Interval variables represent time spans during which tasks are done.

In the problem, there are two ways to get from toasting the front of a slice to toasting the back: you can leave it on the grill and flip it; or you can remove it and (later) replace it with the other side up. Since I didn't know a priori which slices will be handled which way, I created interval variables for removing each slice after the first side, replacing each slice with the second side up, and flipping each slice. Those variables are declared optional, meaning each interval may or may not show up in the solution. For each slice, there is an interval variable for the "reversing" task that is not optional. Each slice has to be reversed, one way or the other. The tasks for replacing a slice (after removing it) and for flipping the slice are listed as alternatives for the reversing task for that slice, which means exactly one of flipping or replacing must be in the solution. Separate constraints ensure that a slice is reinserted if and only if it was removed after the first side toasted. Those constraints use the IloCP.presenceOf function to test whether the remove and reinsert intervals are present, and set the results equal (so both present or neither present).

The sequencing of operations (insert, toast first side, reverse, toast second side, remove) is enforced through a bunch of constraints that use IloCP.endBeforeStart (which says the first argument has to end before the second argument starts). The dummy "done" task is sequenced to start only after each slice has been removed for the final time. I'm pretty sure the objective value (the time everything is done) could be handled other ways, but I tend to think of completion as a zero-length task.

The cook can only do one thing at a time. This is handled using the IloCP.noOverlap function. It is passed a list of every interval that requires the cook's attention (everything but the actual toasting tasks), and prevents any of those intervals from overlapping with any other.

Finally, I need to prevent more than two slices from occupying the grill at any one time. The noOverlap function is no help here. Instead, I use an instance of IloCumFunctionExpr, which represents a function over time that changes as intervals begin and end. In this case, the function measures occupancy.  This is handled by treating the usage as a combination of step functions (IloCP.stepAtStart and IloCP.stepAtEnd). Usage steps up by one at the start of the task of inserting a slice and steps down by one at the end of the task of removing a slice. (Toasting and flipping have no effect on occupancy.) The Javadoc for the relevant functions a bit, um, sparse, essentially saying nothing about the step height argument. Thus I discovered the hard way (through error messages) that adding a step with height -1 when a slice was removed was not acceptable. Instead, I had to subtract a step of height +1.

Although it was not really necessary on a problem this small, I removed some symmetry resulting from the arbitrary ordering of the slices by setting precedence constraints saying that slice 1 is started before slice 2, which in turn is started before slice 3.

It is possible to model the problem as an integer program, and in fact I initially leaned that direction. The IP model, however, would be bulkier and less expressive (which would make it more prone to logic errors), and quite possibly would be slower to solve. CPOptimizer is designed specifically with scheduling problems in mind, so it is the better tool for this particular job.

Updated Java Utilities for CPLEX and CP Optimizer

I just finished adding a feature to a utility library I use in Java projects that employ either CPLEX or CP Optimizer. In addition, I moved the files to a new home. The library is free to use under the Eclipse Public License 1.0. The code is mentioned in previous posts, so I'll just quickly summarize the content here and refer interested parties to the earlier posts:

• Setting CPLEX Parameters (October 2012)
• Printing a CP Optimizer Model in Java (March 2014)
• Setting CPLEX Parameters in Java Revisited (May 2014)

The latest source code is now available from the Michigan State University Gitlab server. You do not need to log in, and you do not need to be a Git user. You can just click the download button near the upper right to get a ZIP archive of the source code. If you run into any bugs, there is an issue tracker on the MSU site where you can report them (please!). If you just want a binary (.jar) file and the Javadoc documentation, you can download a .zip file from my MSU web space.

In the following description, please assume that cplex and cp are instances of IloCplex and IloCP respectively. The main reason I developed the library is that I like to experiment with different parameter settings for CPLEX and CP Optimizer. Rather than hard coding a parameter (e.g., cplex.setParameter(IloCplex.Param.Emphasis.MIP, 3)) and then having to edit and recompile the code to try a different value, I prefer to pass CPLEX and CP Optimizer parameters to the program through the command line (or, if my program has a graphical interface, through a user dialog). The equivalent code to the previous example might look like cplex.setParameter(pname, pval) where pname is a string with value "Emphasis.MIP" (the minimum portion of the full parameter name necessary to uniquely identify the parameter) and pval is a string with the value "3".

With that as background, here is a summary of the contents of the library:

• CplexParameterSetter: Use an instance of this class to apply parameter settings (each specified by two strings, parameter name and new value) to an instance of IloCplex. Example code appears in the May 2014 post (look for the version 2.0 sample).
• CPOptimizerParameterSetter: Use an instance of this class to apply parameter settings to an instance of IloCP. Again, sample code is in the May 2014 post.
• CPDisplay: The static method CPDisplay.asString(cp) will produce a summary of the model in cp, suitable for printing or displaying. For whatever reason, IloCplex.toString() produces a human-readable version of a CPLEX model, but IloCP.toString() just prints the object's hash code. This class provides a workaround. For the output to really be readable, you need to be assiduous about assigning meaningful names to the variables and constraints in the model. I originally released this (in the March 2014 post) as an override to IloCP.toString(), but I decided a static method was easier to use (does not require extending IloCP).
• Main program: The project comes with a main program. If you run it, you will get an alphabetized list of all parameters known to the versions of CPLEX and CP Optimizer that you are using. For instance, run against CPLEX Studio 12.6.1, the output I get looks like this:

  CPLEX:
             AbsGap double  IloCplex.Param.MIP.Pool.AbsGap
          AbsMIPGap double  IloCplex.Param.MIP.Tolerances.AbsMIPGap
          AbsMIPGap double  IloCplex.Param.MIP.PolishAfter.AbsMIPGap
            Advance int  IloCplex.Param.Advance
  [...]
         WriteLevel int  IloCplex.Param.Output.WriteLevel
        ZeroHalfCut int  IloCplex.Param.MIP.Cuts.ZeroHalfCut
  
  CPOptimizer:
                    AllDiffInferenceLevel int  IloCP.IntParam.AllDiffInferenceLevel
             AllMinDistanceInferenceLevel int  IloCP.IntParam.AllMinDistanceInferenceLevel
  [...]
                             WarningLevel int  IloCP.IntParam.WarningLevel
                                  Workers int  IloCP.IntParam.Workers
  

  At least for me, the main use of this is to figure out which parameter names are unambiguous and which are repeated. For instance, the CPLEX parameter IloCplex.Param.MIP.Pool.AbsGap can be abbreviated "AbsGap"; but the minimum amount necessary to specify the absolute MIP gap for convergence is "Tolerances.AbsMIPGap", since "AbsMIPGap" could also refer to IloCplex.Param.MIP.PolishAfter.AbsMIPGap.

If you have questions about the proper use of the code, please feel free to post them in as comments here. If you run into bugs (or missing features), please use the issue tracker. That will help me keep tabs on what needs to be done.

Setting CPLEX Parameters in Java Revisited

A bit more than a year and a half ago, I wrote some Java code to facilitate setting parameters for the CPLEX optimizer using their Concert API. Since then, I've added support for their CP Optimizer, and IBM has refactored the handling of parameters in CPLEX, necessitating an update to my code. This post (which supersedes the previous one) describes how to get and use my code, which is licensed under the Eclipse Public License.

Purpose

When using any of the programming APIs to CPLEX or CP Optimizer, the conventional ways to set parameters for the solver are to hard-code them, or to hard-code methods of setting specific parameters (for instance, write a method that sets the solver time limit using an argument fetched from somewhere). Unfortunately, picking parameter values for either solver is an NP-annoying task, with lots of possible combinations to consider. I therefore prefer to set them either from command line arguments or possibly from user inputs obtained from a GUI for my program. My utility library provides the necessary infrastructure for doing that.

Requirements

Other than Java 7 or later (once a "later" becomes available), all you need to use the code are the same jar and binary files for CPLEX and/or CP Optimizer that your program needs to use those solvers. If you are only using one of the solvers, you will not need to link the other library in order to use my code.

Versions

Due to the aforementioned refactoring, I was forced to create two versions of the utility, with the second version not backward-compatible. I'll provide usage example for both below. As best I can tell, they work identically with CPOptimizer, other than needing (version 2) or not needing (version 1) to have a class instance created. CPOptimizer does not have hierarchical parameter names, and none of its parameter names are ambiguous.

Both versions use strings for both the parameter name and the parameter value (since a string is how the value would be obtained from the command line); the utility takes care of interpreting strings representing numerical or logical values.

Version 1.0

Version 1 of my utility works with CPLEX 12.5.1 or earlier. It uses the (mercifully short) parameter names in force prior to the IBM refactoring, so for instance you can specify the time limit parameter as "TiLim". Parameter names in this version are case-sensitive (so "TiLim" works but neither "tilim" nor "Tilim" will). Version 1.0 also works with CPLEX 12.6 using the old parameter names, but it will not recognize the new names. For instance, when setting the branching direction in CPLEX 12.6, version 1.0 will recognize the old name "BrDir" but not the new name "MIP.Strategy.Branch". According to the CPLEX documentation, the old parameter names are deprecated, so version 1 of my utility will work with CPLEX 12.6 and probably with any minor upgrades (a hypothetical 12.6.1, say), but may stop working with some future version of CPLEX.

Version 1 uses a static method to set parameters (see the example below) and does not require that an instance of the parameter setter class be created.

Version 1 does not contain a main program; it is purely a library.

Version 2.0

Version 2 of my utility works with CPLEX 12.6 but not with earlier versions of CPLEX, as it only knows the new parameter names. Thus, reversing the previous example, version 2 will recognize "MIP.Strategy.Branch" but not "BrDir". Unlike version 1, parameter names in version 2 are not case-sensitive; "mip.strategy.branch" and "MIP.strategy.branch" will work just as well as "MIP.Strategy.Branch".

The new parameter names, which reflect a class hierarchy, are a PITA to type, so version 2 will accept shortened versions when no ambiguity exists. In the case of the branch direction, "Strategy.Branch" and just "Branch" will work equally well. The name "Display", however, maps to seven (!) distinct parameters, so you need to provide enough of the hierarchy to eliminate the ambiguity. If you want to adjust the simplex display, you can use "IloCplex.Param.Simplex.Display" (have fun typing that!) or "Param.Simplex.Display" or "Simplex.Display" (which gets my vote), but not just "Display". Failure to use enough of the hierarchy to uniquely identify the target parameter will result in an AmbiguousParameterException being thrown.

The inevitable one exception to this is the time limit. Three parameters answer to the name "TimeLimit", but for somewhat arcane reasons I coded the utility to recognize "TimeLimit" as meaning "IloCplex.Param.TimeLimit". (For the other two parameters, you'll need "Tune.TimeLimit" and either "DistMIP.Rampup.TimeLimit" or just "Rampup.TimeLimit".)

Version 2, in contrast to version 1, does not employ a static parameter setter, and so you need to create an instance of the parameter setter in order to use it. Again, see the example below.

Version 2 contains a main program. If you run it, it will list all the parameters it can find for both CPLEX and CPOptimizer. If you have one but not the other linked, you'll want to comment out the portion of the code that lists parameters for the solver you are not using.

Examples

In the following examples, I will assume that you want to set the time limit (double) for both CPLEX and CPOptimizer, the log verbosity (integer) for CPOptimizer, the solution limit (long) for CPLEX, and the presolve switch (logical) for CPLEX. For the CPLEX 12.6 parameters, I'll use the shortest legal name. Left to the reader as an exercising: import statements and wrapping portions of the code in try-catch blocks as needed.

Version 1.0

// create solver instances
IloCplex cplex = new IloCplex();
IloCP cp = new IloCP();

// parameter names (would normally come from command line or GUI)
String[] cplexNames = new String[] {"TiLim", "IntSolLim", "PreInd"};
String[]  cpNames = new String[] {"TimeLimit", LogVerbosity"};

// parameter values  (would normally come from command line or GUI)
String[] cplexValues = new String[] {"23.5", "1000", "false"};
String[] cpValues = new String[] {"23.5", 1};

// set the CPLEX parameters
for (int i = 0; i < cplexNames.length; i++) {
   cplexutils.CplexParamSetter.set(cplex, cplexNames[i], cplexValues[i]);
}

// set the CPOptimizer parameters
for (int i = 0; i < cpNames.length; i++) {
  cplexutils.CPOptimizerParamSetter.set(cp, cpNames[i], cpValues[i]);
}

Version 2.0

// create solver instances
IloCplex cplex = new IloCplex();
IloCP cp = new IloCP();

// create parameter setter instances
CplexParameterSetter csetter = new CplexParameterSetter();
CPOptimizerParameterSetter cpsetter = new CPOptimizerParameterSetter();

// parameter names (would normally come from command line or GUI)
String[] cplexNames = new String[] {"TimeLimit", "Limits.Solutions", "Presolve"};
String[]  cpNames = new String[] {"TimeLimit", LogVerbosity"};

// parameter values  (would normally come from command line or GUI)
String[] cplexValues = new String[] {"23.5", "1000", "false"};
String[] cpValues = new String[] {"23.5", 1};

// set the CPLEX parameters
for (int i = 0; i < cplexNames.length; i++) {
   csetter.set(cplex, cplexNames[i], cplexValues[i]);
}

// set the CPOptimizer parameters
for (int i = 0; i < cpNames.length; i++) {
  cpsetter.set(cp, cpNames[i], cpValues[i]);
}

Obtaining the code

You can download either version from the project's downloads page on Bitbucket. Binaries are available from the "Downloads" tab, source code from the "Tags" tab. If you run into a bug (unlikely, but you never know), please let me know. There's an issue tracker under the "Issues" link.
Please see the more recent post Updated Java Utilities for CPLEX and CP Optimizer for a description of the contents of the library and links to both source code and a binary distribution. Please note that version 1.0 no longer exists; the links in the updated post will take you to the most recent version.

Printing a CP Optimizer Model in Java

Update: I've converted the code to a static method (so that you do not need to extend the IloCP class), and added to a utility package I wrote. Please see this post for details on the software and how to get it.

The IBM ILOG CP Optimizer constraint programming solver has a Java API that currently seems to provide no easy way to print out a model. Here's a hack that prints the key ingredients (objectives and constraints). It does not explicitly list variables (they're embedded in the constraints and objectives), but that would be an easy fix. It also does not print out parameter settings. The code as written overrides the .toString() method for a class containing an instance of IloCP named 'solver'.

  @Override
  public String toString() {
    if (solver == null) {
      return "No model yet!";
    } else {
      StringBuilder sb = new StringBuilder();
      Iterator it = solver.iterator();
      while (it.hasNext()) {                           // iterate over the model
        IloAddable object = (IloAddable) it.next();    // get the next object
        if (object instanceof IloObjective) {
          // For an objective, .toString() returns the body of the objective.
          sb.append(object.getName())
            .append(": ")
            .append(object)
            .append("\n");
        } else if (object instanceof IloConstraint) {
          /*
            For some constraints, .toString() returns the body; for others
            (notably inequalities), .toString() returns the name if there is
            one, the body if the name is null.
          */
          IloConstraint ct = (IloConstraint) object;
          String name = ct.getName();             // get the name
          ct.setName(null);                       // temporarily remove the name
          sb.append(name)
            .append(": ")
            .append(ct)                           // this now gets the body
            .append("\n");
          ct.setName(name);                       // restore the name
        } else {
          sb.append(object.getClass().toString()).append("\n");
        }
      }
      return sb.toString();
    }
  }

CP Optimizer, Java and NetBeans

After years of coding CPLEX applications in Java, I've just started working with CP Optimizer (the IBM/ILOG constraint programming solver) ... and it did not take me long to run into problems.

As with CPLEX, you access CP Optimizer from Java through the Concert API. As always, I am using the NetBeans IDE to do the coding. With CPLEX, this required two steps: add a library to the project, containing the cplex.jar file (for compilation); and add an option of the form -Djava.library.path=<path to CPLEX>/cplex/bin/x86-64_linux to Project Properties > Run > VM Options (for execution). Your path will differ depending on which version of CPLEX you have, where it is installed, and what operating system you are using.

So I naively expected to have to do the same two things to use CP Optimizer, albeit with different paths and files. I was half right (which, like being half alive, is not all that useful).

The good news was that for compilation, all that was required was adding a library to the project, this time pointing to ILOG.CP.jar. The bad news was that putting the corresponding path to the binary libraries in java.library.path most emphatically did not work. I got a ton of linking errors.

I won't bore you with the details of the errors, nor my fruitless pounding on Google to find me an answer. The CPLEX Optimization Studio distribution comes with Java examples and a make file for them. I ran the make file (outside NetBeans), and everything worked. That gave me an idea of what I needed to do. Apparently, the path to the binaries cannot go in java.library.path. I'm not sure why, but I think it has something to do with the way the binaries, which are C/C++ code wrapped for use by Java, are linked. Instead, on my Linux system they have to be specified in the LD_LIBRARY_PATH environment variable.

Thus, per this earlier post, I hacked the <NetBeans directory>/etc/netbeans.conf file and added the line

export LD_LIBRARY_PATH=<path to CPLEX Studio 12.6>/cplex/bin/x86-64_linux:<path to CPLEX Studio 12.6>/cpoptimizer/bin/x86-64_linux

Note that if you have other goodies already on your library path that your NetBeans programs might need, you'll need to append them to the path. Also, I'm not sure what the equivalent of LD_LIBRARY_PATH is in the Windows world, let alone on a Mac ... but I suspect that something similar will be required.

I also added the same LD_LIBRARY_PATH export to ~/.bashrc so that, should I run one of my programs from a terminal, the correct paths will be in place.

A couple of warnings:

• Obviously this hack will need to be updated whenever you upgrade to a newer version of CPLEX Optimization Studio.
• This will complicate the testing of different versions of CPLEX or CP Optimizer in the same program (other than by editing netbeans.conf for each version). With CPLEX and my previous configuration, I could just switch the CPLEX library version and alter the java.library.path string in the NetBeans project properties for that project. So much for the good old days.