MaxDensity: Very slow adding for edge constraints

[Nikkolix]

I try to calculate the maximum density over all sub-graphs.
My graph instance has 248,152 vertices and 878,801 edges.
Resulting in the following size of the LP:
rows: 1,757,603
cols: 1,126,953

I think I did everything according to add_constraint, add_constraintex, str_add_constraint in [https://lpsolve.sourceforge.net/5.5/](LPSolve 5.5):

Thus it is almost always better to use add_constraintex instead of add_constraint. add_constraintex is always at least as performant as add_constraint.

Note that it is advised to set the objective function (via set_obj_fn, set_obj_fnex, str_set_obj_fn, set_obj) before adding rows. This especially for larger models. This will be much more performant than adding the objective function afterwards.

Note that these routines will perform much better when set_add_rowmode is called before adding constraints.

Below you can see my implementation.
It's adding two rows per edge in the loop, via AddConstraintSparse, which uses add_constraintex.
My specs are 32GB DDR5 RAM, which is not full at any time, and the latest i9.
With my current implementation, I add approx 200 rows per second, which is way slower than expected.

func MaxDensity(g graph.Graph) (float64, error) {
	n := g.VertexCount()
	m := g.EdgeCount()

	log.Printf("MaxDensity: Creating LP instance with %d vertices and %d edges", n, m)
	lp := golp.NewLP(int(2*m+1), int(m+n))

	// x_ij vars (one per edge), y_i vars (one per node)
	log.Printf("MaxDensity: Setting object function")
	obj := make([]float64, m+n)
	for i := range m {
		obj[i] = 1
	}
	lp.SetObjFn(obj)
	lp.SetMaximize()

	row := make([]golp.Entry, 2)
	row[0].Val = 1
	row[1].Val = -1

	// Constraints: x_ij ≤ y_i und x_ij ≤ y_j
	log.Printf("MaxDensity: Adding constraints for edges")
	err := g.ForEdges(
		func(u, v, i integer.Int) error {
			row[0].Col = int(i)
			row[1].Col = int(m + u)
			_ = lp.AddConstraintSparse(row, golp.LE, 0) // err is always nil

			row[0].Col = int(i)
			row[1].Col = int(m + v)
			_ = lp.AddConstraintSparse(row, golp.LE, 0) // err is always nil
			return nil
		},
	)
	if err != nil {
		return -1, err
	}

	// Constraint: ∑ y_i ≤ 1
	log.Printf("MaxDensity: Adding sum y_i constraint")
	sumY := make([]float64, m+n)
	for i := range n {
		sumY[m+i] = 1
	}
	lp.AddConstraint(sumY, golp.LE, 1) // err is always nil

	log.Printf("MaxDensity: Solving MaxDensity LP with %d variables and %d constraints", lp.NumCols(), lp.NumRows())
	lp.Solve()

	return lp.Objective(), nil
}

[Nikkolix]

Adding this, as SetObjFn does set SetAddRowMode to false, did speed up to about 1000 edges per second. But even this seems slow.

lp.SetObjFn(obj)
lp.SetAddRowMode(true)

[draffensperger]

Hi @Nikkolix it sounds like this may be an underlying issue with LPSolve. If you find opportunities for performance improvements in the Go binding side of things, I'm happy to review any pull requests.