### A.33.1 Introduction

A **linear programming problem** or simply **linear program**
(LP) consists of:

- a set of
*linear***constraints** - a set of
**variables** - a
*linear***objective function**.

The goal is to assign values to the variables so as to *maximize*
(or minimize) the value of the objective function while satisfying all
constraints.

Many optimization problems can be modeled in this way. As one basic
example, consider a knapsack with fixed capacity C, and a number of
items with sizes `s(i)`

and values `v(i)`

. The
goal is to put as many items as possible in the knapsack (not exceeding
its capacity) while maximizing the sum of their values.

As another example, suppose you are given a set of *coins* with
certain values, and you are to find the minimum number of coins such
that their values sum up to a fixed amount. Instances of these problems
are solved below.

Solving an LP or integer linear program (ILP) with this library typically comprises 4 stages:

- an initial state is generated with gen_state/1
- all relevant constraints are added with constraint/3
- maximize/3 or minimize/3
are used to obtain a
*solved state*that represents an optimum solution - variable_value/3 and objective/2 are used on the solved state to obtain variable values and the objective function at the optimum.

The most frequently used predicates are thus:

**gen_state**(`-State`)- Generates an initial state corresponding to an empty linear program.
**constraint**(`+Constraint, +S0, -S`)- Adds a linear or integrality constraint to the linear program
corresponding to state
`S0`. A linear constraint is of the form`Left Op C`

, where`Left`is a list of`Coefficient*Variable`

terms (variables in the context of linear programs can be atoms or compound terms) and`C`is a non-negative numeric constant. The list represents the sum of its elements.`Op`can be`=`

,`=<`

or`>=`

. The coefficient`1`

can be omitted. An integrality constraint is of the form`integral(Variable)`

and constrains Variable to an integral value. **maximize**(`+Objective, +S0, -S`)- Maximizes the objective function, stated as a list of
`Coefficient*Variable`

terms that represents the sum of its elements, with respect to the linear program corresponding to state`S0`.`\`

arg{`S`} is unified with an internal representation of the solved instance. **minimize**(`+Objective, +S0, -S`)- Analogous to maximize/3.
**variable_value**(`+State, +Variable, -Value`)`Value`is unified with the value obtained for`Variable`.`State`must correspond to a solved instance.**objective**(`+State, -Objective`)- Unifies
`Objective`with the result of the objective function at the obtained extremum.`State`must correspond to a solved instance.

All numeric quantities are converted to rationals via rationalize/1,
and rational arithmetic is used throughout solving linear programs. In
the current implementation, all variables are implicitly constrained to
be *non-negative*. This may change in future versions, and
non-negativity constraints should therefore be stated explicitly.