# Simplifying LP for repeated resolving

**URL:** <https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528>\
**Category:** Optimization (Mathematical)\
**Tags:** jump\
**Created:** [April 16, 2023, 12:25am UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528 "2023-04-16T00:25:31Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![mikel8](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@mikel8](https://discourse.julialang.org/u/mikel8)\
**Post date:** [April 16, 2023, 12:25am UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/1 "2023-04-16T00:25:31Z")

</div>

Hi all,  
I’m working on a problem that requires repeated resolving of a large LP with different objectives. The methodology I’m working on involves solving a first problem to optimality, then imposing an epsilon constraint before repeatedly reoptimizing with varied objective statements to explore the near-optimal feasible space. I thought that one way to simplify the problem might be to remove redundant constraints that do not intersect with the newly epsilon constrained feasible region. I haven’t found a good way to ask a solver to look for redundant constraints yet.

Do you all have any suggestions as to packages or functions that might be useful?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [April 16, 2023, 5:52pm UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/2 "2023-04-16T17:52:35Z")

</div>

Not sure it helps, but the epsilon-constrained feasible region is itself a polytope P\_\varepsilon = \{x \in P: c^\top x \leq c^\top x^\star + \varepsilon\}  
And deciding whether a constraint a^\top x \leq b intersects P\_\varepsilon is as hard as solving the linear program \max\_{x \in P\_\varepsilon} a^\top x.  
Of course you can take advantage of the previous optimal solution x^\star as a starting point within P\_\varepsilon, but eliminating redundant constraints manually like this may not be a piece of cake.

That being said, I think many solvers include constraint elimination subroutines, so maybe it is possible without getting your hands too dirty?

---

<div class="post-metadata">

**Author:** ![mikel8](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@mikel8](https://discourse.julialang.org/u/mikel8)\
**Post date:** [April 16, 2023, 6:42pm UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/3 "2023-04-16T18:42:10Z")

</div>

Thanks for the thoughts! Yes, I’m aware it’s an equally hard problem, I suppose I was hoping that passing some form of presolved/reduced form model with redundant constraints eliminated to the solver in the repeated solving stage might offer at least some returns on solution times, given that I’m resolving that problem somewhere in the hundreds to thousands of times. I’ve tried utilizing CPLEX presolves, but as the presolve routines eliminate more than just redundant constraints depending on the objective function in use, it doesn’t seem to necessarily be helpful. Warmstarting with x\* is an idea I’ve toyed around with as well, but because the goal of the routine is to get maximally different solutions, it seems to be somewhat contradictory to warm-start. Do you think warm-starting would still have some benefits despite that?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [April 16, 2023, 7:25pm UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/4 "2023-04-16T19:25:34Z")

</div>

I guess you could always warm start and include a penalty for proximity to x^\star?

---

<div class="post-metadata">

**Author:** ![mikel8](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@mikel8](https://discourse.julialang.org/u/mikel8)\
**Post date:** [April 16, 2023, 8:29pm UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/5 "2023-04-16T20:29:50Z")

</div>

I think, depending on the method of choosing the objective function in the problem at hand, the warm start will be more or less valuable. I don’t think the penalty is necessary as we can conceptually rule out certain approaches from warmstarting, while endorsing others. Thanks so much for your help! Unfortunate that there’s doesn’t seem to be a better way to reduce the computational complexity of the problem though.

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [April 16, 2023, 8:57pm UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/6 "2023-04-16T20:57:44Z")

</div>

See

- [GitHub - jump-dev/MultiObjectiveAlgorithms.jl](https://github.com/jump-dev/MultiObjectiveAlgorithms.jl)
- [Simple multi-objective examples · JuMP](https://jump.dev/JuMP.jl/stable/tutorials/linear/multi_objective_examples/)
- [Multi-objective knapsack · JuMP](https://jump.dev/JuMP.jl/stable/tutorials/linear/multi_objective_knapsack/)

The `MOA.EpsilonConstraint` algorithm in MOA preserves the presolved model in memory, enabling efficient warm-starts. You don’t need to do this manually.

---

<div class="post-metadata">

**Author:** ![mikel8](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@mikel8](https://discourse.julialang.org/u/mikel8)\
**Post date:** [April 16, 2023, 11:17pm UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/7 "2023-04-16T23:17:57Z")

</div>

Thanks! Very cool that this is implemented. It’s not a perfect fit for my problem as it is limited to a couple objectives (as far as I can see), whereas I am looking at somewhere between several hundred and several thousand objectives. Do you have any tips on implementing preserving the presolved model in memory so that I can put it in my own code?

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [April 16, 2023, 11:50pm UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/8 "2023-04-16T23:50:54Z")

</div>

> Do you have any tips on implementing preserving the presolved model in memory so that I can put it in my own code?

JuMP will automatically keep the model in memory if you use modifications. So this will work:

```julia
using JuMP, HiGHS
n, o = 20, 10
weights = rand(n)
C = rand(o, n)
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, x[1:n] >= 0)
@constraint(model, weights' * x <= n / 3)
@expression(model, c, C * x)
for i in 1:o
    @objective(model, Max, c[i])
    optimize!(model)
    @constraint(model, c[i] >= 0.9 * objective_value(model))
end
optimize!(model)
value.(x)

```

This algorithm is already implemented in MOA:

```julia
import MultiObjectiveAlgorithms as MOA
model = Model(() -> MOA.Optimizer(HiGHS.Optimizer))
set_attribute(model, MOA.Algorithm(), MOA.Hierarchical())
for i in 1:o
    set_attribute(model, MOA.ObjectiveRelativeTolerance(i), 0.1)
    set_attribute(model, MOA.ObjectivePriority(i), o - i)
end
set_silent(model)
@variable(model, x[1:n] >= 0)
@constraint(model, weights' * x <= n / 3)
@objective(model, Max, C * x)
optimize!(model)
value.(x)

```

> [@mikel8](#):
>
> I am looking at somewhere between several hundred and several thousand objectives

Are you sure the problem makes sense to solve, and the solutions make sense to interpret? By the time you’ve solved the first few objectives, there is probably very little freedom in how the solution can adapt to the remaining hundreds of objectives.

---

<div class="post-metadata">

**Author:** ![mikel8](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@mikel8](https://discourse.julialang.org/u/mikel8)\
**Post date:** [April 17, 2023, 1:46am UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/9 "2023-04-17T01:46:18Z")

</div>

Great, that’s what I’m already doing. Glad to hear it works as well as it can. Yes, it’s for an application involving very high dimensional polytopes with significant feasible space that I’m looking to explore as well as I can. Appreciate the help!

---

<div class="post-metadata">

**Author:** ![mtanneau](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mtanneau/32/17787_2.png) [@mtanneau](https://discourse.julialang.org/u/mtanneau)\
**Post date:** [April 17, 2023, 11:46pm UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/10 "2023-04-17T23:46:14Z")

</div>

## About

I highly recommend [this section of the Gurobi docs](https://www.gurobi.com/documentation/9.5/refman/working_with_multiple_obje.html), especially the last paragraph of the “Allowing Multiple-Objective Degradation” section.  
In a nutshell: to prevent degradation of the objective value, instead of adding an objective constraint, it is typically more efficient to use reduced cost information to force non-basic variables (with non-zero reduced cost) to stay at zero.

## About presolve

LP solvers use two types of reductions in presolve: primal and dual reductions.

- _Primal reductions_ only use information from constraints, and keep the feasible set unchanged. For instance, if you have a constraint x = 1, you can remove variable x from the problem.
- _Dual reductions_ use information from constraints _and_ the objective. While they may remove feasible solution, they are guaranteed to retain at least one optimal solution.  
For instance, suppose you have a variable x \geq 0 that appears in no constraint and has an objective coefficient of 1. It is straightforward to show that any optimal solution will have x = 0, so the solver goes ahead and eliminates x. Of course, this reduction is not valid if, say, the objective coefficient had been -1.

In your setting, after you’ve added the objective constraint, you are repeatedly solving an LP with identical constraints but different objectives.

- To avoid having the solver discard the presolved model at each iteration, you should disable dual reductions at presolve. Not all solvers support doing that, but Gurobi (and likely other mainstream solvers) does (see [Gurobi’s docs](https://www.gurobi.com/documentation/9.5/refman/dualreductions.html#parameter:DualReductions)).
- Make sure to use primal simplex by setting [the `Method` parameter](https://www.gurobi.com/documentation/9.5/refman/method.html) to `0`. This will ensure that you can re-use the previous solution as warm-start.

If you look at the log, you should see two things:

- no presolve after the second solve
- the number of iterations at the second solve is much smaller

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [April 18, 2023, 12:30am UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/11 "2023-04-18T00:30:17Z")

</div>

> [@mtanneau](#):
>
> In a nutshell: to prevent degradation of the objective value, instead of adding an objective constraint, it is typically more efficient to use reduced cost information to force non-basic variables (with non-zero reduced cost) to stay at zero.

This is complicated to do from JuMP, which is why I didn’t suggest it.

I doubt that there’s much of a problem with the constraint generation approach.

You could always do this, which may be faster for very large problems:

```julia
using JuMP, HiGHS
n, o = 20, 10
weights = rand(n)
C = rand(o, n)
model = Model(HiGHS.Optimizer)
set_silent(model)
@variable(model, x[1:n] >= 0)
@variable(model, y[1:o])
@constraint(model, weights' * x <= n / 3)
@constraint(model, y == C * x)
for i in 1:o
    @objective(model, Max, y[i])
    optimize!(model)
    set_lower_bound(model, y[i] >= 0.9 * value(y[i]))
end
optimize!(model)
value.(x)

```

---

<div class="post-metadata">

**Author:** ![mikel8](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@mikel8](https://discourse.julialang.org/u/mikel8)\
**Post date:** [April 18, 2023, 12:43am UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/12 "2023-04-18T00:43:29Z")

</div>

Thanks for the reply! One difficulty with this, aside from the ones Oscar mentioned, is that the problems in question are actually too large for primal simplex, we typically use interior point methods instead. I’ll definitely keep the primal reductions note in mind though!

---

<div class="post-metadata">

**Author:** ![mikel8](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@mikel8](https://discourse.julialang.org/u/mikel8)\
**Post date:** [April 18, 2023, 12:44am UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/13 "2023-04-18T00:44:26Z")

</div>

Thanks again for the time. Are there actually significant speed advantages to using set\_upper\_bound() over simply adding a slack constraint?

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [April 18, 2023, 9:00am UTC](https://discourse.julialang.org/t/simplifying-lp-for-repeated-resolving/97528/14 "2023-04-18T09:00:03Z")

</div>

You’d have to test that on your problem. The answer is probably it depends