Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
1answer
63 views

Integer programming, system of linear inequalities.

I am woring on a problem and I got these inequalities. $t_{01}+t_{11}+t_{21}\ge 4$ $t_{02}+t_{12}+t_{22}\ge 4$ $t_{10}+t_{11}+t_{12}\ge 4$ $t_{10}+t_{01}+t_{22}\ge 4$ $t_{10}+t_{02}+t_{21}\ge 4$ ...
0
votes
0answers
28 views

Integer program with known non-integer “solutions”

I have an integer program (IP) (see the formulation here for example) with the matrix $A$ being total unimodular. In this case, the linear program (LP) relaxation of the IP provides an integer ...
0
votes
0answers
29 views

Mixed-integer (Linear) Programming (MILP) standard/canonical form

Is there a standard or canonical form for mixed-integer (linear) programming problems? For linear programms the standard form is sometimes given by: $$ \max_{\boldsymbol x} \boldsymbol c^T \boldsymbol ...
0
votes
0answers
23 views

All facets' coefficients contain only integers -1,0,1

Suppose a polytope $C\subset \mathbb R^{kl}$ is the $l$-product of $k-1$-simplex with extreme points containing coordinates $0$ or $1$ in each coordinate. A linear transformation is given by ...
0
votes
1answer
24 views

integer valued outer normal vectors

Suppose a bounded polyhedra $C$ is given by $$x\in \mathbb R^n: Ax\leq b$$ The matrix $A\in\mathbb R^{m\times n}$ contains only elements from $\{-1,0,1\}$, which implies the outer normal vectors of ...
0
votes
2answers
39 views

Polynomial time solvable cases of the knapsack problem.

