1
$\begingroup$

Source of the Problem

The problem comes from an application in economics concerning trade between agents to maximize aggregate "wealth". More exactly, there are $m$ agents and $n$ groups and we perform independent trials where an agent interacting with a representative from a group yields either a success or a failure. Each agent $i$ has a probability of success $p_{i,j}$ when interacting with a representative from group $j$. Under constraints on how many group representatives an agent can interact with and how many representatives each group has, we want to maximize the expected number of total successes. This problem can be formalized as described in the following section (where the constant $\mathbf{c}^T$ is a vectorized form of the probabilities $p_{i,j}$).

The Problem

Consider the following integer linear program (ILP):

$$ \begin{aligned} & \underset{\mathbf{x}}{\text{maximize}} & & \mathbf{c}^T \mathbf{x} \\ & \text{subject to} & & \mathbf{A}\mathbf{x} = \mathbf{h} \\ & \text{and} & & \mathbf{x} \geq \mathbf{0} \end{aligned} \tag{ILP} $$

Where:

  • $\mathbf{c}^T$ is a fixed row vector of rational constants, having all of its entries between 0 and 1 (both endpoints included).
  • $\mathbf{A}$ is a fixed $(m+n) \times mn$-matrix. Specifically, $\mathbf{A}$ is constructed as: $$ \begin{bmatrix} \mathbf{V}_1^A \\ \vdots \\ \mathbf{V}_m^A \\ \mathbf{V}_1^G \\ \vdots \\ \mathbf{V}_n^G \end{bmatrix} $$
    • $\mathbf{V}_i^A$ is a row vector with the following value at position $k$: $$ \begin{cases} 1, & (i-1)n+1 \leq k \leq in \\ 0, & else \end{cases} $$
    • $\mathbf{V}_j^G$ is a row vector with the following value at position $k$: $$ \begin{cases} 1, & k \equiv j \mod{n} \\ 0, & else \end{cases} $$
  • Let $h$ be a strictly positive integer and assume $mh$ is divisible by $n$. $\mathbf{h}$ is a fixed column vector with the following value at position $k$: $$ \begin{cases} h, & 1 \leq k \leq m \\ \frac{mh}{n}, & m+1 \leq k \leq m+n \end{cases} $$

As an illustration, when $m = n = 2$, we obtain the following $\mathbf{A}\mathbf{x} = \mathbf{h}$: $$ \underbrace{ \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{bmatrix} }_\mathbf{A} \underbrace{ \begin{bmatrix} x_{1,1} \\ x_{1,2} \\ x_{2,1} \\ x_{2,2} \end{bmatrix} }_\mathbf{x} = \underbrace{ \begin{bmatrix} h \\ h \\ \frac{2h}{2} \\ \frac{2h}{2} \end{bmatrix} }_\mathbf{h} $$

My problem is as follows: For the general case, when $\mathbf{A}$ is a $(m+n) \times mn$-matrix, I want to find the solution $\mathbf{x}^*$ of my ILP as a function of the constant vector $\mathbf{c}^T$. That is, I want a formula telling me that a certain $\mathbf{c}^T$ results in a specific $\mathbf{x}^*(\mathbf{c}^T)$. I always keep $\mathbf{A}$ and $\mathbf{h}$ unchanged, I just want to see how the solution changes with $\mathbf{c}^T$.

I don't have any background in optimization. So far I have:

  • Concluded that $\mathbf{A}$ is a totally unimodular matrix. As a results of this, we may simply maximize $\mathbf{c}^T \mathbf{x}$ subject to the constraints and theorems from optimization guarantee that we will obtain an integer solution.
  • Started reading about the simplex algorithm, though not really implemented anything with it yet.
  • Started reading about the KKT-conditions for constrained optimization.

My question is thus:

  • Is it possible to obtain the formula I want, and if so how do I find it?

It seems extraordinarily tedious to use the simplex algorithm or the KKT-conditions to solve the problem in its general form, though perhaps that's the only way to get a general solution?

EDIT

Expressed perhaps too shortly to be clear: In economic terms, I'm quite sure the answer to the general situation is to let agents interact only with groups for which they have a comparative advantage over all other agents.

$\endgroup$
2
$\begingroup$

There is no closed form solution for an LP or MIP. For LPs we can say a few things about how the optimal solution may change when we start to perturb c (search for reduced cost and more generally: sensitivity analysis).

The simplex method is very good in finding optimal solutions to related problems. After changing some coefficients, it can often find the optimal solution in just very few iterations.

There are some good books on linear programming (e.g. Vanderbei, Chvatal).

$\endgroup$
  • 1
    $\begingroup$ And there is no "class" of ILPs which have closed form solutions? I feel my problem has such a natural interpretation that it should have an explicit solution for arbitrary c, if that makes sense. $\endgroup$ – SimonSimon May 1 '19 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.