Mdthbs

Is TA-ing worth the opportunity cost?

Could one become a successful researcher by writing some really good papers while being outside academia?

In the movie Harry Potter and the Order or the Phoenix, why didn't Mr. Filch succeed to open the Room of Requirement if it's what he needed?

Decode a variable-length quantity

Infeasibility in mathematical optimization models

Colleagues speaking another language and it impacts work

Short story about a teenager who has his brain replaced with a microchip (Psychological Horror)

What is to be understood by the assertion 'Israels right to exist'?

What are good ways to improve as a writer other than writing courses?

Can a PC attack themselves with an unarmed strike?

Independent table row spacing

How do I change the output voltage of the LM7805?

Is it really ~648.69 km/s Delta-V to "Land" on the Surface of the Sun?

Can an actual attack instead of a feint be used as the distraction for a help action?

Unexpected route on a flight from USA to Europe

Is this cheap "air conditioner" able to cool a room?

Did silent film actors actually say their lines or did they simply improvise “dialogue” while being filmed?

Casting Goblin Matron with Plague Engineer on the battlefield

Was there ever a difference between 'volo' and 'volo'?

Secure my password from unsafe servers

Where is the rule for moving slowly when searching for traps that’s referenced by Dungeon Delver?

What can make Linux unresponsive for minutes when browsing certain websites?

How does The Fools Guild make its money?

Validation and verification of mathematical models

Infeasibility in mathematical optimization models

The difference between max-min and min-maxSymmetry-breaking ILP constraints for square binary matrixGuidelines for Linear Optimization approaches?partitioning hub assignment modelsHow to determine the correct level of detail when modelling?Mathematically creating the 'perfect' permutation for reservations in a hostelGood sources on developing mathematical modelsOptimal value exceeds actual value for a minimization problemDifference between Chance constraints and logical constraintsValidation and verification of mathematical models

4

$begingroup$

Sometimes, when solving mathematical optimization models (especially MIPs), they may be infeasible. Is there any comprehensive method to deal with the infeasibility conditions? (especially in complex models)

optimization modeling

share|improve this question

edited 7 hours ago

LarrySnyder610

5,1981313 silver badges6161 bronze badges

asked 8 hours ago

abbas omidiabbas omidi

5511010 bronze badges

$endgroup$

add a comment | 

4

$begingroup$

Sometimes, when solving mathematical optimization models (especially MIPs), they may be infeasible. Is there any comprehensive method to deal with the infeasibility conditions? (especially in complex models)

optimization modeling

share|improve this question

edited 7 hours ago

LarrySnyder610

5,1981313 silver badges6161 bronze badges

asked 8 hours ago

abbas omidiabbas omidi

5511010 bronze badges

$endgroup$

add a comment | 

$begingroup$

Sometimes, when solving mathematical optimization models (especially MIPs), they may be infeasible. Is there any comprehensive method to deal with the infeasibility conditions? (especially in complex models)

optimization modeling

share|improve this question

edited 7 hours ago

LarrySnyder610

5,1981313 silver badges6161 bronze badges

asked 8 hours ago

abbas omidiabbas omidi

5511010 bronze badges

$endgroup$

share|improve this question

edited 7 hours ago

LarrySnyder610

5,1981313 silver badges6161 bronze badges

asked 8 hours ago

abbas omidiabbas omidi

5511010 bronze badges

share|improve this question

edited 7 hours ago

LarrySnyder610

5,1981313 silver badges6161 bronze badges

asked 8 hours ago

abbas omidiabbas omidi

5511010 bronze badges

edited 7 hours ago

LarrySnyder610

5,1981313 silver badges6161 bronze badges

edited 7 hours ago

LarrySnyder610

5,1981313 silver badges6161 bronze badges

asked 8 hours ago

abbas omidiabbas omidi

5511010 bronze badges

asked 8 hours ago

abbas omidiabbas omidi

5511010 bronze badges

5 Answers
5

active

oldest

votes

5

$begingroup$

Adding slack variables (with high penalty in the objective function) converts hard constraint into soft ones, and can also be useful to locate the source of infeasibility. This approach can be very useful for feasible problems for which finding a heuristic feasible solution is hard/very time consuming.

share|improve this answer

answered 8 hours ago

Matteo FischettiMatteo Fischetti

