More MOIified implementation, again #504

ericphanson · 2023-07-06T23:39:05Z

Updated #393 to the latest master, and made a few fixes and cleanup. Still has a ways to go.

replaces UniqueConicForms construction with similar-in-spirit Context object, which now holds the MOI problem so we can add constraints/variables directly there as we traverse the problem. This is the main improvement which lets us lower new cones directly to MOI and handle things like geomean: Support for vectors #388.
makes context the first argument to conic_forms! to make it clear that is what is being mutated (not the atom)
removes non-functional caching system
closes Move away from hashing #78 by not using hashing to cache conic_forms! within a problem. We do so by simply not caching them. However I think if we wanted to, we could cache by objectid instead of hash, xref Proof of concept more-MOIified implementation #393 (comment).
closes scaledgeomean exported but not defined #392 by deleting the file
closes geomean: Support for vectors #388
does not yet solve Add support for quadratic objective functions #384. I think this one is still somewhat hard (though easier now?) because we have no internal modelling of quadratic things at all. This partial rewrite makes it easier to add new constraints of the form "affine function in cone", and we can add atoms that use such constraints in extended formulations, but we still can't actually have any kind of standalone quadratic atom. Maybe one path there is to move these extended formulations into MOI itself (and DCP modelling so it can know when they are valid), so Convex is an even smaller wrapper, and handle everything at the MOI layer.
populates duals in more cases. These need tests.

ericphanson · 2023-07-09T14:08:22Z

Status:

The old system has been replaced by the new one everywhere
The new system is quite buggy still
The majority of problems in the test suite can be solved, including most SDPs, SOCPs, exponential cone problems, duals, integer constraints, etc
in terms of getting all tests passing, I think the biggest remaining issues are around complex variable handling, specifically where problems have a mix of complex variables and non-complex variables. E.g. I am missing a method for complex_operate(vcat, T, ::ComplexTape, ::SparseAffineTape)
in terms of making the new system work reliably, I am concerned about the robustness of the operate system implemented here. I think there is too much room to hit unimplemented methods or incorrect fallbacks. I think it needs to be tightened up considerably to prevent unforseen issues.
I am also concerned that the tests may not cover all problem formulations and there could be correctness issues left after getting all the tests to pass.

From a recent SCS run locally:

Test Summary:                                              | Pass  Fail  Error  Total     Time
SCS                                                        |  611     5     10    626  4m03.2s
  constant                                                 |   28                  28     4.4s
  affine                                                   |  140                 140    14.1s
  exp                                                      |   27                  27     4.8s
  socp                                                     |   99            1    100    14.5s
  lp                                                       |   56            2     58     4.5s
  sdp                                                      |  258     5      7    270  3m18.8s

odow · 2023-07-09T16:00:32Z

I think there is too much room to hit unimplemented methods or incorrect fallbacks. I think it needs to be tightened up considerably to prevent unforseen issues.

Agree. If you want to see my recent work on this:

ericphanson · 2023-07-09T17:51:18Z

@odow would you mind summarizing any tips or general strategy for that work?

Specifically, do you have any tips for cases where the user passes input that influences things?

E.g. in Convex the user can write hcat(args...) with a mix of variables, constants, and expressions which is causing me issues.

codecov · 2023-07-10T22:40:06Z

Codecov Report

Attention: 127 lines in your changes are missing coverage. Please review.

Comparison is base (4c4bead) 90.27% compared to head (6db87bd) 92.00%.

Files	Patch %	Lines
src/atoms/affine/multiply_divide.jl	85.52%	11 Missing ⚠️
src/constraints/constraints.jl	83.33%	11 Missing ⚠️
src/complex_operate.jl	72.97%	10 Missing ⚠️
src/solution.jl	78.04%	9 Missing ⚠️
src/constraints/sdp_constraints.jl	77.41%	7 Missing ⚠️
src/MOI_wrapper.jl	82.35%	6 Missing ⚠️
src/operate.jl	85.00%	6 Missing ⚠️
src/atoms/affine/add_subtract.jl	80.00%	5 Missing ⚠️
src/ComplexTape.jl	71.42%	4 Missing ⚠️
src/SparseTape.jl	87.50%	4 Missing ⚠️
... and 21 more

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #504      +/-   ##
==========================================
+ Coverage   90.27%   92.00%   +1.73%     
==========================================
  Files          84       87       +3     
  Lines        5572     5293     -279     
