# Problem finding feasible solution for IP/constraint programming problem when objective function changes

 3 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 Roeder 31●1●2 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

 3 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. answered 25 Sep '12, 21:08 AndyT 678●8 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
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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: