Hi, everyone,

A coworker and I are working on an IP/CP problem in OPL and running into a baffling-to-us problem:

If our objective is to max(sum x_i), CPLEX is able to find a solution without any difficulties. If we modify the objective to read max((sum x_i) - (y-z)), where y and z are variables that already exist in the program, it cannot find a feasible solution.

We're running the problems on our PCs using the ILOG studios software from IBM.

Does anyone have any ideas what we might do (or not do) to avoid this problem? We're in simulation, so are relatively inexperienced in this area. If there are any references we should check out, we'd be happy to do so.

Thank you! Theresa

asked 24 Sep '12, 18:23

Theresa%20Roeder's gravatar image

Theresa Roeder
3112
accept rate: 0%

Sorry for asking some silly questions, but is the term \(-(y-z)\) bounded under maximization? What is its magnitude (roughly) relative to \(\sum x_i\)?

(25 Sep '12, 01:00) Gilead ♦
1

A good and not silly question: (y-z) is definitely bounded. Specifically, y is the max of all the x_i, z is the min. (We're trying to maximize the total while keeping the range within a reasonable value.)

(25 Sep '12, 01:03) Theresa Roeder

This seems strange as feasibility should be governed with the set of constraints, and not the objective function. Perhaps, there is something wrong with the new constraints you're adding to find minimum and maximum of \(x_i\).

(25 Sep '12, 01:43) Ehsan ♦

To make sure that you're correctly calculating minimum and maximum of \(x_i\), omit the \(\sum x_i\) term from the objective function and see what happens. If the related constraints are wrong, the solver should identify the model as either infeasible or unbounded.

(25 Sep '12, 01:48) Ehsan ♦

Is your model a MIP model or a CP model?

How do you define y and z?

(25 Sep '12, 04:18) jfpuget

Thanks for all the thoughts!

The strange thing is that we didn't add any constraints; the definition for y and z are in the original model, we're just adding them to the objective function in the second case. For their definition, we've got y >= x_i for all i, and z <= x_i for all i. Just for fun, I'll remove the sum(x_i) from the objective and see if it can solve min (y-z).

The problem is MIP with CP constraints. We're using CPLEX to solve it.

(25 Sep '12, 09:59) Theresa Roeder

Does "cannot find a feasible solution" mean CPLEX declares the model infeasible? Or does it mean that you cut off iterations at some specific time and CPLEX has yet to find an incumbent?

(25 Sep '12, 18:11) Paul Rubin ♦♦

No, it doesn't declare it infeasible. We ran for an hour; with the original objective, it takes at most 3 minutes to find a feasible solution.

(25 Sep '12, 19:42) Theresa Roeder

Is your model solved with CPLEX Optimizer or CP Optimizer? Both are available in OPL, and since you mention CP constraints I wonder if you're not using the latter.

(26 Sep '12, 08:39) jfpuget

My colleague tried using CP Optimizer and was unable to find a feasible solution within an hour for a majority of the problems. Those that did find solutions were significantly worse solutions than the ones found by CPLEX, so we went back to CPLEX.

(26 Sep '12, 18:05) Theresa Roeder
showing 5 of 10 show 5 more comments

If you are interested in solving the problem with the modified objective, one approach would be to write out one (or more) feasible solutions to an MST or SOL file. Such feasible solutions can then be used as a warm start to solve the modified objective problem with the same solution space.

link

answered 25 Sep '12, 21:08

AndyT's gravatar image

AndyT
6788
accept rate: 7%

1

Ohhh - see, told you I'm new to this. That would definitely be a good thing to do. Hopefully it'll be able to find something with that! :)

(26 Sep '12, 17:56) Theresa Roeder

Hmm, my guess is simply that the additional term makes the heuristics of CPLEX look in an infeasible part of the solution space. Even though changing an objective function coefficient should not have any effect on the solution space, it might have an effect on the heuristics. In particular many heuristics in modern MIP (and I guess CP) solvers take the objective into account.

At the EURO2012 conference in Vilnius I overhead a talk in which a significant improvement in the solution time was found by adding completely redundant constraint (as in not useful in any way). I think the speaker was Prof. Matteo Fischetti from Padova University. An example would be a program with only binary variables, say x_i. Adding a redundant cut like

sum_i x_i >= -1

would improve the runtime by a factor of 10, which also seems very strange.

Did you try to change the CPLEX parameter to emphasize on finding a feasible solution? Alternative, you can find out which heuristic finds a good solution in the case without the term and tune the parameter for this in the case with the term added.

TL:DR: Modern solvers some times behave strange...

Edit: This is of course assuming that you added the term correctly etc.

link

answered 25 Sep '12, 07:35

Tue_Christensen's gravatar image

Tue_Christensen
102
accept rate: 0%

edited 25 Sep '12, 07:36

2

Fischetti did not claim that simply adding that constraint improved solution times. His point was that there is a significant amount of randomness in tree search and that adding irrelevant constraints can change the order in which things are done.

(25 Sep '12, 09:18) Michael Trick ♦♦

Yes, you are (of course) correct. Anyway, my point was that adding seemingly unrelated (in some sense) stuff to an MIP/CP can have unexpected effects when using CPLEX. I have seen differences in runtimes when solving a model depending on if it was supplied by an .lp file or by the Concert technology...

(25 Sep '12, 09:35) Tue_Christensen

Thank you! This helps us at least understand why the seemingly irrelevant change to the objective function would impact the feasibility of the problem. I did try changing the parameter to emphasize feasibility, but perhaps I will try it again and just run the problem overnight. The second objective function makes logical sense, and we've been forced to try to "hack" the model to achieve the desired result - which feels unsatisfying.

(25 Sep '12, 10:10) Theresa Roeder

If the heuristics are the cause of the problem, then perturbing them by permuting the binary variables as suggested may reveal some clues. Mike Trick wrote a very interesting piece on this (referencing Fischetti's insights): goo.gl/pWUSj This would be of interest to anybody who uses IP.

(25 Sep '12, 20:36) Gilead ♦

Gilead: I can see it is took long since my last visit to Michael's homepage.

I am glad to see that a paper has been submitted on the subject, which is very fascinating!

(26 Sep '12, 03:02) Tue_Christensen

@Tue_Christensen "I have seen differences in runtimes when solving a model depending on if it was supplied by an .lp file or by the Concert technology..." => This is a well known fact, which applies for both LP and MIP. When column,row,nonzero matrix order is changed it can (and often will) change the path of the algorithm. On top of that you got limited precision in some of the file formats too, so even if the order is the same the coefficients may be slightly different.

(26 Sep '12, 03:12) Bo Jensen ♦

con't I remember a study by Torsten Koch from zib where just randomly permuting MIP's significantly change solution times on a large data set.

(26 Sep '12, 03:12) Bo Jensen ♦

I posted before reading Mike's blog post, hence why my comment looks a bit odd, sorry.

(26 Sep '12, 03:50) Bo Jensen ♦

Hah, I'm about 2 weeks behind on reading Mike's blog, which is why I hadn't seen this post yet.

THANK YOU to everyone for your help! We're very, very grateful for all your insights. I'll report back on how we fare!

(26 Sep '12, 18:18) Theresa Roeder
showing 5 of 9 show 4 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×37
×1

Asked: 24 Sep '12, 18:23

Seen: 3,140 times

Last updated: 26 Sep '12, 18:18

OR-Exchange! Your site for questions, answers, and announcements about operations research.