Is there some restricted version of the knapsack problem, which is not $Np$-complete and there is a polynomial time algorithm? In my cases the weights are all power of $2$, so $(1, 2, 4, 8, 16, ...
1
vote
3answers
191 views

What are common Mathematical Programming Languages out there?

I've seen the term used Mathematical Programming to describe a superset of: Linear programming Quadratic programming Nonlinear programming Mixed-integer programming Mixed-integer nonlinear ...
1
vote
1answer
62 views

MILP optimization constraint formulation

I'm trying to find a sensible way to add constraint for my optimization problem. Lets assume we have binary decision variables $x_i\in\{0,1\}$ and two constraints \begin{align*} \sum\limits_{i=1}^n ...
1
vote
0answers
37 views

Lenstra's integer programming algorithm: Finding a lattice point “near the center”

Preliminaries: As part of Lenstra's algorithm for integer programming (see here, page 4) we compute a linear transformation $\tau$ and a point $z \in \mathbb{R}^n$ which meet certain conditions (step ...
0
votes
1answer
77 views

Can the “goat cabbage wolf” problem be solved using integer programming?

Question: Can you solve the "goat cabbage wolf" problem using integer programming. If so could I get an outline of the solution or a reference to one?
0
votes
2answers
53 views

What method will work for this linear programming problem?

I just started studying linear programming and I have limited resources with which to work. I have to work on a number of exercises but the notes I have do not help much so I have to look online for ...
0
votes
1answer
52 views

Network flow as a linear/integer programming problem with special conditional constraints

Consider the classic network flow problem where the constraint is that the inflow to a vertex is equal to the sum of its outflows. Consider having a more specific constraint where the flow cannot be ...
0
votes
1answer
20 views

Find the global/local minima of a quadratic function over the set of integer?

Sorry for my poor English, I'm trying to find the global and local minima of a quadratic function: $x^2 - 3x$, with $x \in Z $. Here is my solution: It is straightforward to find the global minima ...
0
votes
0answers
21 views

Multiple Choice Integer Program Special Ordered Set Naming

I have been given a problem, for which I have a hard time to find literature, since I'm unsure about the right name of the problem. The problem is defined as: We have given $k$ sets and we need to ...
1
vote
0answers
73 views

Shadow prices in assignment problems (and their relationship to Lagrange multipliers of LP-relaxation)

Lagrange multipliers for linear programs can be interpreted as shadow prices. Shadow prices typically represent marginal/differential changes in the objective from a marginal loosening of a given ...
1
vote
1answer
42 views

Binary variable in a constraint

I have the following optimization problem: Model I: $$f(x,y) \\ s.t., \\ y\leq x+M(1-V)\\ y \leq MV \\ x \geq 0, y \geq 0$$ where x and y are continuous variables whereas V is a binary variable. M ...
0
votes
1answer
42 views

How to formulate LP for shortest path problems?

I'm trying to understand how LP formulaton for shortest path problem. However I'm having trouble understanding constrains. Why this formulation work? http://ie.bilkent.edu.tr/~ie400/Lecture8.pdf ...
0
votes
1answer
96 views

Binary integer program with nonlinear function

I have given a matrix $A^{m \times n}$ and I am looking for a submatrix $B^{m \times k}$ for a given $k$ that maximizes the following expression: $$\sum_{i=1}^m \max_{j \in \{1 \dots k\}} B_{i,j}$$ ...
0
votes
2answers
28 views

Mixed Integer Linear Programming Conditional Constraints

I have a set of variables: $x_1,x_2,x_3,x_4$ $x_1$ is a binary integer variable while the rest are real numbers all between 0 and 1 I want a constraint such that: if $x_2+x_3+x_4$>0 then $x_1$=1 ...
0
votes
2answers
26 views

Integer Programming Conditional Constraints

I have a set of integer [0,1]variables $x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4$ I want a conditional constraint such that if any of the $x$ variables is equal to 1, I want the sum of the subsequent $y$ ...
3
votes
1answer
132 views

Linear constraints to placing N queens on an N x N chessboard?

I'm trying to formulate the problem of placing N queens on an N x N chessboard such that no two queens share any row, column, or diagonal. I managed to define my decision variable as x[n][n], a ...
0
votes
1answer
70 views

Is this matrix totally unimodular? [closed]

Is this matrix totally unimodular? Thank you in advance! $A=\begin{pmatrix} -1& 0& 0& 0& -1\\ 0& 1& 1& 0& 0\\ 1& 0& 0& 1& 0\\ 0& ...
0
votes
0answers
63 views

Hungarian Method algorithm question. Dual solution.

I have included two images which I have to prove the next problem. The first image is the alternate(k) algorithm (alternate paths algorithm) and the second is the Hungarian Method algorithm. ...
1
vote
2answers
47 views

How can I maximize this expression?

Let $d_1,...,d_n$ be non-negative integers such that $d_1 + ... + d_n = n -1$ and $d_{i} \leq i$. What is the value of the following expression: $\sum_{i=1}^n d_i (n - i)$ when maximized (a good ...
2
votes
0answers
29 views

Showing the integrality property for an Integer Linear Program

I am trying to figure out why solving a relaxed Integer Linear Program (ILP) always give an integral solution. The ILP can be summarized as: $$\min \sum_{t\in T} \sum_{s \in S} c_s k_s^t $$ subject ...
0
votes
0answers
12 views

Definition of support of a nonzero vector

I am studying integer programming and specifically Graver Basis and Circuits. However, to define a circuit they use the term of support of a non zero vector $supp(c)$ and say it is minimal. Does ...
0
votes
1answer
88 views

Linear programming. Find the maximum number of vertex disjoint paths in a directed graph.

How I can write like an objective function subject to its corresponding restriccions the next problem? (max "...") subject to ($\sum "..." - \sum "..."=0$ $\forall$ "...") I have a directed graph ...
0
votes
1answer
21 views

The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$). This is what I observed from some books (e.g. "Combinatorial ...
0
votes
1answer
29 views

Beyond quadratic in binary integer programming

If I have an integer programming problem with binary decision variables in a quadratic objective function with quadratic constraints, I can solve it using branch and bound in a few different solvers. ...
0
votes
1answer
19 views

Integer Programming Problem - Machines To Products

A man is trying to decide how he can assign his five machines to four products in order to maximize output. The estimated output per day for each machine is shown and reflect its productivity for each ...
0
votes
0answers
12 views

Totally uni-modular matrix

I encountered the following matrix and am wondering whether it is totally uni-modular or not: $$\begin{bmatrix} A_{n\times m} & 0_{n\times m}\\ I_{n\times m} & I_{n\times m}\\ ...
2
votes
2answers
75 views

Linear Programming Model (or IP) - Staff Allocation

A retailer is trying to decide how best to assign its 3 staff to two internal departments in order to maximize sales. The estimated sales revenues per day for each staff member are shown and reflect ...
2
votes
0answers
48 views

Approximate algorithms for integer linear programming (for optimal subset selection)

I'm trying to select an optimal subset of some items. I've tried 2 optimal approaches (branch-and-bound and integer programming) but both proved impossible for the size of the problem. I'm wondering ...
1
vote
1answer
27 views

How to increase the lower bound on possible counter-examples to the Collatz Conjecture?

According to Wikipedia, all positive integers up to $2^{60}$ have been tested and follow the Collatz Conjecture. This got me thinking, could one write a program that tests integers of the form $2^{60} ...
1
vote
0answers
24 views

Social welfare convergence in large assignment problems with random utilities

Suppose there are $N$ agents each to be assigned one of $N$ objects. The utility an agent gets for a particular object is drawn uniformly, i.i.d., from the set of integers between $0$ and $100$ ...
0
votes
1answer
24 views

Optimization of a colour graph

Formulate as a discrete optimization problem: Label each node of the graph with a different non negative integer number, in such a way that the numbers of the nodes of each path composed of the same ...
1
vote
1answer
43 views

Defining an integer (binary) linear program to solve a logistics problem

As an analogy, lets say I have $k$ buckets and $n$ items I want to put into these buckets. So we have binary variables $x_{ij}$ ($1 \leq i \leq n$, $1 \leq j \leq k$), whether or not we put the ...
0
votes
2answers
199 views

Binary integer LP problem

Joe Henderson runs a small metal parts shop. The shop contains three machines – a drill press, a lathe, and a grinder. Joe has three operators, each certified to work on all three machines. ...
0
votes
1answer
90 views

Formulation of mutually exclusive condition

So I have two integer variable and they can be one of the following $x=0, y=1$ $x=1, y=0$ $x=2, y=0$ how can I formulate this as an integer program? I've gotten $x + y \le 2$ and $y \le 1$ ...
4
votes
0answers
118 views

ax+by+cz<=d, find the maximum value of ax+by+cz.

I am recently calculating that kind of questions as shown in title. And of course, I use a lot of time to find the answer. Therefore I would like to know how I can calculate faster. Q.: ax + by + ...
0
votes
0answers
15 views

Adding an upper bound increases the number of branching nodes

I am solving a maximization problem by means of integer programming and have observed the following curiosity: When I add an upper bound in the input for the solver (an upper bound that is tighter ...
1
vote
0answers
19 views

Integer programming - multi-set partitioning

I'm trying to solve this question: Let S be a multi-set of n integers, can S be partitioned into two sub-multi-sets $S1$,$S2$, such that: $$ \sum_{x \in S1} x = \sum_{y \in S2} y $$ I'm trying to ...
1
vote
0answers
27 views

How to determine the smallest N such that there are X (or more) prime numbers with exactly N bits?

I understand how I can use the prime number theorem to determine how many primes exist for a given bit length: $\pi(2^n)-\pi(2^{n-1})$. However, my specific problem is that I need to approach this ...
0
votes
1answer
43 views

Zero-one linear programming with substitutable constraints

Suppose $x_1, x_2, \ldots, x_n$ each take values zero or one and we want to solve the following linear programming problem: $$ \min_{x_1,x_2,\ldots, x_n} f(x_1,x_2,\ldots,x_n) $$ subject to a bunch ...
0
votes
1answer
114 views

How can linearize the product of decision variables in ILP?

Here, we have something like this: R + (1-R)T + (1-R)(1-T)S + (1-R)(1-T)(1-S)Q = 1 where R, T, S, Q are binary decision variable How can I convert this ...
0
votes
1answer
35 views

01-integer programming

can someone please explain to me what is meant by easily converting negative objective function coefficients? This may seem like a restrictive set of conditions, but many problems are easy to ...
0
votes
0answers
58 views

Find all answers to a Mixed-Integer-Linear-Program using branch and bound?

I am trying to solve a MILP which might have multiple answers (all give the same value for objective function). Is a branch and bound based algorithm able to find all solutions? Is it possible to ...
4
votes
1answer
200 views

Why calculating XOR of consecutive values can be simplified? [duplicate]

I was trying to calculate integer xor of 0..n. I named the function xored(n). Note that in examples below ^ does not mean power but integer xor (like in C or Java language) So, xored(0) = 0, ...
2
votes
1answer
67 views

Prove that this matrix is total unimodular

Is there an easy way to prove that this matrix is total unimodular ? $$ \begin{bmatrix} 1 & F_1 & 0\\ 1 & 0 & F^T_1 \\ 0 & F_2 \end{bmatrix} $$ $1$ is the identity matrix, ...
0
votes
1answer
19 views

Lattice points in simplices - reference request

I found this paper http://homepages.math.uic.edu/~yau/35%20publications/An%20upper.pdf which, in formulas (1.2) and (1.3), relates the number of non-negative and positive integer values that are ...