90133 silver badges1111 bronze badges

$endgroup$

add a comment | 

3

$begingroup$

CPLEX offers the conflict refiner for this purpose:

A conflict is a set of mutually contradictory constraints and bounds within a model. Given an infeasible model, IBM ILOG CPLEX can identify conflicting constraints and bounds within it. CPLEX refines an infeasible model by examining elements that can be removed from the conflict to arrive at a minimal conflict. A conflict smaller than the full model may make it easier for the user to analyze the source of infeasibilities in the original model.

Taken from the CPLEX documentation.

share|improve this answer

answered 7 hours ago

Kevin DalmeijerKevin Dalmeijer

1,59944 silver badges2222 bronze badges

$endgroup$

add a comment | 

3

$begingroup$

Related to @Kevin Dalmeijer's answer, Gurobi offers Irreducible Inconsistent Subsystem functionality via Model.computeIIS():

Compute an Irreducible Inconsistent Subsystem (IIS). An IIS is a subset of the constraints and variable bounds with the following properties:

• the subsystem represented by the IIS is infeasible, and




• if any of the constraints or bounds of the IIS is removed, the subsystem becomes feasible.

Note that an infeasible model may have multiple IISs. The one returned by Gurobi is not necessarily the one with minimum cardinality; there may exist others with fewer constraints or bounds.

share|improve this answer

answered 6 hours ago

dxbdxb

81333 silver badges1414 bronze badges

$endgroup$

add a comment | 

1

$begingroup$

Here is a good (but a little bit old) paper[1] discussing the algorithmic approaches to identify and manage the infeasibility situation in MIPs and IPs.

[1] Guieu, Olivier, and John W. Chinneck. "Analyzing infeasible mixed-integer and integer linear programs." INFORMS Journal on Computing 11.1 (1999): 63-77.

share|improve this answer

answered 7 hours ago

Oguz ToragayOguz Toragay

1,95822 silver badges2222 bronze badges

$endgroup$

add a comment | 

1

$begingroup$

On top of getting IIS from the solver and using slack variables (as suggested by other answers), one more thing that you can do for debugging purposes is to fix your variables to a known feasible solution and see what is reported from your model. Doing that, you can figure out what has happened to make the problem infeasible.

For example, assume you have $x_1 +x_2 = 10$ constraint and a known feasible solution is $x_1 = 6, x_2 = 2$, you can see the infeasibility and the constraint that throws the infeasibility.

share|improve this answer

answered 6 hours ago

EhsanKEhsanK

1,95933 silver badges2929 bronze badges

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "700"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f1215%2finfeasibility-in-mathematical-optimization-models%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

5

$begingroup$

Adding slack variables (with high penalty in the objective function) converts hard constraint into soft ones, and can also be useful to locate the source of infeasibility. This approach can be very useful for feasible problems for which finding a heuristic feasible solution is hard/very time consuming.

share|improve this answer

answered 8 hours ago

Matteo FischettiMatteo Fischetti

90133 silver badges1111 bronze badges

$endgroup$

add a comment | 

5

$begingroup$

Adding slack variables (with high penalty in the objective function) converts hard constraint into soft ones, and can also be useful to locate the source of infeasibility. This approach can be very useful for feasible problems for which finding a heuristic feasible solution is hard/very time consuming.

share|improve this answer

answered 8 hours ago

Matteo FischettiMatteo Fischetti

90133 silver badges1111 bronze badges

$endgroup$

add a comment | 

$begingroup$

Adding slack variables (with high penalty in the objective function) converts hard constraint into soft ones, and can also be useful to locate the source of infeasibility. This approach can be very useful for feasible problems for which finding a heuristic feasible solution is hard/very time consuming.

share|improve this answer

answered 8 hours ago

Matteo FischettiMatteo Fischetti

90133 silver badges1111 bronze badges

$endgroup$

share|improve this answer

answered 8 hours ago

Matteo FischettiMatteo Fischetti

90133 silver badges1111 bronze badges

answered 8 hours ago

Matteo FischettiMatteo Fischetti

90133 silver badges1111 bronze badges

answered 8 hours ago

Matteo FischettiMatteo Fischetti

90133 silver badges1111 bronze badges

3

$begingroup$

CPLEX offers the conflict refiner for this purpose:

