Questions tagged [linear-programming]

Questions on linear programming, the optimization of a linear function subject to linear constraints.

Filter by
Sorted by
Tagged with
4
votes
1answer
1k views

Lemke-Howson pivoting in degenerate bimatrix games

I'm working on an implementation of the Lemke-Howson algorithm for finding Mixed Nash Equilibria of bimatrix games, and I'm running into a roadblock when the algorithm is fed a degenerate game. For ...
4
votes
2answers
2k views

When change making problem has an optimal greedy solution?

A well-known Change-making problem, which asks how can a given amount of money be made with the least number of coins of given denominations for some sets of coins (50c, 25c, 10c, 5c, 1c) will ...
4
votes
1answer
133 views

Above what order of magnitude a pure cutting-plane algorithm must be forgotten in favour of branch-and-cut?

Crawling the web on the subject of the cutting-plane algorithm, I have seen everywhere that a pure cutting-plane method cannot be used for numerical instability reasons after some iterations. But do ...
4
votes
2answers
569 views

Help with formulating a linear programming problem

I have the following linear programming problem I would like to be verified: I have sketched the problem in the following picture: Here is my attempted solution: I figured that I have ten ...
4
votes
2answers
3k views

Linearizing min function Problem

How can I linearize $\min(x_1,x_2,x_3)$ in a maximization linear programming problem? Please help me. I've tried many things but I didn't solve.. My LP equations are as follows: Objective function is:...
4
votes
1answer
10k views

What does basic solution mean?

Linear programming: basic solution? If the matrix consists of $$\begin{bmatrix}1&-2&0&0&0\\-3&6&1&3&0\\0&0&2&6&-1\end{bmatrix},$$ how is it that there ...
4
votes
1answer
1k views

Developing Constraints for a linear programming based problem

Recently, I thought of developing a mathematical approach to a task I commonly do every week. Simply enough, it's a schedule. That said, I have a few questions regarding the process. I haven't ...
4
votes
1answer
2k views

Regarding complementary slackness condition

I have a question regarding complementary slackness, the answer should be true of false. The complementary slackness conditions connect pairs of optimal basic feasible solution of primal and dual ...
4
votes
3answers
4k views

Linear programming problem formulation

Stuck in this problem for quite a while. Anyone can offer some help? The problem is as follows: Fred has $5000 to invest over the next five years. At the beginning of each year he can invest money in ...
4
votes
1answer
701 views

How to minimize a function where the number of variables is unknown?

