0
$\begingroup$

Integer Programming formulation described as follows:

Assume a set of variable $V$ = ${v_1,...,v_m}$.

The set of total $S$ constraints is of the form:

$$v_1 + \overline{v_2} + v_3 \leq 1 \\ ... \\ \overline{v_2} + v_4 + v_6 \leq 1 $$

each called a clause, $C$.

Problem formulation (Objective function):

Find an assignment that satisfies maximum constraints (out of S constraints).

Formally: $$r(C) = max \sum_{C \in S} z_{C}$$

The variable $z_C$ will be 1 if the each corresponding constraint is true; for example in case $v_1 + \overline{v_2} + v_3 \leq 1$ is true and 0 otherwise.

I'm new to Integer programming and first tool that I tried MIP solver I can write all $S$ constraints easily. But I have no idea how to encode the objective function.

$\endgroup$
1
  • $\begingroup$ Note that you can replace any appearance of $\overline{v_u}$ with $1-v_u$. $\endgroup$ Commented Dec 31, 2019 at 18:54

1 Answer 1

Reset to default
1
$\begingroup$

The objective function to be maximized is $\sum_{C\in S} z_C$. You can define it here.

$\endgroup$
2
  • 1
    $\begingroup$ You can represent the "such that" part by defining constraints. $\endgroup$ Commented Dec 31, 2019 at 18:18
  • $\begingroup$ No problem. I recommend working through that complete example and modifying it. $\endgroup$ Commented Dec 31, 2019 at 18:27

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.