Questions tagged [integer-programming]

Questions on optimization constrained to integer variables.

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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-...
-1
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
2answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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}}{{...
0
votes
1answer
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 ...
1
vote
0answers
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}+...
1
vote
4answers
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.
0
votes
0answers
14 views

derived variable of when it is appeared

I am dealing with a multi traveling passenger problem $x_{i,j}$ is a binary variable that allocate a passenger $i$ to a vehicle $j$, every vehicle can carry only $n_{pv}$ passenger where $i \in \{1,...
0
votes
3answers
66 views

How to solve this six variables of simultaneous equation? [closed]

The problems is: $A^2+D^2=5$ $B^2+E^2=2$ $C^2+F^2=6$ $AB+DE=3$ $BC+EF=1$ $AC+DF=1$ Please tell me what is the roots for this simultaneous equation, no process or just solve it by calculator are ...
0
votes
0answers
15 views

Obtaining the integral hull with Chvatal closure

I have to solve the following task and I'm not sure if my thoughts are correct. It would be really great, if somebody could please help me: Obtain the integral hull of $\lbrace z \in \mathbb{Z}: Bz \...
0
votes
2answers
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}$ ...
1
vote
2answers
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 ...
0
votes
0answers
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 \\...
0
votes
0answers
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 ...
1
vote
1answer
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$ ...
1
vote
1answer
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 ...
0
votes
1answer
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?
-1
votes
1answer
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
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
24 views

How to determine if a integer linear equation with contraints is solvable?

I want to write an efficient program to the determine if the following equation is solvable. The equation and the constraints look like this: $$\begin{align} &\sum_{i=1}^{n}a_ix_i=0\quad(\forall ...
2
votes
2answers
159 views

Combinatorics - Optimisation (Minimum number of questions)

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 ...
0
votes
2answers
32 views

Optimize combination of cards to least multicolored cards

I asked a question about how to calculate a combination of specific color pair cards. I'd now like to optimize the calculation in a way, that the least number of triple and double colored cards are ...
0
votes
1answer
34 views

polytopes and integer programming

Given a connected graph $G$ with vertex set $V(G)$, a set $S\subseteq V(G)$ is called a dude set if every vertex of $V(G)\setminus S$ is adjacent to at least one vertex of $S$. Let $\mathcal{D}$ ...
0
votes
0answers
9 views

Networks and Submodularity

I have no idea in proving a problem in graph theory. Let $G$ be a direct graph on vertex set $V(G)$ and edge set $E(G)$. Assume that $V(G)$ has a special "source vertex" $s$ and a special "sink vertex"...
0
votes
1answer
69 views

Proving lower bound of Integer Linear Program (ILP)

Consider an Integer Linear Program (ILP) of the following form: ILP 1: Minimize $c^1x^1 + c^2 x^2+ c^3 x^3$ Subject to: \begin{align} A^1x^1 &\leq b^1\\ A^2x^2 &\leq b^2\\ A^3_1x^1 + A^3_2x^...
0
votes
1answer
32 views

LP Relaxation is unbounded

How do I go about proving the integer linear program has an optimal solution, but that its linear program relaxation is unbounded? \begin{equation} \begin{array}{cl} {\max} & {x_1} \\ {\text{s.t.}...
0
votes
0answers
20 views

this question is related to operation research .( facility location problem)

This is a conceptual facility location problem. I want advice on how one would approach it. We have 20 stands, each plotted on a 2d map. Each stand demands a certain # of apples per year. We are ...
0
votes
1answer
30 views

Optimizing a shortest path problem

I am asked to formulate shortest path problem as a min-cost flow problem and I am stuck on the following step: Min cost flow probelm can be formulated as https://en.wikipedia.org/wiki/Minimum-...
2
votes
1answer
74 views

Quickly Finding Positive Solutions to Diophantine Equations

I'm wondering if someone can help point me to the fastest available methods for solving problems like the following: Given positive integers $C, D,$ find the smallest positive integers $x$ and $y$...
1
vote
1answer
29 views

Problem with big-M logical constraints

Consider a linear optimization problem with two variables $u_1, u_2$: $$\begin{array}{rl} \max_{u_1, u_2} & k_1 u_1 + k_2 u_2\\ \text{s.t.}\\ & 0 \leq u_1 \leq a_1\\ & 0 \leq u_2 \leq a_2 ...
0
votes
0answers
30 views

Computing the set of integral points of a convex hull

Assume that we have integral points $x_1, \ldots, x_n \in \lbrace 0, \ldots, l - 1 \rbrace^3$ for some $l \in \mathbb{N}_{> 0}$, that the vertices of the associated convex hull are given by $v_1, \...
0
votes
0answers
34 views

Integer optimization method

Suppose I have to maximize $f(n)=\displaystyle\sum_{i=0}^n{(2-i)}.$ Which of these two methods is correct (generally, not only for this example)? 1) Since $f(n)=\displaystyle\sum_{i=0}^n{(2-i)}=\...
1
vote
2answers
68 views

Combinatorial optimization (find partitions)

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, ...
1
vote
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 ...
-3
votes
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 ...
1
vote
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{...
1
vote
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 ...
0
votes
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. \\...
1
vote
1answer
34 views

integral polyhedron and projection

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 ...

1
2 3 4 5
17