jdmoorman / laptools Goto Github PK

When calling an action from the marketplace such as actions/checkout@master, it is recommended practice to pin the action to a particular version such as actions/checkout@v1. This alleviates the risk of master introducing a breaking change or vulnerability.

The relevant workflow files are in the .github/workflow directory.

In particular, Thomas noticed that np.argsort takes up a lot of the time.

This way we will not need to take the same arguments into every single function.

Our code should be based on the fastest available with graphs to prove it.

Given the solution to an unconstrained problem, we should be able to solve the constrained problem super quickly. You can use the algorithm from the paper you showed me as a basis. https://www.ri.cmu.edu/pub_files/pub4/mills_tettey_g_ayorkor_2007_3/mills_tettey_g_ayorkor_2007_3.pdf

Description

A clear description of the bug

Expected Behavior

What did you expect to happen instead?

Reproduction

A minimal example that exhibits the behavior.

Environment

Any additional information about your environment

Use Case

Please provide a use case to help us understand your request in context

Solution

Please describe your ideal solution

Alternatives

Please describe any alternatives you've considered, even if you've dismissed them

Description

A clear description of the bug

Expected Behavior

What did you expect to happen instead?

Reproduction

A minimal example that exhibits the behavior.

Environment

Any additional information about your environment

Currently nothing is explained in the docs. We should explain everything in the docs once the API settles down.

Use Case

Please provide a use case to help us understand your request in context

Solution

Please describe your ideal solution

Alternatives

Please describe any alternatives you've considered, even if you've dismissed them

We are getting some datatype incompatibility issues on windows only, but none of the devs have windows machines. We have friends though, and once our friends come to the rescue we will bring back windows support.

Apparently the solvers break if there is a row or maybe a column of all infinity. We should test for this and handle it somehow.

• The function that computes the solution to the linear assignment problem can be called laptools.lap.solve(cost_matrix)
• Ideally, lap would take an optional argument of whether to return dual variables: laptools.lap.solve(cost_matrix, return_duals=True)
• The function for computing the cost of the constrained assignment for every possible constraint should be called laptools.clap.costs(cost_matrix)
  • What do we do about the functions for solving problems with a row or column removed? Let's keep them a secret for now.

Description

A clear description of the bug

Based on my understanding of the clap.costs() definition, it should solve a constrained linear assignment problem. Therefore, I believe the output of clap.costs() should be consistent with the output of the following naive_cost() function for the same input. However, I don't understand why my test code below fails to pass.

Reproduction

A minimal example that exhibits the behavior.

import numpy as np
from laptools import lap
from laptools import clap

def one_hot(idx, length):
    one_hot = np.zeros(length, dtype=np.bool)
    one_hot[idx] = True
    return one_hot

def naive_costs(cost_matrix):
    """An naive algorithm of solving all constraint LAPs. """
    n_rows, n_cols = cost_matrix.shape
    total_costs = np.full(cost_matrix.shape, np.inf)
    for i in range(n_rows):
        for j in range(n_cols):
            if cost_matrix[i,j] == np.inf:
                continue
            sub_row_ind = ~one_hot(i, n_rows)
            sub_col_ind = ~one_hot(j, n_cols)
            sub_cost_matrix = cost_matrix[sub_row_ind, :][:, sub_col_ind]
            row_idx, col_idx = lap.solve(sub_cost_matrix)
            sub_total_cost = sub_cost_matrix[row_idx, col_idx].sum()
            total_costs[i, j] = cost_matrix[i, j] + sub_total_cost
    return total_costs

cost = [[0. , np.inf, np.inf],
        [np.inf, 0. , 0.5],
        [np.inf, 1. , 0. ]]


cost = np.array(cost)
cost_clap1 = clap.costs(cost)
cost_clap2 = naive_costs(cost)
assert np.array_equal(cost_clap1, cost_clap2)

We have an implementation of costs that computes the constrained cost for every possible constraint. This should move over here.