Ask Your Question

Revision history [back]

A linear program return infeasible but I think to know a feasible solution.

I have the following linear programming program which is solved without problem by SageMath.

   nv=6 #nombre de contraintes
mv=4 #nombre de variables
F=10
a=1.5
Av= matrix(RR,nv,mv,[1,0,0,0,
                     0,1,0,0,
                     0,0,1,0,
                     0,0,0,1,
                     1,1,1,1,
                     1,-a,0,-a])     #les coefficients
bvmin=vector(RR,[3/20*F,3/20*F,11/40*F,3/20*F,17/20*F,0]) #les bornes inférieures pour les contraintes
bvmax=vector(RR,[9/20*F,9/20*F,9/20*F,9/20*F,17/20*F,9/20*F]) #les bornes supérieures pour les contraintes
show(LatexExpr('A='),Av)
show(LatexExpr('bmin='),bvmin)
show(LatexExpr('bmax='),bvmax)
#Création du programme
v=MixedIntegerLinearProgram(maximization=True, solver='GLPK') 
#On pose les nouvelles variables allant de x_0 à x_5
ind=[0..mv-1]
x=v.new_variable(integer=False,indices=ind) 
#On utilise la fonction linéaire pour les contraintes
Bv=Av*x
#On fixe l'objectif
v.set_objective(x[0])
for i in range(mv) :
    v.set_min(x[i],0)
    v.set_max(x[i],F)
for i in range(0,nv-1):
    v.add_constraint(Bv[i],min=bvmin[i], max=bvmax[i])    
v.show()
v.solve()
xx=v.get_values(x)
show(xx)

Now I want to change the objective to $maxmin(x_0,x_1,x_2,x_3)$. So I follow the usual approach which leads to the addition of a variable says $x_4$ and four new constraints $x_0\geq x_4$,$x_1\geq x_4$,$x_2\geq x_4$ and $x_3 \geq x_4$ as in the following code.

nv=10 #nombre de contraintes
mv=5 #nombre de variables
F=10
a=1.5
Av= matrix(RR,nv,mv,[1,0,0,0,0,
                     0,1,0,0,0,
                     0,0,1,0,0,
                     0,0,0,1,0,
                     1,1,1,1,0,
                     1,-a,0,-a,0,
                     1,0,0,0,-1,
                     0,1,0,0,-1,
                     0,0,1,0,-1,
                     0,0,0,1,-1])     #les coefficients
bvmin=vector(RR,[3/20*F,3/20*F,11/40*F,3/20*F,17/20*F,0,0,0,0,0]) #les bornes inférieures pour les contraintes
bvmax=vector(RR,[9/20*F,9/20*F,9/20*F,9/20*F,17/20*F,9/20*F,F,F,F,F]) #les bornes supérieures pour les contraintes
show(LatexExpr('A='),Av)
show(LatexExpr('bmin='),bvmin)
show(LatexExpr('bmax='),bvmax)
#Création du programme
v=MixedIntegerLinearProgram(maximization=True, solver='GLPK') 
#On pose les nouvelles variables allant de x_0 à x_5
ind=[0..mv-1]
x=v.new_variable(integer=False,indices=ind) 
#On utilise la fonction linéaire pour les contraintes
Bv=Av*x
#On fixe l'objectif
v.set_objective(x[4])
for i in range(mv) :
    v.set_min(x[i],0)
    v.set_max(x[i],F)
for i in range(0,nv):
    v.add_constraint(Bv[i],min=bvmin[i], max=bvmax[i])    
v.show()
v.solve()
xx=v.get_values(x)
show(xx)

But this time Sagemath return an infeasability of this program. What bother me is that if I set $x_4$ to the minimum value of the former program and use the optimal solution in this second program, I have a perfectly feasible solution.