A conflict is a set of mutually contradictory constraints and bounds within a model. Given an infeasible model, IBM ILOG CPLEX can identify conflicting constraints and bounds within it. CPLEX refines an infeasible model by examining elements that can be removed from the conflict to arrive at a minimal conflict. A conflict smaller than the full model may make it easier for the user to analyze the source of infeasibilities in the original model.

Taken from the CPLEX documentation.

share|improve this answer

answered 7 hours ago

Kevin DalmeijerKevin Dalmeijer

1,59944 silver badges2222 bronze badges

$endgroup$

add a comment | 

3

$begingroup$

CPLEX offers the conflict refiner for this purpose:

A conflict is a set of mutually contradictory constraints and bounds within a model. Given an infeasible model, IBM ILOG CPLEX can identify conflicting constraints and bounds within it. CPLEX refines an infeasible model by examining elements that can be removed from the conflict to arrive at a minimal conflict. A conflict smaller than the full model may make it easier for the user to analyze the source of infeasibilities in the original model.

Taken from the CPLEX documentation.

share|improve this answer

answered 7 hours ago

Kevin DalmeijerKevin Dalmeijer

1,59944 silver badges2222 bronze badges

$endgroup$

add a comment | 

$begingroup$

CPLEX offers the conflict refiner for this purpose:

A conflict is a set of mutually contradictory constraints and bounds within a model. Given an infeasible model, IBM ILOG CPLEX can identify conflicting constraints and bounds within it. CPLEX refines an infeasible model by examining elements that can be removed from the conflict to arrive at a minimal conflict. A conflict smaller than the full model may make it easier for the user to analyze the source of infeasibilities in the original model.

Taken from the CPLEX documentation.

share|improve this answer

answered 7 hours ago

Kevin DalmeijerKevin Dalmeijer

1,59944 silver badges2222 bronze badges

$endgroup$

share|improve this answer

answered 7 hours ago

Kevin DalmeijerKevin Dalmeijer

1,59944 silver badges2222 bronze badges

answered 7 hours ago

Kevin DalmeijerKevin Dalmeijer

1,59944 silver badges2222 bronze badges

answered 7 hours ago

Kevin DalmeijerKevin Dalmeijer

1,59944 silver badges2222 bronze badges

3

$begingroup$

Related to @Kevin Dalmeijer's answer, Gurobi offers Irreducible Inconsistent Subsystem functionality via Model.computeIIS():

Compute an Irreducible Inconsistent Subsystem (IIS). An IIS is a subset of the constraints and variable bounds with the following properties:

• the subsystem represented by the IIS is infeasible, and




• if any of the constraints or bounds of the IIS is removed, the subsystem becomes feasible.

Note that an infeasible model may have multiple IISs. The one returned by Gurobi is not necessarily the one with minimum cardinality; there may exist others with fewer constraints or bounds.

share|improve this answer

answered 6 hours ago

dxbdxb

81333 silver badges1414 bronze badges

$endgroup$

add a comment | 

3

$begingroup$

Related to @Kevin Dalmeijer's answer, Gurobi offers Irreducible Inconsistent Subsystem functionality via Model.computeIIS():

Compute an Irreducible Inconsistent Subsystem (IIS). An IIS is a subset of the constraints and variable bounds with the following properties:

• the subsystem represented by the IIS is infeasible, and




• if any of the constraints or bounds of the IIS is removed, the subsystem becomes feasible.

Note that an infeasible model may have multiple IISs. The one returned by Gurobi is not necessarily the one with minimum cardinality; there may exist others with fewer constraints or bounds.

share|improve this answer

answered 6 hours ago

dxbdxb

81333 silver badges1414 bronze badges

$endgroup$

add a comment | 

$begingroup$

Related to @Kevin Dalmeijer's answer, Gurobi offers Irreducible Inconsistent Subsystem functionality via Model.computeIIS():

Compute an Irreducible Inconsistent Subsystem (IIS). An IIS is a subset of the constraints and variable bounds with the following properties:

• the subsystem represented by the IIS is infeasible, and




• if any of the constraints or bounds of the IIS is removed, the subsystem becomes feasible.

Note that an infeasible model may have multiple IISs. The one returned by Gurobi is not necessarily the one with minimum cardinality; there may exist others with fewer constraints or bounds.

share|improve this answer

answered 6 hours ago

dxbdxb

