Linear Programming Solver - osvaldoandrade/ova-lib GitHub Wiki

Linear Programming Solver

Read this page when the problem is a linear objective with <= constraints and you want the simplex implementation shipped in the library.

Supported Solver Types

The public enum lists 4 solver types:

SOLVER_BRANCH_AND_CUT

SOLVER_BRANCH_AND_BOUND

SOLVER_LAGRANGEAN_SIMPLEX

SOLVER_SIMPLEX

The current source implements only SOLVER_SIMPLEX. The other enum values exist in the public header but do not install working algorithms in the current tree.

Build the Problem

The problem constructor is:

lp_problem *create_problem(int numVariables, int numConstraints);

Construction allocates:

Stored object	Shape
`constraints`	`numConstraints x numVariables` matrix
`objective`	vector of `numVariables` coefficients
`bounds`	vector of `numConstraints` bounds

If numVariables <= 0, construction fails.

If numConstraints < 1, construction raises the capacity to 1.

The problem tracks constraint_count separately from constraint_capacity, which is why you can add constraints incrementally after construction.

Problem Mutators

The public method table on lp_problem exposes:

Field	Meaning
`add_constraint(self, coefficients, bound)`	appends one `<=` row
`set_objective(self, coefficients, type)`	copies objective coefficients and stores `PROBLEM_MAX` or `PROBLEM_MIN`
`set_bounds(self, bounds)`	overwrites the active bounds
`print(self)`	prints the objective and active constraints

add_constraint grows capacity when needed by resizing the constraint matrix rows and the bounds vector.

The current problem printer renders constraints as <= constraints, and the current simplex solver is written around that shape.

Create and Run the Solver

The solver constructor is:

solver *create_solver(SolverType type);

The solver method table exposes:

Field	Meaning
`solve(self, problem, &out_tableau)`	runs the algorithm and returns a status code
`free(self)`	frees the solver wrapper

The status codes are:

Status	Value
`OPTIMAL`	`0`
`UNBOUNDED`	`-1`
`INFEASIBLE`	`-2`

What Solve Writes Back

On success, the simplex solver stores results internally. Access the primal solution with problem->solution_value(problem, index) and the objective value with problem->objective_value(problem).

out_tableau is a caller-owned matrix * that must be freed explicitly with tableau->free(tableau).

Example

#include "solver.h"

int main(void) {
    lp_problem *problem = create_problem(2, 2);
    solver *simplex = create_solver(SOLVER_SIMPLEX);
    matrix *tableau = NULL;

    double objective[] = {1, 1};
    double c1[] = {1, 0};
    double c2[] = {0, 1};

    problem->set_objective(problem, objective, PROBLEM_MAX);
    problem->add_constraint(problem, c1, 1.0);
    problem->add_constraint(problem, c2, 1.0);

    int status = simplex->solve(simplex, problem, &tableau);

    if (tableau) {
        tableau->free(tableau);
    }
    simplex->free(simplex);
    problem->free(problem);
    return status == OPTIMAL ? 0 : 1;
}

Helper Functions

The header also exports:

Function	Meaning
`problem->is_feasible(problem, solution)`	method-table field on `lp_problem`; checks whether a vector satisfies the stored constraints
`problem->improves_objective(problem, solution, old_value, index)`	method-table field on `lp_problem`; checks whether a candidate value improves the objective
`is_integer(value)`	standalone function; checks whether a double is close to an integer

These helpers matter when you build additional solver logic around the current simplex path.

Ownership and Cleanup

Destroy the solver with solver->free(solver).

Destroy the problem with problem->free(problem).

Destroy the returned tableau with matrix->free(matrix).

The problem object owns the constraint matrix, objective vector, bounds vector, and solution array.