Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
0answers
12 views

Maximizing iterations of finding circular successive differences

From a competition we had in comp sci: Given four integers, $a$, $b$, $c$, and $d$ take repeated absolute differences including $|a-d|$ until you reach all zeros. At each iteration, $a' \gets |b-a|...
4
votes
0answers
46 views

Name for “Almost a vector space, but with $\mathbb{N}_0$ instead of a field”

I have a finite set of vectors $V\subset \mathbb{R}^n$ Let us enumerate $V = \{\tilde{v}_1, \tilde{v}_2,...,\tilde{v}_m\}$ I have some space that I want to talk about (I spend a lot of time talking ...
1
vote
1answer
68 views

To show a closed convex set $S \subseteq R^n$ is bounded if and only if $S$ contains no rays.

I want to show that a closed convex set $S \subseteq R^n$ is bounded if and only if $S$ contains no rays. Where $r \in S$ is a ray of $S$ if $x \in S$ implies that $x+\mu r \in S$ for all $\mu \in R_{...
0
votes
1answer
38 views

How to solve mixed-integer problem?

I don't know how to solve this equation, $$\left\lceil\frac{x-A}{B}\right\rceil C + D x < E, \quad x\in \mathbb{Z}$$ In this equation, only $x$ is unknown and $x$ is integer, but $A,B,C,D,E$ are ...
2
votes
0answers
28 views

Discrete Optimization Problem (VRP)

Consider the following setting : We have two pickup nodes (a) and (b)and two delivery nodes (c) and (d). At each pickup node, there are entities to be picked up and delivered by cars (n cars) to ...
1
vote
1answer
35 views

Are there combinatorial problems that admit closed form solution? [closed]

I was wondering if there's some classes of combinatorial problems (specifically assignment problems) something like maximize: $$ f(\vec{x}) = \sum_{i,j} x_{i}x_{j}2^{i+j}, \;\; x_i \in {0,1} \;\;\...
0
votes
2answers
30 views

Writing conditional logic using mathematics forumla

I'm working on an application which has a specific function which receives 2 ints: x and y. If y > x then I would like the function to return y otherwise return x - y. Just a few examples: f(10, 12)...
1
vote
2answers
55 views

Boolean equation

$$\text{Solve for}\space{x, y}$$ $${a_1, a_2, a_3, a_4, b_1, b_2} \; \text{ - variables}$$ $$\left\{ \begin{aligned} {a_1}\&x \oplus {a_2}\&y &= {b_1} \\ {a_3}\&x \oplus {a_4}\&y ...
2
votes
0answers
33 views

Why does the cutting plane method for integer programming run in exponential time?

I am looking for a proof of the fact that the cutting plane algorithm for integer programming does not run in polynomial time. The algorithm consists in adding constraints to the initial problem in ...
-2
votes
2answers
80 views

Integer programming [closed]

Can anyone help me to find the right solution? How can integer programming be used to ensure that X takes on values 1,3, 5 or any even number less than 100? In practice we have a integer ...
0
votes
1answer
39 views

For any integer $n$ find $x<n$, and $y<n$ to minimize the natural number $z=xy-n$

I need to develop an algorithm for finding the optimal dimensions for setting a set of symbols on a grid (for a typesetting library I'm writing). I need to minimize the number of cells in my grid ...
0
votes
1answer
32 views

Modeling integers in NLP

I was wondering why it is not OK to model binary (integer) variables of an optimization problem, in the following form x(x-1) = 0 What are the consequences for ...
0
votes
0answers
27 views

Approximate ratio with a small fraction so that numerator multiplied by denominator give enough rectangular area?

I would like to layout given number of objects (like plots) into rectangular area (like computer operating system window on screen). I would like to calculate the width and height of the window (in ...
1
vote
1answer
60 views

Set up an integer programming problem so that all variables in the solution are different [closed]

I have a relatively simple minimisation problem. I have to minimise a linear function with many variables (more than 20), and I would like all the solutions to be different and in set $ x \in \{1,...,...
0
votes
0answers
29 views

Converting a linear-fractional program with an integer constraint to a linear program

Is it possible to convert the following linear-fractional program to a linear program ? $$ \max_x \frac{v\cdot x}{z \cdot x}\\s.t \\x_i \in \{0,1\}\\ \\ \sum_i x_i = k$$ where $v \in R^{d}$, $z \in R^...
0
votes
0answers
13 views

Optimize polling frequency between producer and consumer to achieve minimum waiting time

Background: I am trying to optimize what we call AJAX request polling frequency in the domain of web design, and I wanted to check if I could use some help from math guys to explore a better ...
3
votes
1answer
43 views

solve $54 x + 16 y = 2400$ for integer values of x,y

How to get integer values for x and y that satisfy: $$54 x + 16 y = 2400$$ Someone told me that I can do it using Euclid-Wallis algorithm, but I don't understand it so, if there isn't any else ...
1
vote
1answer
55 views

What is the difference between linear and integer programming?

Recently I tried to solve a maximization integer programming problem using linear programming by flooring the max point - but got the wrong answer. I'm wondering if someone can explain mathematically ...
2
votes
1answer
45 views

Solving integer programming problem using the graphical method

I have an integer programming problem I need to solve using the graphical method. Maximize $55x_1 + 500x_2$ such that $$\begin{align} 4x_1 + 5x_2 &\le 2000\\ 2.5x_1 + 7x_2 &\le 1750\\ ...
3
votes
1answer
113 views

Discrete Linear Programming over Finite Fields?

$A$ is an $l\times m$ matrix with integer entries and each column of which contains at least one negative entry. $y$ is a column matrix with integer entries of length $l$. Define the set of sequence $...
0
votes
0answers
15 views

Reference Request For Hermite normal form of non full row rank matrix

Could someone recommend me some references which discuss the problem of the reduction of a matrix which is not full row rank into its Hermite normal form?
0
votes
0answers
37 views

Conditions for a totally unimodular coefficient matrix of a Multi-Commodity-Minimum-Cost-Flow-Problem

I'm considering the following Multi-Commodity-minimum-Cost-Flow-Problem: This leads us to a coefficient matrix $A$ with $N$ donates the incidence matrix of a directed graph and $I$ is the ...
1
vote
0answers
31 views

How to interpret this integer program

I'm having problem understanding the min weight st-cut integer programming in this wiki page: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem In the min-cut dual part, it has $$d_{ij}-p_i+p_i ...
0
votes
1answer
146 views

Normalized objective function in optimization problem

I have fairly standard linear optimization model with two objectives \begin{align*} \text{max}\, (f_1 &= 4x_1+5 x_2\,,\,f_2 = 1x_1 + 0x_2 ) \\ \text{subject to}& \\ 1x_1 + 1x_2 &...
0
votes
0answers
91 views

KKT conditions (equations) for Generalized Assignment Problem or Binary integer programming problem

I have this formulated Generalized Assignment Problem (GAP) or it can also be considered as Binary integer programming problem. Solving this problem can be achieved through Branch and Bound Technique. ...
1
vote
1answer
69 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
31 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
33 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 $L:\...
0
votes
1answer
25 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
43 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
253 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
74 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
39 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
79 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
56 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
55 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
81 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
43 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
46 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 I'...
0
votes
1answer
100 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}$$ ...
1
vote
3answers
55 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
31 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
156 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
77 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& 1&...
0
votes
0answers
67 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. Question:...
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
31 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 to:...