Constraint Exchange Algorithms

Constraints Consensus

class disropt.algorithms.constraintexchange.ConstraintsConsensus(agent, enable_log=False)[source]

Bases: disropt.algorithms.algorithm.Algorithm

Constraints Consensus Algorithm [NoBu11]

This algorithm solves convex and abstract programs in the form

\begin{split} \min_{x} \: & \: c^\top x \\ \mathrm{subj. to} \: & \: x\in \bigcap_{i=1}^{N} X_i \\ & \: x \ge 0 \end{split}
x

current value of the local solution

Type

numpy.ndarray

B

basis associated to the local solution

Type

numpy.ndarray

shape

shape of the variable

Type

tuple

x_neigh

dictionary containing the local solution of the (in-)neighbors

Type

dict

sequence_x

sequence of local solutions

Type

numpy.ndarray

Parameters
  • agent (Agent) – agent to execute the algorithm

  • enable_log (bool) – True to enable log

compare_constr(a, b)[source]

Compare two constraints to check whether they are equal

compute_basis(constraints)[source]

Compute a (minimal) basis for the given constraint list

constr_to_dict(constraints)[source]

Convert constraint list to dictionary

dict_to_constr(dictio)[source]

Convert dictionary to constraint list

get_basis()[source]

Return agent basis

get_result()[source]

Return the current value of x

Returns

value of x

Return type

numpy.ndarray

iterate_run(event)[source]

Run a single iterate of the algorithm

run(iterations=100, verbose=False, event=None, **kwargs)[source]

Run the algorithm for a given number of iterations

Parameters
  • iterations (int, optional) – Number of iterations. Defaults to 100.

  • verbose (bool) – If True print some information during the evolution of the algorithm. Defaults to False.

Return type

ndarray

Returns

the sequence of computed solutions if enable_log=True.

unique_constr(constraints)[source]

Remove redundant constraints from given constraint list

Distributed Simplex

class disropt.algorithms.constraintexchange.DistributedSimplex(agent, problem_size=None, local_indices=None, enable_log=False, stop_iterations=None, big_M=500.0)[source]

Bases: disropt.algorithms.algorithm.Algorithm

Distributed Simplex Algorithm [BuNo11]

This algorithm solves linear programs in standard form

\begin{split} \min_{x} \: & \: c^\top x \\ \mathrm{subj. to} \: & \: Ax = b \\ & \: x \ge 0 \end{split}

When reading the variable agent.problem.constraints, this class only considers equality constraints. Other constraints are discarded.

x

current value of the complete solution

Type

numpy.ndarray

J

current value of the cost

Type

float

x_basic

current value of the basic solution

Type

numpy.ndarray

B

basis associated to the local solution

Type

numpy.ndarray

n_constr

number of constraints of the problem

Type

tuple

B_neigh

dictionary containing the local bases of (in-)neighbors

Type

dict

A_init

initial constraint matrix

Type

numpy.ndarray

b_init

initial constraint vector

Type

numpy.ndarray

c_init

initial cost vector

Type

numpy.ndarray

sequence_x

sequence of solutions

Type

numpy.ndarray

sequence_J

sequence of costs

Type

numpy.ndarray

Parameters
  • agent (Agent) – agent to execute the algorithm

  • problem_size (list) – total number of variables in the network. Defaults to None. If both problem_size and local_indices is provided, the complete solution vector will be computed.

  • local_indices (list) – indices of the agent’s variables in the network, starting from 0. Defaults to None. If both problem_size and local_indices is provided, the complete solution vector will be computed.

  • enable_log (bool) – True to enable log

  • stop_iterations (int) – iterations with constant solution to stop algorithm. Defaults to None (disabled).

  • big_M (float) – cost of big-M variables. Defaults to 500.

check_index_consistency()[source]

Check consistency of local indices, problem_size and constraint matrix

get_basis()[source]

Return current basis

get_result()[source]

Return the current value of the solution

Returns

value of primal solution, primal basic solution, dual solution, cost

Return type

tuple of nd.ndarray (primal, primal_basic, dual, cost)

initialize()[source]

Evaluate a first solution and basis starting from agent’s constraints through the Big-M method

iterate_run(event)[source]

Run a single iterate of the algorithm

read_problem_data()[source]

Read local problem data from agent.problem. The data is saved in order to be solved as a standard form problem.

run(iterations=100, verbose=False, event=None, **kwargs)[source]

Run the algorithm for a given number of iterations

Parameters
  • iterations (int, optional) – Maximum number of iterations. Defaults to 100.

  • verbose (bool) – If True print some information during the evolution of the algorithm. Defaults to False.

Raises

TypeError – The number of iterations must be an int

Return type

ndarray

Returns

return a tuple (x, J) with the sequence of solutions and costs if enable_log=True.

Dual Distributed Simplex

class disropt.algorithms.constraintexchange.DualDistributedSimplex(agent, num_constraints=None, local_indices=None, enable_log=False, stop_iterations=None, big_M=500.0)[source]

Bases: disropt.algorithms.constraintexchange.DistributedSimplex

Distributed Simplex Algorithm on dual problem [BuNo11]

This algorithm solves linear programs of the form

\begin{split} \max_{x} \: & \: c^\top x \\ \mathrm{subj. to} \: & \: Ax \le b \end{split}

This class runs the Distributed Simplex algorithm on the (standard form) dual problem.

Parameters
  • agent (Agent) – agent to execute the algorithm

  • num_constraints (list) – total number of constraints in the network. Defaults to None. If both num_constraints and local_indices is provided, the complete dual solution vector will be computed.

  • local_indices (list) – indices of the agent’s constraints in the network, starting from 0. Defaults to None. If both num_constraints and local_indices is provided, the complete dual solution vector will be computed.

  • enable_log (bool) – True to enable log

  • stop_iterations (int) – iterations with constant solution to stop algorithm. Defaults to None (disabled).

  • big_M (float) – cost of big-M variables. Defaults to 500.

check_index_consistency()[source]

Check consistency of local indices, num_constraints and constraint matrix

get_result()[source]

Return the current value of the solution

Returns

value of primal solution, dual basic solution, dual solution, cost

Return type

tuple of nd.ndarray (primal, dual_basic, dual, cost)

read_problem_data()[source]

Read local problem data from agent.problem. The data is saved in order to be solved as a standard form problem.

References

NoBu11

Notarstefano, G.; Bullo, F.: Distributed abstract optimization via constraints consensus: Theory and applications.

BuNo11(1,2)

Bürger, M.; Notarstefano, G.: A distributed simplex algorithm for degenerate linear programs and multi-agent assignments.