1. 23 Jun, 2022 2 commits
  2. 22 Jun, 2022 4 commits
  3. 30 May, 2022 4 commits
    • Gwenael SAMAIN's avatar
      LB: update some fixme/todo comments · adcc30d9
      Gwenael SAMAIN authored
      adcc30d9
    • Gwenael SAMAIN's avatar
      ICD: feature parity with homotopy for dual pruning & screening. · da9b5de0
      Gwenael SAMAIN authored
      This commit achieves the feature parity between homotopy and icd.
      More precisely, before this commit icd already had dual pruning and screening,
      but the iteration modulo were hardcoded instead of exposed to the command line arguments.
      Also, some optimization were made just like homotopy: using the target_UB when
      it's better than the current primal iterate, and nest the screening computation
      inside the dual pruning block so that we don't try to compute the screening
      when the dual wasn't updated.
      Note that the dual rescale done in the homotopy couldn't be done in icd,
      at least not the same way, as we don't have "intermediary mu" like in homotopy.
      da9b5de0
    • Gwenael SAMAIN's avatar
      Remove old Makefiles. · 596f3adb
      Gwenael SAMAIN authored
      As there are already handful of commits of both CMake and plain Makefiles,
      and as we've reached performance parity, there is no need to keep & maintain
      plain Makefiles anymore, so this commit remove them from the tree.
      596f3adb
    • Gwenael SAMAIN's avatar
      Include Armadillo's cmake script for detecting OpenBLAS, Lapack, etc. · 6e6fdfe7
      Gwenael SAMAIN authored
      Detecting linear algebra libraries seem to be a bit clunky.
      As a brainless way to do it, I took the corresponding cmake scripts
      from Armadillo, and "tada, it works !".
      This would need a bit of streamlining to live in a better world.
      6e6fdfe7
  4. 03 May, 2022 6 commits
    • Gwenael SAMAIN's avatar
      Fix ICD final objective value when evaluating LB. · b71d2d5e
      Gwenael SAMAIN authored
      When we evaluate the lower bound, several algorithms can be used,
      among them (iterative) coordinate descent, coined as ICD in the code.
      The lower bound given at the end of the ICD iterations was too high by
      mu * Card(S1), due to the integration of that term in the dual objective function
      (used in every algorithm for computing the lower bound) not being
      retropropagated to the ICD specific code, meaning we added again
      this mu*Card(S1) in the ICD specifi code.
      This commit fixes this double addition.
      b71d2d5e
    • Gwenael SAMAIN's avatar
      Active set: change back numerical zero to 10^-3. · 857755e7
      Gwenael SAMAIN authored
      My previous change to 10^-8 was apparently defective: it severely
      crashes when running it on instances.
      In the lack of time & motivation to inspect this further right now,
      I revert to the previous epsilon given by Ramzi of 10^-3.
      857755e7
    • Gwenael SAMAIN's avatar
      Fix parameter for P2+0 (no times 2 anymore). · f9d89bec
      Gwenael SAMAIN authored
      The most used theoretical formulation of P2+0 is (with mu as penalty parameter):
      1/2 ||y - Ax||^2 + mu ||x||_0
      
      The 1/2 before the least-square term is handy when manipulating the gradient
      in the optimization algorithms.
      However, due to historical reasons, Mimosa was solving problems formulated as:
      ||y - Ax||^2 + mu ||x||_0
      
      This is now fixed to the 1/2 version.
      f9d89bec
    • Gwenael SAMAIN's avatar
      Change P2+0 parameter to mu.dat. · f3c3667b
      Gwenael SAMAIN authored
      The P2+0 (also denoted as L2pL0 in the code) problem is the penalized
      version of our sparse optimization problems: the objective function
      is composed of a least-square term and an l0 pseudo-norm, this l0
      term being weighted by a parameter. Previously, this parameter was named
      lambda, but it conflicts with reserved name for some application problems,
      such as (sparse) spectral analysis, where lambda denotes a frequency in a spectrum.
      This renames the parameter _in the instance files_ as mu.
      WARNING: the code still "speaks" in terms of lambda.
      f3c3667b
    • Gwenael SAMAIN's avatar
      0133bbd7
    • Gwenael SAMAIN's avatar
      Fix gap-safe screening rule to be compatible with homotopy rescale. · 61fc1845
      Gwenael SAMAIN authored
      The Gap-Safe screening rule has a radius which depends on the duality gap.
      It works with an arbitrary (feasible) primal point x, as well as an arbitrary
      dual point w. Moreover, the theoretical performance of the screening is better
      if we choose w such that w = Ax - y, because the radius of the screening
      decreases, from sqrt(2*Gap(x, w)) to sqrt(Gap(x, w)) (i.e. we saved a sqrt(2) factor).
      However, in the case of homotopy, the rescaled w = breakpoint_lambda / target_mu * (Ax - y)
      is able to produce a dual objective which is way better than w = Ax - y.
      So, the dual gap is really lower, at the cost of a sqrt(2) increase in the screening radius.
      Empirically, we are winning when using this dual rescale.
      This fixes the screening radius by adding the sqrt(2) factor, so that we can use
      any dual point, including the homotopy rescaled version.
      61fc1845
  5. 12 Apr, 2022 1 commit
    • Gwenael SAMAIN's avatar
      Change exploration strategy in l2pl0 scripts: stack -> heap_on_lb. · 6a9db83f
      Gwenael SAMAIN authored
      The choice of the exploration strategy has an impact on the performance
      of the method, particularly when the problem is hard to solve,
      and bounds are not that good.
      To quickly proove the optimality of the solution, empirical evidences
      suggest to prefer heap_on_lb (that is, best-first search) instead of
      stack (that is, depth-first search).
      This commit changes the default strategy used in the handy scripts
      in this direction.
      6a9db83f
  6. 07 Apr, 2022 4 commits
    • Gwenael SAMAIN's avatar
      Make L2pL1_dual resilient to empty SBar. · e0c963be
      Gwenael SAMAIN authored
      When we are screening out variables, we remove them
      from the SBar support explored during optimization.
      During the optimization, we may compute a dual objective value.
      This dual depends on SBar.
      The edge case of empty SBar wasn't taken into account before,
      leading to an exception when taking some max of an empty vector.
      This is now fixed: no SBar = don't take that maximum.
      e0c963be
    • Gwenael SAMAIN's avatar
      Code aesthetic for residual expression · fa134920
      Gwenael SAMAIN authored
      fa134920
    • Gwenael SAMAIN's avatar
      Change TimeBBMax to 1 hour. · 754ddd9a
      Gwenael SAMAIN authored
      When creating the Context, a default value is assigned
      to TimeBBMax, which controls the maximum amount of seconds
      left to the solver. This commit raises this limit from 1000 sec
      to 3600 (= 1 hour).
      754ddd9a
    • Gwenael SAMAIN's avatar
      Change default value of warm_restart to false. · 8c1a5c2e
      Gwenael SAMAIN authored
      When creating a Context, sane default values are assigned
      to a number of options, including the warm_restart.
      To be conservative with respect to old behaviour,
      the warm restart is set to false by default.
      8c1a5c2e
  7. 01 Apr, 2022 1 commit
    • Gwenael SAMAIN's avatar
      Fix CMake -O3 flag not set. · 84be8414
      Gwenael SAMAIN authored
      CMake being what it is, it seems that CMAKE_CXX_FLAGS and CMAKE_CXX_FLAGS_RELEASE
      are not performing the same job, because CMake doesn't build in Release mode
      by default ?
      Anyway, the O3 flag is not anymore set into CMAKE_CXX_FLAGS_RELEASE, but
      into CMAKE_CXX_FLAGS. Works like a charm.
      84be8414
  8. 16 Mar, 2022 1 commit
    • Gwenael SAMAIN's avatar
      Fix scripts borrowed from MimosaUnmix. · 8015d2dc
      Gwenael SAMAIN authored
      Mimosa_l2pl0_listinst, Mimosa_l2pl0_pipeinst, Mimosa_l2pl0_1inst
      are scripted originally written for MimosaUnmix, the code version
      targetting sparse problems with positivity and sum to 1 constraints.
      This fixes the scripts calling MimosaUnmix instead of Mimosa.
      8015d2dc
  9. 04 Mar, 2022 4 commits
    • Gwenael SAMAIN's avatar
      Change matrix filename to A.dat. · 4ea101dd
      Gwenael SAMAIN authored
      Before we used the old Hmatrix.dat,but H is more a signal processing notation,
      and not as general as A.
      4ea101dd
    • Gwenael SAMAIN's avatar
      Introduce shorthand scripts for l2pl0 quick invocation. · ac197b53
      Gwenael SAMAIN authored
      This introduce three script dedicated to l2pl0 that ease invocation
      of Mimosa by predefining all the solver options, the only remaining
      thing being the place(s) to find the instance(s).
      CMakeLists has been updated so that these scripts are shipped into
      cpacks packages.
      ac197b53
    • Gwenael SAMAIN's avatar
      Remove SBR reference for l2pl0. · 77a4e2d5
      Gwenael SAMAIN authored
      `l2pl0_with_SBR` and `l2pl0_without_SBR` has been merged into
      a single `l2pl0`, to avoid newcomers surprises. The sbr boolean
      switch is still in the code if needed sometimes later though.
      77a4e2d5
    • Gwenael SAMAIN's avatar
      Add back heap_on_ls in show_usage(). · c21e930f
      Gwenael SAMAIN authored
      heap_on_ls exploration strategy was already added back in the
      comments, but not in the end-user usage message.
      c21e930f
  10. 17 Feb, 2022 1 commit
    • Gwenael SAMAIN's avatar
      Add optional argument to output CSV data. · acec4ac0
      Gwenael SAMAIN authored
      Before this commit, cerr contained both the usual
      error output _and_ some useful execution metrics
      formatted as csv.
      Separating that csv from the standard output is useful
      because of the kind of interactive "I'm still alive"
      way to log things into standard output currently implemented.
      Throwing out that CSV output to standard error is just
      a semantic mess done because of previous (extreme) lazyness
      from my end.
      This commit adds an optional argument, the filename
      where the CSV data must be throwned to.
      If this argument is absent, the old way of throwing the CSV
      to standard error is kept, for backward compatibility purpose.
      acec4ac0
  11. 25 Jan, 2022 2 commits
    • Gwenael SAMAIN's avatar
      Consume instance from stdin. · 5ca53af7
      Gwenael SAMAIN authored
      This commit is a small change in the way we get the list of instances to run.
      Before this commit, we are supposed to give an SNR, a K and an instance range.
      It therefore assumes that a given instance has an SNR, and a K.
      More precisely, the instance format MUST follow:
      SA_SNRxx_Kyy_instancezz
      Where xx, yy and zz are integers.
      This format is absolutely arbitrary, and comes from the first dataset
      used to test the code.
      After this commit, the arguments SNR, K, instance are removed.
      Instead, we get a list of instances, one instance per line, from stdin.
      5ca53af7
    • Gwenael SAMAIN's avatar
      Add inplace comment for dual modulo and screening modulo parsing. · 8df12217
      Gwenael SAMAIN authored
      Each command line argument has a small dedicated parsing section.
      As there is quite a lot of arguments, a comment recall what argument
      is being parsed at the beginning of the section.
      This was not yet the case for dual modulo and screening modulo arguments.
      8df12217
  12. 18 Jan, 2022 1 commit
    • Gwenael SAMAIN's avatar
      Add back heap_on_ls in docs + LDS introduction. · 097b062a
      Gwenael SAMAIN authored
      Heap_on_ls was previously absent from usage message, this is fixed.
      Also, Limited Discrepancy Search can be a good heuristic to guide
      the branch-and-bound, possibly better than Depth-first search.
      An LDS gives equivalent score to nodes which have the same
      number of right branches ("wrong" branches in the branching strategy sense)
      in their ancestry path. In our setting, this corresponds to the size of S0.
      097b062a
  13. 11 Jan, 2022 1 commit
    • Gwenael SAMAIN's avatar
      Fix ret.prune not initialized. · 3f7638de
      Gwenael SAMAIN authored
      To leverage dual pruning, the current implementation
      uses a struct called relax_info as a return for l1 algorithms functions.
      This relax_info contains, among other things, whether the node must be pruned
      or not.
      This structure was created simply with a:
      ```
      relax_info ret
      ```
      And then, if we are in the correct case, ret.prune is set to true.
      This assumes the above declaration initialize ret.prune to false.
      This is not the case for every compiler-os-platform combination.
      This commit fixes this by forcing the initialization to false.
      3f7638de
  14. 07 Jan, 2022 8 commits
    • Gwenael SAMAIN's avatar
      Active set: update numerical zero. · 3cdfa006
      Gwenael SAMAIN authored
      Before that patch, the active set numerical zero
      (aka the threshold under which we disregard the value and say it's 0)
      was way too high. This patch makes this threshold a bit more sensible.
      3cdfa006
    • Gwenael SAMAIN's avatar
      Update scr_b_S1_card comment · 45576be5
      Gwenael SAMAIN authored
      45576be5
    • Gwenael SAMAIN's avatar
      Update main header comment. · d9ea6224
      Gwenael SAMAIN authored
      d9ea6224
    • Gwenael SAMAIN's avatar
      Per node dual pruning stats. · bccf7724
      Gwenael SAMAIN authored
      This patch allows logging detailed traces of per node metrics.
      For now we are only talking about dual pruning and screening
      in the lower bounding stage, but this can be further extended
      according to needs.
      bccf7724
    • Gwenael SAMAIN's avatar
      Give names to nodes. · 6a0ad78f
      Gwenael SAMAIN authored
      Before, nodes didn't have any names, preventing them to be uniquely
      identified. Now, the name as the format:
      T[rl]*
      "T" denotes the root node,
      "r" denotes the right child of a parent node,
      "l" the left child.
      So, "Trl" is the left child of the right child of the root:
        T
       / \
      Tl  Tr
         /  \
        Trl  Trr
      6a0ad78f
    • Gwenael SAMAIN's avatar
      Introduce mod_dual and mod_screening in command line arguments. · d03bf1a1
      Gwenael SAMAIN authored
      Inside the homotopy, how many times should we compute the dual,
      and when we compute it, should we compute the GapSafe screening ?
      Previously, the answers to these questions were hardcoded.
      Now, they are command line (mandatory) arguments.
      d03bf1a1
    • Gwenael SAMAIN's avatar
      Homotopy screening acceleration: use min(UB, P(x)). · 0f507eb4
      Gwenael SAMAIN authored
      When we use the screening inside the homotopy, we compute
      a duality gap therefore we need a primal and a dual.
      But the screening is also valid for non-pruned nodes
      if we take the best known upper bound instead of the primal.
      For eventually pruned nodes, it will either:
      - change nothing,
      - get a suboptimal solution P(x') > P(x) > UB, so we will prune anyway.
      This commit takes as "primal value" the minimum between the
      best upper bound and the current primal iterate objective.
      0f507eb4
    • Gwenael SAMAIN's avatar
      Unclutter log file when displacing screened out components. · 36745ba3
      Gwenael SAMAIN authored
      When using the screening, we displace components from "can move" supports
      to "won't move anymore" supports.
      The current implementation doesn't know from which "can move" support a given
      component must be displaced, so we test them in sequence.
      This commit negates a log message (redundant with the return value)
      shouting at the console it cannot find a given component in a specific
      "can move" support.
      36745ba3