I have a standard linear programming problems I want to solve: $$ \min_x f^T x \text{ such that } \left\{ \begin{aligned} A\cdot x &\le b, \\ A_{eq}\cdot x &= b_{eq}, \\ lb \le x &\le ub. ...
4
votes
1answer
145 views

Does set remain bounded if these integer constraints are removed?

Question: Let $P$ be a nonempty polyhedron in $\mathbb{R}^n$, and let $l_i, u_i \in \mathbb{R}$ for all $i \in I$, where $I \subseteq \{1,\dots,n\}$. I'm looking at a problem where the feasible ...
4
votes
2answers
178 views

Is There an $ {L}_{1} $ Norm Equivalent to Ordinary Least Squares?

The ordinary least squares (OLS) method is very useful. It gives you the solution to the problem $$ \arg \min_{x} {\left\| A x - b \right\|}_{2}^{2} $$ Now, if the problem is the same, but the $1$-...
4
votes
1answer
112 views

Deriving a parameter in optimization problem

My question: My solution for the part (i) Hopefully my solution is correct. Especially check the budget constraint. If it is correct, then my actual question to you is the second part (i). I ...
4
votes
1answer
157 views

Integer programming formulation of Takuzu

A Takuzu is a logic-based number puzzle whose objective is to fill a (usually $10 \times 10$) grid with ones and zeros such that the following conditions are satisfied: Each row and each column have ...
4
votes
1answer
164 views

Exercise 2.27 from Bazaraa (LP)

Consider the system $Ax=b$ where $A=[a_1,a_2,...,a_n]$ is an $m \times n$ matrix of rank $m$. Let $x$ be any solution of this system. Starting with $x$, construct a basic solution. There is a hint ...
4
votes
2answers
251 views

prove that if A is M-matrix then A is also a P-matrix

$A \in \mathbb{R}^{n \times n}$ is a $P$-$matrix$ if all its principal minors are positive. Let $I$ be the identity matrix of rank $n$. $A \in \mathbb{R}^{nxn}$ is a non-singular $M$-$matrix$ if $A=...
4
votes
1answer
825 views

How to setup the correct transportation tableu for this Caterer Problem?

The problem said: A caterer must supply 110 napkins on Monday, 90 on Tuesday, 130 on Wednesday, and 170 on Thursday. The caterer initially has no napkins on hand. New napkins can be bought for ...
4
votes
1answer
179 views

Maximize $Z=-x+2y$ given $x\geq 3,\ x+y\geq 5,\ x+2y\geq 6,\ y\geq 0$

I am a highschool senior that's new to this topic. So, apologies for my lack of knowledge and misconceptions. The proof of the theory of this chapter is beyond the scope of my textbook, so that may be ...
4
votes
1answer
6k views

What's a basic solution, and how do we find them?

I've just started learning linear programming, and for some reason, have run into a question about something that isn't mentioned in the first chapter (and we're supposed to answer these questions ...
4
votes
1answer
2k views

Max flow min cut from duality

I have been having some trouble deriving the max flow min cut theorem from duality, which I was told is possible. To begin with, I need to cast the problem into the form "maximize $\langle c, x\...
4
votes
1answer
68 views

Is a System of Linear Equations the Right Way to Solve This Optimization Problem?

This is kind of a high-level question, in that I'm not sure which mathematical approach might be best for solving my problem. I'm trying to automate a painful, error prone, and time consuming process ...
4
votes
1answer
707 views

Writing a linear program in standard form

Usually I have been asked to write problems in standard form that have inequalities involved. However, this problem has none and I was wondering if anyone had insight on how to go about solving it. ...
4
votes
1answer
3k views

Absolute values in linear programming

Suppose I have an objective function in my LP as follows $max$ $|x|$ Based on some googling, I have found there are two ways to convert this into a standard LP. Method 1. $|x|$ = $ x^+ + x^-$ $x ...
4
votes
1answer
462 views

Solving special boolean equation set

I have boolean equation sets that look like this (where ^ means xor): eq 1: x1^x3^x5^x6^x9^x10^x11^x13^x17^x18 = 0 eq 2: 1^x1^x3^x10^x12^x17 = 0 eq 3: 1^x2^x3^x5^x8^x10^x14^x16 = 0 ...
4
votes
2answers
1k views

Converting if else constraints into linear ones

I have the following two constraints: $$ x_1 \leq x_2 \leq x_3 \qquad \mbox{if } x_1 \leq x_3 \\ x_1 > x_2 > x_3 \qquad \mbox{otherwise} $$ Is there a way to get rid of the two conditions and ...
4
votes
1answer
2k views

The size of the maximum matching is bounded by the size of the minimum vertex cover

Prove, using the weak duality theorem of linear programming, that: For any graph $G$ (not necessarily bipartite), the size of the maximum matching is at most the size of the minimum vertex cover. ...
4
votes
1answer
40 views

Is it necessary to state that $y_i \leq 1$

In a class test for Linear Programming, my professor deducted some marks because I missed the condition $y_i \leq 1$ in the mixed strategy games solution. $ y_i $ stands for the probability of any ...
4
votes
2answers
3k views

Linear programming problem with no objective function

I have a binary integer programming problem for which I only need a solution that meets all the constraints. I do not have an objective function that I am trying to minimize or maximize. I've been ...
4
votes
1answer
70 views

How can the formula be found for this problem?

We have a truck that we need to completely fill up with merchandise. We have an infinite supply of merchandise of dimension $1\times1\times1, 2\times2\times2, 4\times4\times4, 8\times8\times8, 16\...
4
votes
1answer
566 views

Dimension of solution space for system of linear inequalities

Let's say I have a system of inequalities: $Ax \leq g$ for some $A \in \mathbb{R}^{4\times4}$, $x \in \mathbb{R}^4$, $g \in \mathbb{R}^4$, and $A$ is full rank. Here, the $\leq$ denotes element-wise ...
4
votes
1answer
236 views

Efficiently solving a special integer linear programming with simple structure and known feasible solution

Consider an ILP of the following form: Minimize $\sum_{k=1}^N s_i$ where $\sum_{k=i}^j s_i \ge c_1 (j-i) + c_2 - \sum_{k=i}^j a_i$ for given constants $c_1, c_2 > 0$ and a given sequence of non-...
4
votes
1answer
553 views

Book on advanced topics of Network Flows

I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the ...
4
votes
1answer
809 views

solving linear program with rank constraint?

I have a linear program where the variables are n vectors. Now I'd like to impose an extra constraint that k (k<=n) of the n vectors are linearly independent, or the matrix with the n vectors as ...
4
votes
1answer
202 views

Linear algebra characterization of when half-spaces' intersection is bounded.

Suppose a finite set of $m$ half-spaces $H_i$ in $\mathbb{R}^n$ are described by equations $$ \mathbf{\ell}_i \cdot \mathbf{x} \leq 1. $$ for $1\leq i \leq m$. If $L$ is the $m\times n$ matrix ...
4
votes
0answers
894 views

Ways to speed up solving an LP with Google's ortools [closed]

I'm having an issue solving an LP of the form: $$\min z = c^Tx$$ $$\text{s.t.}$$ $$Ax \geq b$$ $$x\geq p$$ $1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$ The specific problems I'm running into ...
4
votes
0answers
50 views

Efficient Batched Linear Programming

Suppose I have a polyhedron given as $$ Ax \le b , x \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$$ and I have a collection of functions $c_1^Tx , c_2^T x ,\ldots, c_k^Tx$ that ...
4
votes
4answers
1k views

Determining existence of a solution for a system of linear inequalities

I have a set of vectors $\mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_m\in\mathbb{R}^n$ and I want to know if there exists a nonzero vector $\mathbf{x}$ such that $\mathbf{x}\cdot\mathbf{v}_i\le0$ for any ...
4
votes
0answers
92 views

I'm walking towards my car - when should I try the remote, in an optimal sense?

I'm interested to learn about how discrete/'event' based elements are incorporated into optimisation problems. Hopefully this is an interesting problem in its own regard, it's inspired by a daily ...
4
votes
0answers
17k views

How to find all basic feasible solutions of a linear system?

I'm trying to solve this problem but need some help getting started. The problem asks to find all the basic feasible solutions of the following system: \begin{equation} -4x_2+x_3=6 \end{equation} \...
4
votes
1answer
1k 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 ...
4
votes
0answers
965 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:...
4
votes
0answers
89 views

Is $K =\{ S: \exists \text{ positive diagonal} D, D^TSD \;\text{diagonally dominant}\}$ convex?

I am doing some convex cone optimization and wonder whether the following set $K_1$ is convex or not. Assume the following matrices are all in $\mathbb{R}^{n\times n}$ and symmetric. Let the set of ...
4
votes
0answers
204 views

Parameterizing equilateral polygons

I'm not exactly sure how to describe what I want, so if I butcher terms, please forgive me :) I want to "parameterize" the space of simple irregular equilateral polygons with n sides, or at least a ...
4
votes
1answer
96 views

Maximum / Minimum Question with 3 Variables?

I seem to be stuck in this problem, would need your help! Question: Assume I have : 147 of x, 174 of y, 238 of z A different amount of x, y ...
4
votes
0answers
157 views

Effective convexity criterion for the finite point set in $\mathbb{R}^3$

I need to find effective convexity criterion for the finite point set. Below there is description of what is meant by "effective" criterion. Definition. Let $M = \{A_{1}, \ldots, A_{n}\}$ be the ...
4
votes
0answers
806 views

Closed-form solution of the following LP problem

I am considering the following LP problem: $$ \begin{array}{cl} \text{maximize} & c^Tx\\ \text{subject to} & a^Tx\geq0 \\ & 0\leq x\leq x^\max \end{array} $$ where $c,a\in\mathbb{R}^{M\...
4
votes
2answers
9k views

What is the meaning of an “objective function” and “objective functionals”?

Right now I am in front of these expressions objective function objective functionals which seem to be very often used, but I've still not understood their meanings.
4
votes
0answers
105 views

Mappings preserving convex polyhedra

It is known that linear mappings between euclidean spaces map convex polyhedra to convex polyhedra. Can you give a characterization of the class of mappings that preserve convex polyhedra?
4
votes
0answers
680 views

fundamental theorem of linear inequalities

Do you know a proof for the fundamental theorem of linear inequalities, which does not employ an implicit use of the simplex algorithm? Let $a_1, \dots, a_n, b \in \mathbb R^m$. Then either $b$ is a ...
4
votes
0answers
419 views

intuitive explanation of Primal-Dual algorithms

I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...