Questions tagged [integer-programming]
Questions on optimization constrained to integer variables.
802
questions
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 ...
