# Questions tagged [integer-programming]

Questions on optimization constrained to integer variables.

802 questions
Filter by
Sorted by
Tagged with
23 views

### Total unimodular matrices

I am trying to establish the following relationship. If $T$ is a $m \times n$ $TU$ matrix with the property that all rows of $T$ have the same number of non-zero entries and all entries $\geq 0$. Then ...
25 views

### Primal and Dual infeasibility

I have the following relationship for the primal and dual problems listed below. $Max: c^{T}x$ $s.t: Ax\leq-c$ $x\geq0$ where $c \in \mathbb{R}^{m}$ and $A^{T} = -A$. I have formulated the dual ...
23 views

### Let $F$ be a face of a polyhedron $P$ and $P'$ the first Chvátal closure of $P$. Then $F' = P' \cap F$.

The above is a lemma from my class. I'm looking at this picture below to make sense of it. In the picture, I'm focusing on the face $F$ of $P$ defined by (1)(2)(4). I've learned that $P'$ is defined ...
23 views

### Find matrices given sums of each row and column with bounded integer entries: maximize zero-valued entries

I want to find solutions for the following problem. It seems to be a classic problem in integer programmimg and logistics, but I don't know its name. Find a matrix of m rows and n columns, with non-...
11 views

### Minimize time of production/quality check/packaging with parallel processes

My gf came with this problem from a linear programming class where they mostly did cost optimization. You have two plants, plant 1 produces 80 units per hour, plant two produces 60 units/hour -> these ...
18 views

### Solve Constrained zero-one Integer Linear Program Using Simulated Annealing

Recently, I was reading about several techniques that solves Unconstrained Mixed Integer Linear Programs (UM-ILP) using a meta-heuristic algorithm called simulated annealing. I was thinking about the ...
17 views

### For a polyhedron $P$ associated with an LP, find a polyhedral description of the integer polyhedron $P_{IP}$ using Gomory-Chvátal cuts.

Consider the polyhedron $P=\left\{\left(x_{1}, x_{2}\right) \in \mathbb{R}_{+}^{2}: x_{1}+4 x_{2} \leq 8, x_{1}+x_{2} \leq 4\right\} .$ Find a polyhedral description of $P_{I P}$ using GC-cuts. What ...
138 views
+50

### Gomory-Chvátal Cut and Closure

We're having the following definitions and example in our lecture. I'm getting a bit confused. What is the first Chvátal closure of $P$ in this picture (please be specific)? Why is it not necessarily ...
37 views

### Integer programming , a transport problem

A truck with a maximum capacity of 10 boxes must transport food boxes, medicine boxes and boxes of surgical supplies. You cannot transport more than 5 boxes of the same type and if you transport more ...
30 views

### Integer programming problem.

I do not know the integer programming problem. I am reading a paper (1 below) which makes the following claim for the problem P1. I have two questions regarding this claim which I will post after ...
21 views

### Integer programming : linearize product of constants given conditions

I have some constant values $c_i$ in $(0.5, 2)$. I also have binary variables $x_i$. For my integer program, for a particular constraint, I need to multiply only those $c_i$ when $x_i$ takes the value ...
25 views

### Dealing with ABSOLUTE VALUE and IF STATEMENT in linear integer programming

I am trying to write a linear constraint that computes the absolute value of a difference, only if both the variables $x$ and $y$ are different from zero. $x,y$ are binary variables while $s$ is a ...
37 views

### How can i find the solution of this NP-hard optimization problem?