==========================================
- Hits         5030     4870     -160     
+ Misses        542      423     -119

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

ericphanson · 2023-07-11T00:36:34Z

I think I've made some good progress tightening up the operate stuff, although there's a few loose ends in the multiply atom to handle still. Otherwise it is pretty controlled and I am much less worried about unexpected situations. I also removed the fallbacks. Additionally, all tests are passing now, except for the sdp_lieb_ando ones which had issues on main. Now however we can't even formulate the problem (let alone solve it), which means there's still some bugs to shake out in this PR.

ericphanson · 2023-07-11T23:41:41Z

Ok, I think this is in decent shape now; in particular the operate system is much more constrained and there should not be runtime MethodErrors / other errors possible in that system. However depending on what the users passes it could be possible to error elsewhere when trying to convert their type to a matrix or sparse matrix.

Warmstarts are not re-implemented, but I'm not sure it's essential for this PR.

There is probably some missing test coverage that should be fixed before we merge however.

I will mark it as ready-for-review now.

ericphanson · 2023-08-01T07:57:23Z

I've been looking into perf since I believe this has regressed things. I also have some updates in #254. Running the benchmarks here, I get:

In [10]: include("benchmark/pprintjudge.jl")
Out[10]:   Benchmark Report for /Users/eph/Convex.jl
  ≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡

  Job Properties
  ================

    •  Time of benchmarks:
       • Target: 1 Aug 2023 - 09:52
       • Baseline: 1 Aug 2023 - 09:53

    •  Package commits:
       • Target: 4ecbe7
       • Baseline: 614b48

    •  Julia commits:
       • Target: e4ee48
       • Baseline: e4ee48

    •  Julia command flags:
       • Target: None
       • Baseline: None

    •  Environment variables:
       • Target: JULIA_NUM_THREADS => 1
       • Baseline: JULIA_NUM_THREADS => 1

  Results
  =========

  A ratio greater than 1.0 denotes a possible regression (marked with ❌), while a ratio less than 1.0 denotes a possible improvement
  (marked with ✅). Only significant results - results that indicate possible regressions or improvements - are shown below (thus, an
  empty table means that all benchmark results remained invariant between builds).

                                                                 ID  time ratio memory ratio
  ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– ––––––––––– ––––––––––––
              ["formulation", "affine", "affine_dot_multiply_atom"] 4.28 (5%) ❌  1.25 (1%) ❌
                      ["formulation", "affine", "affine_hcat_atom"] 1.83 (5%) ❌  0.93 (1%) ✅
                     ["formulation", "affine", "affine_trace_atom"] 5.22 (5%) ❌  1.23 (1%) ❌
  ["formulation", "constant", "constant_fix!_with_complex_numbers"] 3.10 (5%) ❌  1.05 (1%) ❌
                         ["formulation", "exp", "exp_entropy_atom"] 2.00 (5%) ❌  0.90 (1%) ✅
                 ["formulation", "exp", "exp_log_perspective_atom"] 2.26 (5%) ❌  0.75 (1%) ✅
                           ["formulation", "lp", "lp_maximum_atom"] 3.00 (5%) ❌  0.73 (1%) ✅
                    ["formulation", "mip", "mip_integer_variables"] 3.98 (5%) ❌  1.11 (1%) ❌
                      ["formulation", "sdp", "sdp_lambda_min_atom"] 1.80 (5%) ❌  0.55 (1%) ✅
                     ["formulation", "sdp", "sdp_sum_largest_eigs"] 1.38 (5%) ❌  0.53 (1%) ✅
         ["formulation", "sdp_and_exp", "sdp_and_exp_log_det_atom"] 0.80 (5%) ✅  0.24 (1%) ✅
                     ["formulation", "socp", "socp_quad_form_atom"] 2.30 (5%) ❌  0.95 (1%) ✅
                   ["formulation", "socp", "socp_sum_squares_atom"] 3.00 (5%) ❌  0.94 (1%) ✅

So we have regressed formulation for a bunch of problems, although with better memory consumption in many cases.

