Dear all,

I am working on a milp model on GAMS. the software gave me a feasible solution. however, when I make the size of the model larger, I encounter with thr following error. CPLEX Error 1217: No solution exists. what should I do? does any one have any suggestion?

all the bests,

asked 25 Apr '13, 05:02

nadia's gravatar image

nadia
11125
accept rate: 0%

edited 25 Apr '13, 05:46

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919

1

Contacting GAMS support might be an idea, they can easily spot the problem.

(25 Apr '13, 06:35) Bo Jensen ♦

You have an infeasible model. some of the constraints or bounds you have modeled can't be satisfied for any solution. Check your constraints and bounds in your model.

If You can't find an error in your model you can try using the FeasOpt parameter in cplex. You can find info in section 6.7 in the documentation.

link

answered 25 Apr '13, 05:24

Buxley's gravatar image

Buxley
5641414
accept rate: 9%

If there is no feasible solution, can it not return the infeasible solution with the least number of hard constraints broken? That's what I do in OptaPlanner, so the user has an idea what to change. For example, in Employee rostering, the infeasible solution's broken hard constraints are an indication how many employees to hire and which skill-sets they'll need.

(25 Apr '13, 08:03) Geoffrey De ... ♦
1

@Geoffrey B&B+C based MIP solvers typically will only return a integer feasible solution, in case no such exists, it's highly application dependent what the user want and it should be formulated in a separate problem. One approach could be a feasibility repair routine.

(25 Apr '13, 08:06) Bo Jensen ♦

@Bo very interesting: What might a user want? Apart from knowing if A) the solution is feasible and B) the best (possibly infeasible) solution, is there anything else he might want which I am overlooking? PS: What's a feasibility repair routine?

(25 Apr '13, 08:15) Geoffrey De ... ♦
2

@Geoffrey But the measure to determine the "best possible infeasible solution" could be anything really, as said user specific. A feasibility repair routine could be different ways to tell the user, what minimum changes to apply to the model making it feasible.

(25 Apr '13, 08:22) Bo Jensen ♦

@Bo Thanks

(25 Apr '13, 08:27) Geoffrey De ... ♦
2

@Geoffrey "If there is no feasible solution, can it not return the infeasible solution with the least number of hard constraints broken? " This is exactly what the feasopt parameter will do . You can also specify which constraints you prefer to be feasible.

(25 Apr '13, 08:50) Buxley
showing 5 of 6 show 1 more comments
link

answered 25 Apr '13, 05:27

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

Or the model could in fact be infeasible, which is not an error, but retrieving the non existing solution is probably the error you get.

(25 Apr '13, 05:33) Bo Jensen ♦

short and concise!

(25 Apr '13, 05:36) Buxley

thanks for your answer. As I mentioned, the software can handle the model in small sizes(5,10,15 nodes). but when I increase the size of model to 20 nodes, I encounter with this error. I think there is some problem with GAMS software that can't handle the model. the model with 20 nodes has 160,401 variables and 472,441 constraints.

(25 Apr '13, 05:41) nadia

Following others' good answers, I could give you the tips below:

a) In case you're using your own randomly-generated instances, it's possible that there are some conflicts or inconsistencies in the data that would make the model infeasible.

b) Another possibility is that for small instances, the data would make an incorrect constraint redundant. However for larger instances, that incorrect constraint becomes active. So, I think it would be a good idea to check the constraints manually one more time (removing all the constraints and then adding them one at a time).

c) The size of your model should not have anything to do with the infeasibility. If the size was a problem, it would result in a memory error (CPLEX error code: 1001). Personally, I've worked with larger instances in GAMS and it works fine.

link

answered 25 Apr '13, 08:49

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

edited 26 Apr '13, 10:59

Try rewriting your problem as an over-constrained problem.

A typical approach is this:

  1. Keep your normal hard constraints as hard constraints, except for requiring variables to be assigned.
  2. Allow variable's to be unassigned. Minimize this as medium constraints.
  3. Keep your normal soft constraints.

For example, applied to employee rostering:

  1. HARD: No employee should work 2 shifts on the same day.
  2. MEDIUM: Not every shift must be assigned to an employee, but we want to minimize the number of unassigned shifts.
  3. SOFT: Avoid that an empployee has to work more than 5 days in a row.
link

answered 25 Apr '13, 08:10

Geoffrey%20De%20Smet's gravatar image

Geoffrey De ... ♦
3.6k32764
accept rate: 6%

edited 25 Apr '13, 08:11

If you pass a feasible but difficult model to CPLEX and then arrowroot to access the solution before it find a first feasible solution, I think you get a 1217 error. I don't know how GAMS interfaces with CPLEX, so I don't know whether this can occur using GAMS. If you can see the CPLEX node log, check whether an integer incumbent exists before the error occurs. Perhaps you just need to increase time, memory or iteration limits (or switch the CPLEX MIP emphasis to feasibility).

link

answered 25 Apr '13, 16:27

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

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:

×191
×190
×51
×39

Asked: 25 Apr '13, 05:02

Seen: 26,492 times

Last updated: 26 Apr '13, 10:59

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