JuMP function result_count returns 1 when infinite solutions possible, which solver to use?

Specific Domains Optimization (Mathematical)
1

Consider the following model of a simple LP problem:

using JuMP, HiGHS

m = Model(HiGHS.Optimizer)

@variable(m, x1 >= 0)  
@variable(m, x2 <= 0) 
@objective(m, Max, 2x1-x2) 
@constraint(m, c1, 8x1-4x2<=16) 
@constraint(m, c2, 3x1-4x2<=12)  

print(m)
#Max 2 x1 - x2
#Subject to
# c1 : 8 x1 - 4 x2 <= 16.0
# c2 : 3 x1 - 4 x2 <= 12.0
# x1 >= 0.0
# x2 <= 0.0

JuMP.optimize!(m)
#Running HiGHS 1.4.2 [date: 1970-01-01, git hash: f797c1ab6]
#Copyright (c) 2022 ERGO-Code under MIT licence terms       
#Presolving model
#2 rows, 2 cols, 4 nonzeros
#2 rows, 2 cols, 4 nonzeros
#Presolve : Reductions: rows 2(-0); columns 2(-0); elements 4(-0) - Not reduced
#Problem not reduced by presolve: solving the LP
#Using EKK dual simplex solver - serial
# Iteration        Objective     Infeasibilities num(sum)
#          0    -7.4999893425e-01 Ph1: 2(4.75); Du: 2(0.749999) 0s 
#          1     4.0000000000e+00 Pr: 0(0) 0s
#Model   status      : Optimal
#Simplex   iterations: 1
#Objective value     :  4.0000000000e+00
#HiGHS run time      :          0.02

result_count(m)
# 1

println("Objective value: ", JuMP.objective_value(m))
# Objective value: 4.0

solution_summary(m)
#* Solver : HiGHS
#
#* Status
# Result count       : 1
# Termination status : OPTIMAL
# Message from the solver:
#  "kHighsModelStatusOptimal"
#
#* Candidate solution (result #1)
# Primal status      : FEASIBLE_POINT
# Dual status        : FEASIBLE_POINT
#  Objective value    : 4.00000e+00
#  Objective bound    : 4.00000e+00
# Relative gap       : Inf
#  Dual objective value : 4.00000e+00
#
#* Work counters
#  Solve time (sec)   : 1.56868e-02
#  Simplex iterations : 1
#  Barrier iterations : 0
#  Node count         : -1

println("x1 = ", JuMP.value(x1))
# x1 = 2.0

println("x2 = ", JuMP.value(x2))
# x2 = 0.0

The JuMP solution shows there was a optimal (understanding global) solution found however if you consider the solution (x1,x2)=(1, -2) then it satisfies as well the constraints and produces the same objective value of 4, clearly multiple slutions are possible

The JuMP result count is 1 and termination status reports optimality. Is it because I defined the problem as LP and not as MILP, and some computational inacuracies show, that it does not report the multiple solutions?

2

Since the objective gradient and the gradient of c1 are parallel, a whole face of the polytope is composed of minima. So there’s infinitely many of them :wink: An LP solver can return any of them (if you tried an interior-point method, you could get a non-corner solution). It’s up to you to analyze the results and perhaps modify your model if you’re not happy with the solution.

1 Like
3

I understand.

How would i go About extracting the info about the gradients of objective and constraint parallelism from the JuMP Interface explicitly?

I thought this kind of solution will be given by infinite number of solutions as output of the model.