81333 silver badges1414 bronze badges

$endgroup$

share|improve this answer

answered 6 hours ago

dxbdxb

81333 silver badges1414 bronze badges

answered 6 hours ago

dxbdxb

81333 silver badges1414 bronze badges

answered 6 hours ago

dxbdxb

81333 silver badges1414 bronze badges

1

$begingroup$

Here is a good (but a little bit old) paper[1] discussing the algorithmic approaches to identify and manage the infeasibility situation in MIPs and IPs.

[1] Guieu, Olivier, and John W. Chinneck. "Analyzing infeasible mixed-integer and integer linear programs." INFORMS Journal on Computing 11.1 (1999): 63-77.

share|improve this answer

answered 7 hours ago

Oguz ToragayOguz Toragay

1,95822 silver badges2222 bronze badges

$endgroup$

add a comment | 

1

$begingroup$

Here is a good (but a little bit old) paper[1] discussing the algorithmic approaches to identify and manage the infeasibility situation in MIPs and IPs.

[1] Guieu, Olivier, and John W. Chinneck. "Analyzing infeasible mixed-integer and integer linear programs." INFORMS Journal on Computing 11.1 (1999): 63-77.

share|improve this answer

answered 7 hours ago

Oguz ToragayOguz Toragay

1,95822 silver badges2222 bronze badges

$endgroup$

add a comment | 

$begingroup$

Here is a good (but a little bit old) paper[1] discussing the algorithmic approaches to identify and manage the infeasibility situation in MIPs and IPs.

[1] Guieu, Olivier, and John W. Chinneck. "Analyzing infeasible mixed-integer and integer linear programs." INFORMS Journal on Computing 11.1 (1999): 63-77.

share|improve this answer

answered 7 hours ago

Oguz ToragayOguz Toragay

1,95822 silver badges2222 bronze badges

$endgroup$

share|improve this answer

answered 7 hours ago

Oguz ToragayOguz Toragay

1,95822 silver badges2222 bronze badges

answered 7 hours ago

Oguz ToragayOguz Toragay

1,95822 silver badges2222 bronze badges

answered 7 hours ago

Oguz ToragayOguz Toragay

1,95822 silver badges2222 bronze badges

1

$begingroup$

On top of getting IIS from the solver and using slack variables (as suggested by other answers), one more thing that you can do for debugging purposes is to fix your variables to a known feasible solution and see what is reported from your model. Doing that, you can figure out what has happened to make the problem infeasible.

For example, assume you have $x_1 +x_2 = 10$ constraint and a known feasible solution is $x_1 = 6, x_2 = 2$, you can see the infeasibility and the constraint that throws the infeasibility.

share|improve this answer

answered 6 hours ago

EhsanKEhsanK

1,95933 silver badges2929 bronze badges

$endgroup$

add a comment | 

1

$begingroup$

On top of getting IIS from the solver and using slack variables (as suggested by other answers), one more thing that you can do for debugging purposes is to fix your variables to a known feasible solution and see what is reported from your model. Doing that, you can figure out what has happened to make the problem infeasible.

For example, assume you have $x_1 +x_2 = 10$ constraint and a known feasible solution is $x_1 = 6, x_2 = 2$, you can see the infeasibility and the constraint that throws the infeasibility.

share|improve this answer

answered 6 hours ago

EhsanKEhsanK

1,95933 silver badges2929 bronze badges

$endgroup$

add a comment | 

$begingroup$

On top of getting IIS from the solver and using slack variables (as suggested by other answers), one more thing that you can do for debugging purposes is to fix your variables to a known feasible solution and see what is reported from your model. Doing that, you can figure out what has happened to make the problem infeasible.

For example, assume you have $x_1 +x_2 = 10$ constraint and a known feasible solution is $x_1 = 6, x_2 = 2$, you can see the infeasibility and the constraint that throws the infeasibility.

share|improve this answer

answered 6 hours ago

EhsanKEhsanK

1,95933 silver badges2929 bronze badges

$endgroup$

share|improve this answer

answered 6 hours ago

EhsanKEhsanK

1,95933 silver badges2929 bronze badges

answered 6 hours ago

EhsanKEhsanK

1,95933 silver badges2929 bronze badges

answered 6 hours ago

EhsanKEhsanK

1,95933 silver badges2929 bronze badges