[Cbc] Artificial variables

[Ted Ralphs]

The "1 infeasibility" means (as far as I can tell) simply that there was
only variable for which the implied bounds lead to infeasibility. However,
the implied bounds on the single variable could have arisen from any one or
some combination of multiple constraints. Commercial solvers, such as
CPLEX, will determine IIS's for you automatically (using a heuristic).

Just to follow up with more references, here is a whole book on the topic
of infeasibility:

http://www.amazon.com/Feasibility-Infeasibility-Optimization-Computational-International/dp/0387749314

Just looking at the first few pages will give you some ideas. If you check
the authors home page, you will find papers and other materials. Another
group that has done a lot of work in this area is Edoardo Amaldi et al.
This paper here contains a good overview and summary of what is known:

http://www.cs.elte.hu/~illes/Tantargyak/.../Cikkek-1/MP-03-*IIS*.pdf

You can try adding a slack variable to every constraint that represents the
degree of violation of that constraint and then try to minimize the sum of
infeasibilities, for example. You could also associate these with binary
variables and in a similar fashion try to determine the smallest number of
constraints that can be violated and still maintain feasibility. This
would, of course be a rather large (and probably difficult_ integer
program, but formulating it would be easy and you might find a good
heuristic solution fairly quickly.

Good luck!

Ted

On Fri, Aug 10, 2012 at 4:04 PM, Christos <chtsolak at gmail.com> wrote:

>  Your info was proved to be very useful!
>
> Is there any possibility the infeasibility to be caused from another
> reason other than that you mentioned? (upper bound<lower bound),
>
> and the "1 infeasibility" message means that there is problem only with
> one number in the problem?
>
> I am reading many of the articles and hope to find a solution soon..
>
> Your help is much appreciated!
>
>
>
> On 10/8/2012 20:05, Ted Ralphs wrote:
>
> As far as I can tell from the output and from a brief perusal of the
> source, the model is being found infeasible by the pre-solve during the
> process of tightening bounds. In a nutshell, the solver tries to determine
> if there are "implied bounds" for any of the variables that are tighter
> than the ones actually given in the problem description. The logic is that
> if you have, e.g.,
>
> x1 + x2 <=1
>
> and x1 and x2 are non-negative variables, then they each have an implied
> upper bound of 1, even if this is not given as part of the input. You can
> get implied bounds from the each constraint for each variable and these can
> be tightened in multiple rounds---one round of tightening leads to further
> implications in the next round. If the result of this tightening is that
> the lower bound of a given variable ends up higher than its upper bound,
> the model is infeasible. As far as I can tell, the number that is being
> reported there is the number of such violations, but to be honest, this
> number is very hard to interpret. The single infeasibility could have been
> caused by any number of the actual linear constraints.
>
> Determining what constraints are causing infeasibility is a difficult
> problem in general and has been the subject of much research. A good place
> to start to find out about this area is to put "irreducible inconsistent
> system" in Google Scholar:
>
> http://goo.gl/qdqyU
>
> Cheers,
>
> Ted
>
> On Fri, Aug 10, 2012 at 12:37 PM, Christos <chtsolak at gmail.com> wrote:
>
>>  I forgot to mention that it is a minimization problem , so i do not
>> know if there is any point in limiting objective.
>>
>> Sorry for the double mail.
>>
>>
>> On 10/8/2012 19:24, acw at ascent.com wrote:
>>
>> No single constraint is responsible for an infeasibility.  Consider a
>> system with one variable, and two constraints, X >= 7 and X <= 4.  This
>> system is obviously infeasible, but which of the two constraints is at
>> fault?
>>
>> In your case I suspect that the problem is unbounded rather than
>> infeasible, because you have so few constraints and so many variables.
>>  Unless the problem has a very special structure, a problem with fewer
>> constraints than variables is likely to be unbounded.
>>
>> You can check this by adding a constraint that limits your objective to,
>> say, 1e6.  If the problem now solves, then unboundedness is almost
>> certainly your difficulty.
>>
>>
>>   From: Christos <chtsolak at gmail.com> <chtsolak at gmail.com>  To:
>> cbc at list.coin-or.org  Date: 08/10/2012 09:32 AM  Subject: [Cbc]
>> Artificial variables
>> ------------------------------
>>
>>
>>
>> Hi, i have a model with around 10000 variable and 1500 equations.
>>
>> But i get the messages on the photo when i run it:
>> http://imageshack.us/photo/my-images/39/dascd.png/
>>
>> Is there any way to use artificial variable or something else in order
>> to find the problematic equation?
>>
>> Thank you in advance
>> _______________________________________________
>> Cbc mailing list
>> Cbc at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/cbc
>>
>>
>>
>> _______________________________________________
>> Cbc mailing list
>> Cbc at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/cbc
>>
>>
>
>
> --
> Dr. Ted Ralphs
> Associate Professor, Lehigh University
> (610) 628-1280
> ted 'at' lehigh 'dot' edu
> coral.ie.lehigh.edu/~ted <http://coral.ie.lehigh.edu/%7Eted>
>
>
>


-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted <http://coral.ie.lehigh.edu/%7Eted>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/cbc/attachments/20120810/cb0481bb/attachment-0001.html>