I have an NP-Hard optimization problem of the form: \begin{align} & \min {{\sum\limits_{i=1}^{M}{{{a}_{i}}}}_{{}}} \\ & s.t{{.}\:\:\:\:_{{}}}{{_{{}}}_{{}}}\sum\limits_{i=1}^{M}{{{a}_{i}}{{...
21 views

### Approach to solving for all variables (whole numbers) in this linear and quadratic equation?

Suppose of I have the following setup: $$a + b + c... = m$$ $$a^2 + b^2 + c^2... = n$$ $$0 < a < b < c ... < l$$ Where $m,n,l$ are known constants and there are an arbitrary number of ...
41 views

### Dantzig decomposition and Column Generation for equality constraints

I was trying to apply Dantzig Decomposition followed by Column Generation. The following is how I was taught. \begin{array}{l} \text { Minimize }-10 x_1-2 x_{2}-4 x_{3} \\ \text { subject to: } x_{1}+...
52 views

### Any $(x, y, z)$ can satisfy the $5x^2+2y^2+6z^2-6xy-2xz+2yz<0$?

Please tell me whether there any $(x, y, z)$ which can satisfy the $5x^2+2y^2+6z^2-6xy-2xz+2yz<0$ ? No process or just solve it by calculator are both fine. Thank you.
14 views

35 views

### Division in linear program

In my linear program, I have an inequality constraint as follows. $$x + \frac{y}{g(z)} \leq c$$ where $x \in \mathbf{R}^+, y \in \{0, 1\}$, and $g(z)$ is a function of $z \in \mathbf{Z}_{\geq 0}$ ...
58 views

### Showing that a polyhedron doesn't contain an integral point

I have the following question: I have to decide if a polytope $P = \{x\in\mathbb{R}_{\geq 0}^{\ell}\mid Ax=0\}$ contains an integral point except $x=0$, for hundreds or thousands of different matrices ...
13 views

### Linearizing nonlinear constraints with square term

I am trying to solve an optimization problem with the following constraints. \begin{align} & n_m = \sum_{i=1}^I x_{im}T_i \quad \forall m\\ & n_m^{'} = \sum_{i=1}^I x_{im}C_i \quad \forall \\...
24 views

### Minimisation of the Number of Questions for 160 Papers [duplicate]

An exam centre is going to prepare question papers for 160 students where each paper has 9 questions from 9 different topics (one question per topic). They can allow upto 2 collisions, i.e. at most 2 ...
29 views

### Linear program decomposition and Column Generation

I needed to decompose a large LP of equality constraints. $\\Dx=B^1,$ $\\Ax=B^2,$ $\\D \in R^{m^{(1)} \times n}$ $\\A\in R^{m^{(2)} \times n}, m<<n$ $A$ has a block diagonal structure and $D$ ...
35 views

### Choosing Variable to generate a Node in a MILP

I'm trying to find or understand rigorous a criterion about choosing the variable to generate a new Node in the Branch and Bound method. Usually the methods I've seen just choose the variable nearly ...
24 views

### Converting a conditional constraint (if-then) to integer linear programming.

How can I linearly express the following conditional constraint: If x1 = 1 (x1 is selected) then x2+x3 = 0 (x2 and x3 is not selected) if x1,x2 and x3 are binary?
11 views

### Proving a set has integer extreme points

The hint says to use TU Properties, but I don't know how to express P as a matrix to use the properties Any help is appreciated
22 views

### The existence of an optimal solution in a MILP guarantees existence of the optimal solution in the relaxation problem?

I'm following a description of the Branch and Bound Method. But I don't understand at all, that if you assume a MILP problem has an optimal solution it implies that the relaxation problem has also ...
19 views

### Integer program for minimizing maximum Lateness with precedence constraints

In studying for an upcoming exam the following problem came up: Write an integer program to: minimize the maximum Lateness for the one machine scheduling problem with precedence constraints and ...
13 views

### Optimization of maximal independent set

One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum independent set of a graph with no weights. I was then asked to show ...
24 views

30 views

A problem arose to solve the problem with a solution that became impracticable. Well, I have a set of 12 elements that represent quantities: $$\Omega = \{16, 132, 135, 135, 136, 138, 138, 139, 301, ... 2answers 37 views ### Solving Knapsack with Multiple Constraints and Return nth Best Results Example Data For this question, let's assume the following items: Items: Apple, Banana, Carrot, Steak, Onion Values: 2, 2, 4, 5, 3 Weights: 3, 1, 3, 4, 2 Max Weight: 7 Objective: My goal is to ... 1answer 30 views ### school math, equations and minimal steps problem [closed] I have the following problem:  X(20A + 88C) + Y(32B + 72C) + Z(40A + 40B) \ge 616A + 890B + 982C the second condition is that the sum of  X + Y + Z  should be as low as possible. If there is ... 1answer 22 views ### Total Unimodularity of set of equality and inequality constraints by partitioning of rows Consider binary decision variables x_{ij} and y_j where  i \in \{1,2,\ldots,I\} and  j \in \{1,2,\ldots,J\} for fixed integers I and J. Consider the following feasibility prolem: \begin{... 1answer 22 views ### Efficiency in terms of basic and non basic variables of a LP I have a LP design for my problem(not relevant) where most of the variables gets assigned the value of 0. I want to scale the LP to more variables and equations, and thus want to know the ... 0answers 22 views ### Is the maximum matching LP totally dual integral? Is the maximum matching LP (\Gamma(S)  is the set of edges with both endpoints in S, \delta(S) is the set of edges with exactly one point in S)$$ 2\sum x_e \ \ \{ e \in E \} \\ s.t. \\...
Let $$P=\{x\in R^m: Ax=b, Bx\leq d, x\geq 0 \}$$ and $$Q=\{(x,y)\in R^{m+n}: Ax=b, Bx+y=d, x\geq 0, y\geq 0 \}$$ be given systems of linear inequalities. Assume $Q$ is an integral polyhedron with ...