Right now I maintain a lazy "tape" of affine operations to compose. (This came from the original PR #393). Trying without that, I get (against the same baseline), which looks like the right direction at least.

                                                                 ID  time ratio memory ratio
  ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– ––––––––––– ––––––––––––
              ["formulation", "affine", "affine_dot_multiply_atom"] 3.29 (5%) ❌  1.22 (1%) ❌
                      ["formulation", "affine", "affine_hcat_atom"] 1.27 (5%) ❌  0.89 (1%) ✅
                     ["formulation", "affine", "affine_trace_atom"] 3.67 (5%) ❌  1.20 (1%) ❌
  ["formulation", "constant", "constant_fix!_with_complex_numbers"] 2.49 (5%) ❌    0.99 (1%)
                         ["formulation", "exp", "exp_entropy_atom"] 1.56 (5%) ❌  0.83 (1%) ✅
                 ["formulation", "exp", "exp_log_perspective_atom"] 2.06 (5%) ❌  0.72 (1%) ✅
                           ["formulation", "lp", "lp_maximum_atom"] 2.18 (5%) ❌  0.71 (1%) ✅
                    ["formulation", "mip", "mip_integer_variables"] 2.89 (5%) ❌  1.07 (1%) ❌
                      ["formulation", "sdp", "sdp_lambda_min_atom"] 1.33 (5%) ❌  0.52 (1%) ✅
                     ["formulation", "sdp", "sdp_sum_largest_eigs"] 1.11 (5%) ❌  0.50 (1%) ✅
         ["formulation", "sdp_and_exp", "sdp_and_exp_log_det_atom"] 0.60 (5%) ✅  0.22 (1%) ✅
                     ["formulation", "socp", "socp_quad_form_atom"] 1.74 (5%) ❌  0.87 (1%) ✅
                   ["formulation", "socp", "socp_sum_squares_atom"] 1.83 (5%) ❌  0.88 (1%) ✅

with some additional optimization (aad79b8), I get

                                                                 ID  time ratio memory ratio
  ––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– ––––––––––– ––––––––––––
              ["formulation", "affine", "affine_dot_multiply_atom"] 3.16 (5%) ❌  1.18 (1%) ❌
                      ["formulation", "affine", "affine_hcat_atom"] 1.36 (5%) ❌  0.78 (1%) ✅
                     ["formulation", "affine", "affine_trace_atom"] 3.71 (5%) ❌  1.18 (1%) ❌
  ["formulation", "constant", "constant_fix!_with_complex_numbers"] 2.27 (5%) ❌  0.93 (1%) ✅
                         ["formulation", "exp", "exp_entropy_atom"] 1.84 (5%) ❌  0.79 (1%) ✅
                 ["formulation", "exp", "exp_log_perspective_atom"] 2.32 (5%) ❌  0.69 (1%) ✅
                           ["formulation", "lp", "lp_maximum_atom"] 2.06 (5%) ❌  0.68 (1%) ✅
                    ["formulation", "mip", "mip_integer_variables"] 2.80 (5%) ❌  1.05 (1%) ❌
                      ["formulation", "sdp", "sdp_lambda_min_atom"] 1.27 (5%) ❌  0.49 (1%) ✅
                     ["formulation", "sdp", "sdp_sum_largest_eigs"] 1.05 (5%) ❌  0.46 (1%) ✅
         ["formulation", "sdp_and_exp", "sdp_and_exp_log_det_atom"] 0.57 (5%) ✅  0.22 (1%) ✅
                     ["formulation", "socp", "socp_quad_form_atom"] 1.73 (5%) ❌  0.81 (1%) ✅
                   ["formulation", "socp", "socp_sum_squares_atom"] 2.17 (5%) ❌  0.83 (1%) ✅

blegat · 2023-12-04T13:58:42Z

@ericphanson what's the status of this ? I'd like to make some changes to improve the MOI wrapper support so it would be easier if at least part of this big PR is merged in order to avoid conflict. The small perf difference do not seem big enough to block merging

ericphanson · 2023-12-05T00:50:45Z

Probably just needs some review and a rebase. If you are able to give some review that would help move it forward. I don’t remember there being any real blockers or big TODOs left

blegat · 2023-12-12T10:53:10Z

@odow @ericphanson Any objection to merge this and follow the plan of my above comment ? Since this PR has such a large diff, it's going to be a pain to review changes on top of it and I'd like to try a few things.

ericphanson · 2023-12-12T12:24:44Z

I think that seems OK, especially if you've been looking through the diff as you've worked here. I think that can effectively be some amount of review. At work I'd suggest we pair review it, where we get on a call and go through it together, but realistically I don't think I would have time anytime soon for that.

Are there any areas you are concerned about?

blegat · 2023-12-12T12:40:38Z

One thing I've been wondering is why allowing to pass an instantiated optimizer in Context and solve! that is allowed to be non-empty. In JuMP, we only allow an optimizer constructor and in MOI.CachingOptimizer, we check with MOI.is_empty to check that it is empty. Maybe we could restrict these to only getting an optimizer constructor ?

blegat · 2023-12-12T12:42:49Z

src/problems.jl

@@ -31,6 +30,8 @@ function Base.getproperty(p::Problem, s::Symbol)
        else
            return objective_value(p)
        end
+    elseif s === :size
+        return (1, 1)


I'm not so sure what this is for as well. It actually wasn't tested so I had to add a test

hm, if it was coming up in codecov as untested maybe it's not used at all and we can delete it. I don't really remember this, but if I had to guess it would be for something like partially specified problems (#310)

Let's try to remove it and see if anything breaks:
5b401f0

ericphanson · 2023-12-13T11:36:31Z

One thing I've been wondering is why allowing to pass an instantiated optimizer in Context and solve! that is allowed to be non-empty. In JuMP, we only allow an optimizer constructor and in MOI.CachingOptimizer, we check with MOI.is_empty to check that it is empty. Maybe we could restrict these to only getting an optimizer constructor ?

Hm, that would make sense. I don't think I understood (and probably still don't understand) the semantics of optimizers and just messed with it until it seemed to work. Changing it seems totally fine.

blegat · 2023-12-16T17:46:13Z

I have done the changes suggested in #504 (comment) and #504 (comment) and it looks good to me know, I'll merge next week if there is no objection

odow · 2023-12-20T00:19:18Z

This is too big to review. But given Convex.jl has seen very little activity recently, I'm okay releasing this as a breaking change if it is an improvement that fixes open issues.

@mlubin should take a brief look before merging.

odow · 2023-12-21T20:32:12Z

I've added this PR to the agenda for next week's developer call.

mlubin · 2023-12-22T00:30:57Z

It looks like warmstart=true is removed and there's a FIXME there. Do we plan to merge and release this without the ability to restart from the previous primal/dual solution? Is there a workaround for users?

odow · 2023-12-22T00:51:00Z

There's an open issue: #518

blegat · 2023-12-22T11:15:05Z

Do we plan to merge and release this without the ability to restart from the previous primal/dual solution? Is there a workaround for users?

No, the plan to wait a while before releasing and at least fixing #518

mlubin

Ok to merge. (Comment can be addressed now or later.)

mlubin · 2023-12-22T00:22:00Z

docs/src/contributing.md

-     appropriate variables) in
-     [solve!](https://github.com/jump-dev/Convex.jl/blob/master/src/solution.jl#L205).
+1. A `Problem{T}` struct is created by putting together an objective function and constraints.
+   This forms a tree of sorts, in which variables and constants are the leaves, and atoms form the


Can we be more precise than "a tree of sorts"?

odow · 2023-12-28T22:50:58Z

Developer call agrees to merge as a breaking change. @blegat plans a few other changes once this lands before we tag the next release.

ericphanson mentioned this pull request Jul 6, 2023

Proof of concept more-MOIified implementation #393

Closed

14 tasks

ericphanson marked this pull request as ready for review July 11, 2023 23:41

ericphanson mentioned this pull request Jul 12, 2023

Massive RAM for moderate problem #254

Closed

ericphanson mentioned this pull request Sep 11, 2023

GC corruption JuliaSparse/SuiteSparseGraphBLAS.jl#120

Open

blegat force-pushed the eph/moi2-again branch from aad79b8 to 63aa96c Compare December 5, 2023 20:19

ericphanson added 16 commits December 6, 2023 22:34

reland on master

bf42623

add tests

12cfdf0

remove more complicated variants

ee31f1b

remove 2's from names

771d5fd

simplify

cbcda97

rename

db40dbe

some tweaks

444e87c

wip

88fe9ad

fix strange bug in transpose

f6087cc

move fallback somewhere better

5f83841

tweak

c64b133

slightly cleanup, restore comment

0ba5d63

misc

f28175c

format

e9b42e7

complex vcat

a0a7e5e

get sdp_relative_entropy working

427b28b

blegat added 2 commits December 11, 2023 18:44

Fix MOI wrapper tests

71762ff

Fix format

2171b19

blegat reviewed Dec 12, 2023

View reviewed changes

blegat added 5 commits December 13, 2023 16:26

Remove size

5b401f0

Prevent non-empty model being given

ef6acb6

Fixes

09ac381

Fix

04dfb50

Fix format

6db87bd

mlubin approved these changes Dec 22, 2023

View reviewed changes

blegat merged commit 02bbd70 into master Dec 29, 2023
10 checks passed

blegat mentioned this pull request Dec 29, 2023

Clarify documentation #521

Closed

ericphanson mentioned this pull request Dec 29, 2023

add test for issue 510 #522

Merged

ericphanson deleted the eph/moi2-again branch December 29, 2023 15:32

This was referenced Jan 11, 2024

Document that atoms must be mutable #548

Closed

remove internal function latex_formulation #551

Merged

This was referenced May 7, 2024

Too much memory consumption right before trying to solve a problem. #390

Closed

Add OptimizationSenseAtom #636

Closed

This was referenced May 14, 2024

cleanup: delete internal type VectorAffineFunctionAsMatrix #660

Merged

remove unused incorrect method #680

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

More MOIified implementation, again #504

More MOIified implementation, again #504

ericphanson commented Jul 6, 2023 •

edited

Loading

ericphanson commented Jul 9, 2023

odow commented Jul 9, 2023

ericphanson commented Jul 9, 2023 •

edited

Loading

codecov bot commented Jul 10, 2023 •

edited

Loading

ericphanson commented Jul 11, 2023

ericphanson commented Jul 11, 2023

ericphanson commented Aug 1, 2023 •

edited

Loading

blegat commented Dec 4, 2023 •

edited

Loading

ericphanson commented Dec 5, 2023

blegat commented Dec 12, 2023

ericphanson commented Dec 12, 2023

blegat commented Dec 12, 2023

blegat Dec 12, 2023

ericphanson Dec 13, 2023

blegat Dec 13, 2023

ericphanson commented Dec 13, 2023

blegat commented Dec 16, 2023

odow commented Dec 20, 2023

odow commented Dec 21, 2023

mlubin commented Dec 22, 2023

odow commented Dec 22, 2023

blegat commented Dec 22, 2023

mlubin left a comment

mlubin Dec 22, 2023

odow commented Dec 28, 2023

More MOIified implementation, again #504

More MOIified implementation, again #504

Conversation

ericphanson commented Jul 6, 2023 • edited Loading

ericphanson commented Jul 9, 2023

odow commented Jul 9, 2023

ericphanson commented Jul 9, 2023 • edited Loading

codecov bot commented Jul 10, 2023 • edited Loading

Codecov Report

ericphanson commented Jul 11, 2023

ericphanson commented Jul 11, 2023

ericphanson commented Aug 1, 2023 • edited Loading

blegat commented Dec 4, 2023 • edited Loading

ericphanson commented Dec 5, 2023

blegat commented Dec 12, 2023

ericphanson commented Dec 12, 2023

blegat commented Dec 12, 2023

blegat Dec 12, 2023

Choose a reason for hiding this comment

ericphanson Dec 13, 2023

Choose a reason for hiding this comment

blegat Dec 13, 2023

Choose a reason for hiding this comment

ericphanson commented Dec 13, 2023

blegat commented Dec 16, 2023

odow commented Dec 20, 2023

odow commented Dec 21, 2023

mlubin commented Dec 22, 2023

odow commented Dec 22, 2023

blegat commented Dec 22, 2023

mlubin left a comment

Choose a reason for hiding this comment

mlubin Dec 22, 2023

Choose a reason for hiding this comment

odow commented Dec 28, 2023

ericphanson commented Jul 6, 2023 •

edited

Loading

ericphanson commented Jul 9, 2023 •

edited

Loading

codecov bot commented Jul 10, 2023 •

edited

Loading

ericphanson commented Aug 1, 2023 •

edited

Loading

blegat commented Dec 4, 2023 •

edited

Loading