I do not know where is the problem : a misunderstanding, Glpk (normaly it's a sure program.....). I am not certain that is a true Sagemath question...

A linear program return infeasible but I think to know a feasible solution.

I have the following linear programming program which is solved without problem by SageMath.

   nv=6 #nombre de contraintes
mv=4 #nombre de variables
F=10
a=1.5
Av= matrix(RR,nv,mv,[1,0,0,0,
                     0,1,0,0,
                     0,0,1,0,
                     0,0,0,1,
                     1,1,1,1,
                     1,-a,0,-a])     #les coefficients
bvmin=vector(RR,[3/20*F,3/20*F,11/40*F,3/20*F,17/20*F,0]) #les bornes inférieures pour les contraintes
bvmax=vector(RR,[9/20*F,9/20*F,9/20*F,9/20*F,17/20*F,9/20*F]) #les bornes supérieures pour les contraintes
show(LatexExpr('A='),Av)
show(LatexExpr('bmin='),bvmin)
show(LatexExpr('bmax='),bvmax)
#Création du programme
v=MixedIntegerLinearProgram(maximization=True, solver='GLPK') 
#On pose les nouvelles variables allant de x_0 à x_5
ind=[0..mv-1]
x=v.new_variable(integer=False,indices=ind) 
#On utilise la fonction linéaire pour les contraintes
Bv=Av*x
#On fixe l'objectif
v.set_objective(x[0])
for i in range(mv) :
    v.set_min(x[i],0)
    v.set_max(x[i],F)
for i in range(0,nv-1):
    v.add_constraint(Bv[i],min=bvmin[i], max=bvmax[i])    
v.show()
v.solve()
xx=v.get_values(x)
show(xx)

Now I want to change the objective to $maxmin(x_0,x_1,x_2,x_3)$. So I follow the usual approach which leads to the addition of a variable says $x_4$ and four new constraints $x_0\geq x_4$,$x_1\geq x_4$,$x_2\geq x_4$ and $x_3 \geq x_4$ as in the following code.

nv=10 #nombre de contraintes
mv=5 #nombre de variables
F=10
a=1.5
Av= matrix(RR,nv,mv,[1,0,0,0,0,
                     0,1,0,0,0,
                     0,0,1,0,0,
                     0,0,0,1,0,
                     1,1,1,1,0,
                     1,-a,0,-a,0,
                     1,0,0,0,-1,
                     0,1,0,0,-1,
                     0,0,1,0,-1,
                     0,0,0,1,-1])     #les coefficients
bvmin=vector(RR,[3/20*F,3/20*F,11/40*F,3/20*F,17/20*F,0,0,0,0,0]) #les bornes inférieures pour les contraintes
bvmax=vector(RR,[9/20*F,9/20*F,9/20*F,9/20*F,17/20*F,9/20*F,F,F,F,F]) #les bornes supérieures pour les contraintes
show(LatexExpr('A='),Av)
show(LatexExpr('bmin='),bvmin)
show(LatexExpr('bmax='),bvmax)
#Création du programme
v=MixedIntegerLinearProgram(maximization=True, solver='GLPK') 
#On pose les nouvelles variables allant de x_0 à x_5
ind=[0..mv-1]
x=v.new_variable(integer=False,indices=ind) 
#On utilise la fonction linéaire pour les contraintes
Bv=Av*x
#On fixe l'objectif
v.set_objective(x[4])
for i in range(mv) :
    v.set_min(x[i],0)
    v.set_max(x[i],F)
for i in range(0,nv):
    v.add_constraint(Bv[i],min=bvmin[i], max=bvmax[i])    
v.show()
v.solve()
xx=v.get_values(x)
show(xx)

But this time Sagemath return an infeasability of this program. What bother me is that if I set $x_4$ to the minimum value of the former program and use the optimal solution in this second program, I have a perfectly feasible solution.

I do not know where is the problem : a misunderstanding, Glpk (normaly it's a sure program.....). I am not certain that is a true Sagemath question...

A linear program return returns infeasible but I think to know a feasible solution.

I have the following linear programming program which is solved without problem by SageMath.

   nv=6 #nombre de contraintes
mv=4 #nombre de variables
F=10
a=1.5
Av= matrix(RR,nv,mv,[1,0,0,0,
                     0,1,0,0,
                     0,0,1,0,
                     0,0,0,1,
                     1,1,1,1,
                     1,-a,0,-a])     #les coefficients
bvmin=vector(RR,[3/20*F,3/20*F,11/40*F,3/20*F,17/20*F,0]) #les bornes inférieures pour les contraintes
bvmax=vector(RR,[9/20*F,9/20*F,9/20*F,9/20*F,17/20*F,9/20*F]) #les bornes supérieures pour les contraintes
show(LatexExpr('A='),Av)
show(LatexExpr('bmin='),bvmin)
show(LatexExpr('bmax='),bvmax)
#Création du programme
v=MixedIntegerLinearProgram(maximization=True, solver='GLPK') 
#On pose les nouvelles variables allant de x_0 à x_5
ind=[0..mv-1]
x=v.new_variable(integer=False,indices=ind) 
#On utilise la fonction linéaire pour les contraintes
Bv=Av*x
#On fixe l'objectif
v.set_objective(x[0])
for i in range(mv) :
    v.set_min(x[i],0)
    v.set_max(x[i],F)
for i in range(0,nv-1):
    v.add_constraint(Bv[i],min=bvmin[i], max=bvmax[i])    
v.show()
v.solve()
xx=v.get_values(x)
show(xx)

Now I want to change the objective to $maxmin(x_0,x_1,x_2,x_3)$. So I follow the usual approach which leads to the addition of a variable says $x_4$ and four new constraints $x_0\geq x_4$,$x_1\geq x_4$,$x_2\geq x_4$ and $x_3 \geq x_4$ as in the following code.

nv=10 #nombre de contraintes
mv=5 #nombre de variables
F=10
a=1.5
Av= matrix(RR,nv,mv,[1,0,0,0,0,
                     0,1,0,0,0,
                     0,0,1,0,0,
                     0,0,0,1,0,
                     1,1,1,1,0,
                     1,-a,0,-a,0,
                     1,0,0,0,-1,
                     0,1,0,0,-1,
                     0,0,1,0,-1,
                     0,0,0,1,-1])     #les coefficients
bvmin=vector(RR,[3/20*F,3/20*F,11/40*F,3/20*F,17/20*F,0,0,0,0,0]) #les bornes inférieures pour les contraintes
bvmax=vector(RR,[9/20*F,9/20*F,9/20*F,9/20*F,17/20*F,9/20*F,F,F,F,F]) #les bornes supérieures pour les contraintes
show(LatexExpr('A='),Av)
show(LatexExpr('bmin='),bvmin)
show(LatexExpr('bmax='),bvmax)
#Création du programme
v=MixedIntegerLinearProgram(maximization=True, solver='GLPK') 
#On pose les nouvelles variables allant de x_0 à x_5
ind=[0..mv-1]
x=v.new_variable(integer=False,indices=ind) 
#On utilise la fonction linéaire pour les contraintes
Bv=Av*x
#On fixe l'objectif
v.set_objective(x[4])
for i in range(mv) :
    v.set_min(x[i],0)
    v.set_max(x[i],F)
for i in range(0,nv):
    v.add_constraint(Bv[i],min=bvmin[i], max=bvmax[i])    
v.show()
v.solve()
xx=v.get_values(x)
show(xx)

But this time Sagemath return an infeasability of this program. What bother me is that if I set $x_4$ to the minimum value of the former program and use the optimal solution in this second program, I have a perfectly feasible solution.

I do not know where is the problem : a misunderstanding, Glpk (normaly it's a sure program.....). I am not certain that is a true Sagemath question...

I will add that I have changed the objective of the first program from x[0] to x[1], x[2] and x[3]. In all cases I find a solution. Of course in all those solutions the min of x[i] is always the same. But I am not sure that can explain anything.

click to hide/show revision 4
retagged

updated 2023-05-19 22:07:02 +0100

FrédéricC gravatar image

A linear program returns infeasible but I think to know a feasible solution.

I have the following linear programming program which is solved without problem by SageMath.

   nv=6 #nombre de contraintes
mv=4 #nombre de variables
F=10
a=1.5
Av= matrix(RR,nv,mv,[1,0,0,0,
                     0,1,0,0,
                     0,0,1,0,
                     0,0,0,1,
                     1,1,1,1,
                     1,-a,0,-a])     #les coefficients
bvmin=vector(RR,[3/20*F,3/20*F,11/40*F,3/20*F,17/20*F,0]) #les bornes inférieures pour les contraintes
bvmax=vector(RR,[9/20*F,9/20*F,9/20*F,9/20*F,17/20*F,9/20*F]) #les bornes supérieures pour les contraintes
show(LatexExpr('A='),Av)
show(LatexExpr('bmin='),bvmin)
show(LatexExpr('bmax='),bvmax)
#Création du programme
v=MixedIntegerLinearProgram(maximization=True, solver='GLPK') 
#On pose les nouvelles variables allant de x_0 à x_5
ind=[0..mv-1]
x=v.new_variable(integer=False,indices=ind) 
#On utilise la fonction linéaire pour les contraintes
Bv=Av*x
#On fixe l'objectif
v.set_objective(x[0])
for i in range(mv) :
    v.set_min(x[i],0)
    v.set_max(x[i],F)
for i in range(0,nv-1):
    v.add_constraint(Bv[i],min=bvmin[i], max=bvmax[i])    
v.show()
v.solve()
xx=v.get_values(x)
show(xx)

Now I want to change the objective to $maxmin(x_0,x_1,x_2,x_3)$. So I follow the usual approach which leads to the addition of a variable says $x_4$ and four new constraints $x_0\geq x_4$,$x_1\geq x_4$,$x_2\geq x_4$ and $x_3 \geq x_4$ as in the following code.

nv=10 #nombre de contraintes
mv=5 #nombre de variables
F=10
a=1.5
Av= matrix(RR,nv,mv,[1,0,0,0,0,
                     0,1,0,0,0,
                     0,0,1,0,0,
                     0,0,0,1,0,
                     1,1,1,1,0,
                     1,-a,0,-a,0,
                     1,0,0,0,-1,
                     0,1,0,0,-1,
                     0,0,1,0,-1,
                     0,0,0,1,-1])     #les coefficients
bvmin=vector(RR,[3/20*F,3/20*F,11/40*F,3/20*F,17/20*F,0,0,0,0,0]) #les bornes inférieures pour les contraintes
bvmax=vector(RR,[9/20*F,9/20*F,9/20*F,9/20*F,17/20*F,9/20*F,F,F,F,F]) #les bornes supérieures pour les contraintes
show(LatexExpr('A='),Av)
show(LatexExpr('bmin='),bvmin)
show(LatexExpr('bmax='),bvmax)
#Création du programme
v=MixedIntegerLinearProgram(maximization=True, solver='GLPK') 
#On pose les nouvelles variables allant de x_0 à x_5
ind=[0..mv-1]
x=v.new_variable(integer=False,indices=ind) 
#On utilise la fonction linéaire pour les contraintes
Bv=Av*x
#On fixe l'objectif
v.set_objective(x[4])
for i in range(mv) :
    v.set_min(x[i],0)
    v.set_max(x[i],F)
for i in range(0,nv):
    v.add_constraint(Bv[i],min=bvmin[i], max=bvmax[i])    
v.show()
v.solve()
xx=v.get_values(x)
show(xx)

But this time Sagemath return an infeasability of this program. What bother me is that if I set $x_4$ to the minimum value of the former program and use the optimal solution in this second program, I have a perfectly feasible solution.

I do not know where is the problem : a misunderstanding, Glpk (normaly it's a sure program.....). I am not certain that is a true Sagemath question...

I will add that I have changed the objective of the first program from x[0] to x[1], x[2] and x[3]. In all cases I find a solution. Of course in all those solutions the min of x[i] is always the same. But I am not sure that can explain anything.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59