3
$\begingroup$

Say I have an binary integer programming problem:

\begin{equation*} \begin{aligned} & \underset{\mathbf{x,y}}{\text{minimize}} & & f_0(\mathbf{x,y}) \\ & \text{subject to} & & (\mathbf{x,y}) \in A \\ \end{aligned} \end{equation*} with $(\mathbf{x},\mathbf{y}) = (x_1, \ldots, x_{N}, y_1, \ldots, y_{M}) \in \{0,1\}^{N+M}$

and say I would like to model the set $A$ with conditions such as:

$\quad \quad y_i = 1$ if $g_c(\textbf{x}_C) = 1$ for some clique $c$ of variables in $\mathbf{x}$, where $g_c$ is a boolean function (e.g. a function derived from a truth table using a Karnaugh map).

$\quad \quad y_i = 0$ otherwise.

How would you model a condition like this using linear inequalities, matrix inequalities or second-order cones? Also, how would you progressively tighten their relaxation?

Here is an example of how to model other relationships:

Let's say I want to model a disjunctive constraint on the variables $\mathbf{x}$. Suppose we have two constraints \mathbf{a'\cdot x}\ge b and \mathbf{c'\cdot x}\ge d, and we would like to model the requirement that at least one of the two constraints is satisfied using linear inequalities. To achieve this, we can define a binary variable $y$ and impose the constraints:

\mathbf{a'\cdot x}\ge yb, \quad \mathbf{c'\cdot x}\ge (1-y)d, with $y\in\{0,1\}$

Motivation

I am interested in using conditional statements to model conditional penalties in the cost function. More specifically, if a solution to my practical problem is given by an assignment to the variables $\mathbf{x}$, I could use the auxiliary variables $\mathbf{y}$ to add conditional penalties when certain conditions are met. For example, I could expand $f_0(\mathbf{x,y})$ as $f_0(\mathbf{x,y}) = f_1(\mathbf{x}) + f_2(\mathbf{y})$, where $f_2(\mathbf{y}) = \sum_{1}^{M}{y_i c_i}$, where $c_i$ are the extra penalties incurred for the configurations of $\mathbf{x}$ declared in the conditional statements.

  • 0
    I didn't realize $g_c$ could be nonlinear. Obtaining linear constraints with a generic nonlinear function - that sounds really nasty, and I don't know how to do it. In fact, my guess is that it's not possible (although I would be happy to be proved wrong).2011-07-28

0 Answers 0