Does real linear programming produce bipartite perfect matching using maxflow reduction?

Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram:

enter image description here

We can formulate max flow as an linear programming problem with integer variables in latter.

  1. If we do not use integer variables does solving for maxflow in linear programming formulation with only real variables still produce valid perfect matching of given graph?

  2. Is there a formal proof of this?

Linear order minimizing weighted distance from special element

Let’s say I have a set of beads, $ b_0,\dots,b_n$ , and let $ b_0$ be the ‘special bead’. I want to lay out the beads on a string to minimize the total cost, defined as $ \sum_{i=1}^n w_i \cdot d(b_0, b_i)$ , where the weights $ w_i$ are given, and the distance is computed as the number of beads between the two corresponding beads.

The minimum cost for every position of $ b_0$ can be calculated in linear total time (plus $ n \log n$ pre-processing time to sort the weights), by noting that the optimal solution is to pair up the beads on either side by increasing weight, with a residual ‘tail’ on the longer side, and working out how the cost changes as you shift $ b_0$ along.

What if some of $ b_1,\dots,b_n$ are fixed in given positions?

Obviously quadratic time is possible by solving each sub-problem independently, but is there an incremental algorithm akin to the case without any fixed beads?

If-Then with disjunctions (OR) in Integer Linear Programming (ILP)

I have the following constraints I’m trying to model in Linear Integer Programming. I will try out diverse solvers for this later, but first I need to model the problem.

Given the integer variables: x1, x2, x3, x4, y1, y2, y3, y4, I have the following constraints:

IF (y1 ≤ y3 ≤ y2  OR  y1 ≤ y4 ≤ y2) THEN (x1 ≥ x4  OR  x2 ≥ x3) 

Additionally for all of these variables I have upper and lower bounds.

I think I have to use the “big M” technique, but I’m not sure how to handle the logical OR in the IF condition and in the THEN condition and how to built up one complete model.

Does anyone of you know how to resolve this? Many thanks in advance.

Linear mathematical formulation of a congestion game

I need to implement the following congestion game in AMPL:

Let $ J=\{1,2,3,4\}$ be a set of jobs and let $ M=\{1,2,3\}$ be a set of machines.

  • Job 1 can be solved by machines 1 and 2.
  • Job 2 can be solved by machines 1 and 3.
  • Job 3 can be solved by machines 2 and 3.
  • Job 4 can be solved by machines 2 and 3.

Each job uses only one machine.

The time required by each machine to solve a job depends on its congestion (namely, the number of different jobs assigned to the machine) as follow:

  • Machine 1: $ time_1=[1,3,5,7]$
  • Machine 2: $ time_2=[2,4,6,8]$
  • Machine 3: $ time_3=[3,4,5,6]$

The element $ i$ of the vector $ time_m$ is equal to the time required by machine $ m$ given a congestion equal to $ i$ .

[e.g.] if machine 1 solves job 1 and 2, thus the congestion of machine 1 is equal to 2, then the resolution of these jobs (1 and 2) requires time equal to $ time_1(2)=3$ . (indexing starts from 1)

The aim is to solve all the jobs in a way such that the maximum time among the machines is minimum.

The implementation problem is that I need to use as index the variable “congestion” and that’s not allowed in AMPL.

Is there any way to implement this game as a linear problem in AMPL? What’s the mathematical linear programming formulation without using variable as indexes of the “time matrix” (the matrix having as rows $ time_i$ )?

Gram-Schmidt process in Java for computing independent bases in linear spaces

Given a set of $ k$ $ n$ -vectors $ x_1, \dots, x_k$ , Gram-Schmidt proces computes a basis $ y_1, \dots, y_m$ ($ m \leq k$ ) the vectors of which span the same space as $ x_1, \dots, x_k$ but are mutually orthogonal: $ (y_i, y_j) = 0$ for all $ i \neq j$ , where the parentheses denote inner product $ $ (x, y) = \sum_{i = 1}^n x_i y_i. $ $

Below is my code:

net.coderodde.math.Additive

package net.coderodde.math;  /**  * This interface defines the API for adding the two elements.  *   * @param <I1> the type of the left operand.  * @param <I2> the type of the right operand.  * @param <O>  the sum type.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ public interface Additive<I1, I2, O> {      /**      * This method adds {@code a} and {@code b} and returns the sum.      *       * @param a the first element.      * @param b the second element.      * @return the sum of the two given numbers.      */     public O add(I1 a, I2 b); } 

net.coderodde.math.Demo

package net.coderodde.math;  import net.coderodde.math.impl.ComplexVectorProductByScalar; import net.coderodde.math.impl.ComplexNumber; import net.coderodde.math.impl.ComplexVectorAdditive; import net.coderodde.math.impl.ComplexVectorDivisible; import net.coderodde.math.impl.ComplexVectorInnerProduct; import net.coderodde.math.impl.ComplexVectorNegative; import net.coderodde.math.impl.RealVectorAdditive; import net.coderodde.math.impl.RealVectorDivisible; import net.coderodde.math.impl.RealVectorInnerProduct; import net.coderodde.math.impl.RealVectorNegative; import net.coderodde.math.impl.RealVectorProductByScalar;  /**  * This class runs a simple demo for the Gram-Schmidt process.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ final class Demo {      public static void main(String[] args) {         Vector<Double> x1 = new Vector<>(1., -1., 1., -1.);         Vector<Double> x2 = new Vector<>(5., 1., 1., 1.);         Vector<Double> x3 = new Vector<>(-3., -3., 1., -3.);          Vector<Double>[] orthogonalBasis1 =                  new GramSchmidtProcess<>(new RealVectorInnerProduct(),                                          new RealVectorDivisible(),                                          new RealVectorProductByScalar(),                                          new RealVectorAdditive(),                                          new RealVectorNegative())                 .process(x1, x2, x3);          for (Vector<Double> vector : orthogonalBasis1) {             System.out.println(vector);         }          System.out.println("Orthogonal: " +                  isOrthogonal(orthogonalBasis1[0],                              orthogonalBasis1[1],                              0.00001));          System.out.println("------");          // [(1, -2), (3, 4)] = [1 - 2i, 3 + 4i]         Vector<ComplexNumber> c1 = new Vector<>(new ComplexNumber(1, -2),                                                 new ComplexNumber(3, 4));          // [(0, -3), (1, 1)] = [-3i, 1 + i]         Vector<ComplexNumber> c2 = new Vector<>(new ComplexNumber(0, -3),                                                 new ComplexNumber(1, 1));          Vector<ComplexNumber>[] orthogonalBasis2 =                  new GramSchmidtProcess<>(new ComplexVectorInnerProduct(),                                          new ComplexVectorDivisible(),                                          new ComplexVectorProductByScalar(),                                          new ComplexVectorAdditive(),                                          new ComplexVectorNegative())                 .process(c1, c2);          for (Vector<ComplexNumber> c : orthogonalBasis2) {             System.out.println(c);         }                  System.out.println("Orthogonal: " +                  isOrthogonalComplex(orthogonalBasis2[0],                                     orthogonalBasis2[1],                                     0.00001));     }      public static <E, IP> boolean basisIsOrthogonal(Vector<Double>[] basis,                                                    double epsilon) {         for (int i = 1; i < basis.length; i++) {             Vector<Double> target = basis[i];              for (int j = 0; j < i; j++) {                 Vector<Double> current = basis[j];                  if (!isOrthogonal(target, current, epsilon)) {                     return false;                 }             }         }          return true;     }      public static boolean basisIsOrthogonalComplex(             Vector<ComplexNumber>[] basis, double epsilon) {         for (int i = 1; i < basis.length; i++) {             Vector<ComplexNumber> target = basis[i];              for (int j = 0; j < i; j++) {                 Vector<ComplexNumber> current = basis[j];                  if (!isOrthogonalComplex(target, current, epsilon)) {                     return false;                 }             }         }          return true;     }      private static boolean isOrthogonal(Vector<Double> a, Vector<Double> b, double epsilon) {         double sum = 0.0;          for (int i = 0; i < a.getNumberOfDimensions(); i++) {             sum += a.get(i) * b.get(i);         }          return sum < epsilon;     }      private static boolean isOrthogonalComplex(Vector<ComplexNumber> a,                                                Vector<ComplexNumber> b,                                                double epsilon) {         ComplexNumber sum = new ComplexNumber(0, 0);          for (int i = 0; i < a.getNumberOfDimensions(); i++) {             ComplexNumber product = a.get(i).multiply(b.get(i));             sum = sum.add(product);         }          return Math.abs(sum.getRealPart()) < epsilon &&                Math.abs(sum.getImaginaryPart()) < epsilon;     } } 

net.coderodde.math.Divisible

package net.coderodde.math;  /**  * This interface defines the API for division operator.  *   * @param <D1> the type of the divident.  * @param <D2> the type of the divisor.  * @param <F>  the fraction type.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ public interface Divisible<D1, D2, F> {      /**      * Divides {@code a} by {@code b} and returns the result.      *       * @param divident the object being divided.      * @param divisor  the divisor.      * @return the result of dividing {@code divident} by {@code divisor}.      */     public F divide(D1 divident, D2 divisor); } 

net.coderodde.math.GramSchmidtProcess

package net.coderodde.math;  import java.util.Arrays; import java.util.HashSet; import java.util.Objects; import java.util.Set;  /**  * This class implements the method for running   * <a href="">https://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process</a>  * over a given independent basis of a linear space.  *   * @param <VCT> the vertex component type.  * @param <IPT> the inner product type.  * @param <FT>  the division result type.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ public class GramSchmidtProcess<VCT, IPT, FT> {      /**      * This object is responsible for computing the inner product of two       * vectors.      */     private InnerProduct<VCT, VCT, IPT> innerProduct;      /**      * This object is responsible for computing division.      */     private Divisible<IPT, IPT, FT> divisible;      /**      * This object is responsible for computing products (multiplication).      */     private Product<FT, Vector<VCT>, Vector<VCT>> product;      /**      * This object is responsible for computing addition.      */     private Additive<Vector<VCT>, Vector<VCT>, Vector<VCT>> additive;      /**      * This object is responsible for computing negative elements.      */     private Negative<Vector<VCT>, Vector<VCT>> negative;      /**      * Constructs the object with the method for running Gram-Schmidt process       * over given basis.      *       * @param innerProduct the object for computing inner products.      * @param divisible    the object for performing division.      * @param product      the object for performing multiplication.      * @param additive     the object for performing addition.      * @param negative     the object for computing inverses.      */     public GramSchmidtProcess(InnerProduct<VCT, VCT, IPT> innerProduct,                               Divisible<IPT, IPT, FT> divisible,                               Product<FT, Vector<VCT>, Vector<VCT>> product,                               Additive<Vector<VCT>,                                        Vector<VCT>,                                        Vector<VCT>> additive,                               Negative<Vector<VCT>, Vector<VCT>> negative) {         this.innerProduct =                  Objects.requireNonNull(                         innerProduct,                         "The input InnerProduct is null.");          this.negative = Objects.requireNonNull(negative,                                                  "The input Negative is null.");          this.product = Objects.requireNonNull(product,                                                "The input Product is null.");          this.divisible = Objects.requireNonNull(divisible,                                                  "The input Divisible is null.");          this.additive = Objects.requireNonNull(additive,                                                "The input Additive is null.");     }      /**      * Performs the Gram-Schmidt process upon {@code basis}.      *       * @param basis the basis to process.      * @return the orthogonal basis.      */     public Vector<VCT>[] process(Vector<VCT>... basis) {         // Validate the input basis:         checkBasis(basis);          // Deal with the very first base element:         Vector<VCT>[] orthogonalBasis = new Vector[basis.length];         orthogonalBasis[0] = (Vector<VCT>) new Vector(basis[0]);          // The actual process:         for (int i = 1; i < basis.length; i++) {             // Copy-construct 'x' from 'basis[i]':             Vector<VCT> x = new Vector<>(basis[i]);              // For each basis element before 'x', do:             for (int j = 0; j < i; j++) {                 // Take the inner product of the divident:                 IPT innerProductDivident =                          this.innerProduct.innerProductOf(x, orthogonalBasis[j]);                  // Take the inner product of the divisor:                 IPT innerProductDivisor =                          this.innerProduct.innerProductOf(orthogonalBasis[j],                                                          orthogonalBasis[j]);                  // Divide the divident by divisor:                 FT fraction = divisible.divide(innerProductDivident,                                                innerProductDivisor);                  // Multiply the above by the current basis:                 Vector<VCT> term = product.multiply(fraction, basis[j]);                  // Negate the above:                 term = negative.negate(term);                  // Add the above to 'x'. Effectively, it subtracts 'term' from                 // 'x' since we have negated 'term':                 x = additive.add(x, term);             }              orthogonalBasis[i] = x;         }          // Remove the duplicates and return whatever is left:         return removeDuplicates(orthogonalBasis);     }      /**      * This method validates the input data sent to the Gram-Schmidt process      * implementation above.      *       * @param <E>            the element component type.      * @param basisCandidate the basis candidate.      * @throws IllegalArgumentException if the candidate is not valid.      */     private static <E> void checkBasis(Vector<E>[] basisCandidate) {         // Check not null:         Objects.requireNonNull(basisCandidate, "The input basis is null.");          // Check is not empty:         if (basisCandidate.length == 0) {             throw new IllegalArgumentException("No vectors given.");         }          int expectedDimensions = basisCandidate[0].getNumberOfDimensions();          // Each element in the basis candidate must have the same          // dimensionality:         if (expectedDimensions == 0) {             throw new IllegalArgumentException(                     "The element at index 0 has no components.");         }          for (int i = 1; i < basisCandidate.length; i++) {             if (basisCandidate[i].getNumberOfDimensions() == 0) {                 // Oops. An empty element:                 throw new IllegalArgumentException(                         "The element at index " + i + " has no components.");             }              if (expectedDimensions                     != basisCandidate[i].getNumberOfDimensions()) {                 // Oops. Not all basis elements are of the same equal                  // dimensionality:                 throw new IllegalArgumentException(                     "Element dimension mismatch: expected " +                             expectedDimensions + " but was " +                              basisCandidate[i].getNumberOfDimensions() +                             " at index " + i + ".");             }         }     }      private static <E> Vector<E>[] removeDuplicates(Vector<E>[] basis) {         Set<Vector<E>> set = new HashSet<>(Arrays.asList(basis));         Vector<E>[] vectors = new Vector[set.size()];         return set.toArray(vectors);     } } 

net.coderodde.math.InnerProduct

package net.coderodde.math;  /**  * This interface defines the API for inner product over given vector component  * type.  *   * @param <VCT1> the left vector type.  * @param <VCT2> the right vector type.  * @param <IPT>  the inner product value type.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ public interface InnerProduct<VCT1, VCT2, IPT> {      /**      * Computes the inner product of the two given vectors.      *       * @param a the first vector.      * @param b the second vector.      * @return the inner product       */     public IPT innerProductOf(Vector<VCT1> a, Vector<VCT2> b); } 

net.coderodde.math.Negative

    package net.coderodde.math;  /**  * This interface defines the API for computing negative of given values.  *   * @param <I> the input type.  * @param <O> the output type.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ public interface Negative<I, O> {      /**      * Returns the negative of {@code element}. The negative of {@code a} is       * {@code -a} such that {@code a + (-a) = O}, where {@code O} is the zero      * element.      *       * @param element the element to negate.      * @return the negative of {@code element}.      */     public O negate(I element); } 

net.coderodde.math.Product

package net.coderodde.math;  /**  * This interface defines the API for multiplication (product).  *   * @param <E1> the type of the left element to multiply.  * @param <E2> the type of the right element to multiply.  * @param <O>  the product result type.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ public interface Product<E1, E2, O> {      /**      * Returns the product of {@code a} and {@code b}.      *       * @param a the first element.      * @param b the second element.      * @return the product of the two input elements.      */     public O multiply(E1 a, E2 b); } 

net.coderodde.math.Vector

package net.coderodde.math;  import java.util.Arrays; import java.util.Objects;  /**  * This class implements a vector/element in a {@code n}-dimensional space.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ public final class Vector<E> {      /**      * The actual vector contents.      */     private final E[] components;      /**      * Constructs the vector from the given data.      *       * @param components the vector data.      */     public Vector(E... components) {         Objects.requireNonNull(components, "The input vector is null.");         this.components = Arrays.copyOf(components, components.length);     }      /**      * Copy-constructs this vector.      *       * @param vector the vector to copy.      */     public Vector(Vector<E> vector) {         this.components = Arrays.copyOf(vector.components,                                          vector.components.length);     }      /**      * Returns the {@code index}th component of this vector.      *       * @param index the component index.      * @return the value of the {@code index}th component.      */     public E get(int index) {         return components[index];     }      /**      * Sets the value of the {@code index}th vector component to the given       * value.       *       * @param index the index of the target vector component.      * @param value the value to set.      */     public void set(int index, E value) {         components[index] = value;     }      /**      * Returns the number of components in this vector.      *       * @return the number of components in this vector.      */     public int getNumberOfDimensions() {         return components.length;     }      @Override     public String toString() {         StringBuilder stringBuilder = new StringBuilder("<");         String separator = "";          for (E component : components) {             stringBuilder.append(separator);             separator = ", ";             stringBuilder.append(component);         }         return stringBuilder.append(">").toString();     }      @Override     public int hashCode() {         return Arrays.hashCode(components);     }      @Override     public boolean equals(Object o) {         if (o == null) {             return false;         }          if (o == this) {             return true;         }          if (!o.getClass().equals(this.getClass())) {             return false;         }          Vector<E> other = (Vector<E>) o;         return Arrays.equals(components, other.components);     } } 

net.coderodde.math.impl.ComplexNumber

package net.coderodde.math.impl;  /**  * This class implements a complex number. The complex number consists of a real  * part and an imaginary part. The imaginary part is a real number equipped with  * the imaginary unit {@code i}, for which {@code i^2 = -1}. This class is  * immutable.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 18, 2019)  */ public final class ComplexNumber {      /**      * The real number.      */     private final double realPart;      /**      * The imaginary number.      */     private final double imaginaryPart;      /**      * Constructs a new complex number.      *       * @param realPart      the real part of the newly constructed complex       *                      number.      * @param imaginaryPart the imaginary part of the newly constructed complex      *                      number.      */     public ComplexNumber(final double realPart, final double imaginaryPart) {         checkNotNan(realPart);         checkNotNan(imaginaryPart);         checkNotInfinite(realPart);         checkNotInfinite(imaginaryPart);         this.realPart = realPart;         this.imaginaryPart = imaginaryPart;     }      /**      * Returns the real part of this complex number.      *       * @return the real part of this complex number.      */     public double getRealPart() {         return realPart;     }      /**      * Returns the imaginary part of this complex number.      *       * @return the imaginary part of this complex number.      */     public double getImaginaryPart() {         return imaginaryPart;     }      /**      * Returns the complex number that is equal to the sum of this complex       * number and the {@code other} complex number.      *       * @param other the complex number to add.      * @return the sum of this and {@code other} complex number.      */     public ComplexNumber add(ComplexNumber other) {         return new ComplexNumber(realPart + other.realPart,                                   imaginaryPart + other.imaginaryPart);     }      /**      * Returns the negative of this complex number.      *       * @return the negative of this complex number.       */     public ComplexNumber negate() {         return new ComplexNumber(-realPart, -imaginaryPart);     }      /**      * Returns the complex number representing the product of the two input       * complex numbers.      *       * @param a the first complex number.      * @param b the second complex number.      * @return the product of {@code a} and {@code b}.      */     public ComplexNumber multiply(ComplexNumber complexNumber) {         double a = realPart;         double b = imaginaryPart;         double c = complexNumber.realPart;         double d = complexNumber.imaginaryPart;         double resultRealPart = a * c - b * d;         double resultImaginaryPart = a * d + b * c;         return new ComplexNumber(resultRealPart, resultImaginaryPart);     }      /**      * Returns a simple textual representation of this complex number.      *       * @return the textual representation of this complex number.      */     @Override     public String toString() {         if (realPart == 0.0 && imaginaryPart == 0.0) {             return "0.0";         }          if (realPart == 0.0) {             return imaginaryPart + "i";         }          if (imaginaryPart == 0.0) {             return Double.toString(realPart);         }          if (imaginaryPart < 0.0) {             return realPart + " - " + Math.abs(imaginaryPart) + "i";         }          return realPart + " + " + imaginaryPart + "i";     }      /**      * Checks that the input {@code double} value is not {@code NaN}.      *       * @param d the value to check.      * @throws IllegalArgumentException in case {@code d} is {@code NaN}.      */     private void checkNotNan(double d) {         if (Double.isNaN(d)) {             throw new IllegalArgumentException("NaN");         }     }      /**      * Checks that the input {@code double} value is finite.      *       * @param d the value to check.      * @throws IllegalArgumentException in case {@code d} is not finite.      */     private void checkNotInfinite(double d) {         if (Double.isInfinite(d)) {             throw new IllegalArgumentException("Infinite");         }     } } 

net.coderodde.math.impl.ComplexVectorAdditive

package net.coderodde.math.impl;  import net.coderodde.math.Additive; import net.coderodde.math.Vector;  /**  * This class implements the addition operation over complex vectors.  *   * @author Rodion "rodde" Efremov  * @version 1.6:P (May 18, 2019)  */ public final class ComplexVectorAdditive          implements Additive<Vector<ComplexNumber>,                             Vector<ComplexNumber>,                             Vector<ComplexNumber>> {      /**      * Adds the complex vectors {@code a} and {@code b} and returns the       * component-wise copy of the object. Both input complex vectors remain      * intact.      *       * @param a the left summation operand.      * @param b the right summation operand.      * @return the sum vector.      */     @Override     public Vector<ComplexNumber> add(Vector<ComplexNumber> a,                                       Vector<ComplexNumber> b) {         ComplexNumber[] complexNumbers =                  new ComplexNumber[a.getNumberOfDimensions()];          for (int i = 0; i < a.getNumberOfDimensions(); i++) {             complexNumbers[i] = a.get(i).add(b.get(i));         }          return new Vector<>(complexNumbers);     } } 

net.coderodde.math.impl.ComplexVectorDivisible

package net.coderodde.math.impl;  import net.coderodde.math.Divisible;  /**  * This class implements the division operator over complex numbers.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 18, 2019)  */ public final class ComplexVectorDivisible implements Divisible<ComplexNumber,                                                                ComplexNumber,                                                                ComplexNumber> {      /**      * Divides the complex {@code divident} by the complex {@code divisor} and       * returns the fraction. Both the input complex numbers remain intact.      *       * @param divident the complex divident.      * @param divisor  the complex divisor.      * @return the fraction after dividing the divident by the divisor.      */     @Override     public ComplexNumber divide(ComplexNumber divident, ComplexNumber divisor) {         // TODO: could do Karatsuba multiplication here, I guess.         double a = divident.getRealPart();         double b = divident.getImaginaryPart();         double c = divisor.getRealPart();         double d = divisor.getImaginaryPart();          double resultRealPart = (a * c + b * d) / (c * c + d * d);         double resultImaginaryPart = (b * c - a * d) / (c * c + d * d);          return new ComplexNumber(resultRealPart, resultImaginaryPart);     } } 

net.coderodde.math.impl.ComplexVectorInnerProduct

package net.coderodde.math.impl;  import net.coderodde.math.InnerProduct; import net.coderodde.math.Vector;  /**  * This class implements computing inner product over complex vectors.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 18, 2019)  */ public final class ComplexVectorInnerProduct          implements InnerProduct<ComplexNumber, ComplexNumber, ComplexNumber> {      /**      * Computes the inner product of {@code a} and {@code b} and returns it to      * the caller.      *       * @param a the first operand.      * @param b the second operand.      * @return the inner product.      */     @Override     public ComplexNumber innerProductOf(Vector<ComplexNumber> a,//1 -2i                                         Vector<ComplexNumber> b) {//1 -2i         ComplexNumber innerProduct = new ComplexNumber(0.0, 0.0);          for (int i = 0; i < a.getNumberOfDimensions(); i++) {             ComplexNumber complexNumber1 = a.get(i);             ComplexNumber complexNumber2 = b.get(i);             ComplexNumber product = complexNumber1.multiply(complexNumber2);             innerProduct = innerProduct.add(product);         }          return innerProduct;     } } 

net.coderodde.math.impl.ComplexVectorNegative

package net.coderodde.math.impl;  import net.coderodde.math.Negative; import net.coderodde.math.Vector;  /**  * This class implements the negation operation over complex numbers.  *   * @author Rodino "rodde" Efremov  * @version 1.6 (May 18, 2019)  */ public final class ComplexVectorNegative          implements Negative<Vector<ComplexNumber>,                             Vector<ComplexNumber>> {      /**      * Negates every component in {@code element} and returns the resulting       * vector. The input vector remains intact.      *       * @param element the element to negate.      * @return the element with all the components negated compared to the       *         input vector.       */     @Override     public Vector<ComplexNumber> negate(Vector<ComplexNumber> element) {         Vector<ComplexNumber> result = new Vector<>(element);          for (int i = 0; i < element.getNumberOfDimensions(); i++) {             result.set(i, result.get(i).negate());         }          return result;     } } 

net.coderodde.math.impl.ComplexVectorProductByScalar

package net.coderodde.math.impl;  import net.coderodde.math.Product; import net.coderodde.math.Vector;  /**  * This class implements multiplying complex vectors by a complex scalar.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 18, 2019)  */ public final class ComplexVectorProductByScalar          implements Product<ComplexNumber,                             Vector<ComplexNumber>,                             Vector<ComplexNumber>>{      /**      * Multiplies the complex vector by the given complex scalar and returns the      * result. All the input objects remain intact.      *       * @param scalar the scalar to multiply by.      * @param vector the complex vector to multiply.      * @return the {@code vector} multiplied by {@code scalar}.      */     @Override     public Vector<ComplexNumber> multiply(ComplexNumber scalar,                                            Vector<ComplexNumber> vector) {         Vector<ComplexNumber> ret = new Vector<>(vector);          for (int i = 0; i < vector.getNumberOfDimensions(); i++) {             ret.set(i, ret.get(i).multiply(scalar));         }          return ret;     } } 

net.coderodde.math.impl.RealVectorAdditive

package net.coderodde.math.impl;  import net.coderodde.math.Additive; import net.coderodde.math.Vector;  /**  * This class implements addition over {@code double}-valued vectors of an  * Euclidean space.  *   * @author Rodion "rodde" Efremov   * @version 1.6 (May 17, 2019)  */ public final class RealVectorAdditive implements Additive<Vector<Double>,                                                           Vector<Double>,                                                           Vector<Double>> {      /**      * Adds component-wise the contents in {@code a} and {@code b} and returns       * the sum. Both input vectors remain intact.      *       * @param a the first operand.      * @param b the second operand.      * @return the sum of the two input operands.      */     @Override     public Vector<Double> add(Vector<Double> a, Vector<Double> b) {         Vector<Double> result = new Vector<>(a);          for (int i = 0; i < a.getNumberOfDimensions(); i++) {             result.set(i, result.get(i) + b.get(i));         }          return result;     } } 

net.coderodde.math.impl.RealVectorDivisible

package net.coderodde.math.impl;  import net.coderodde.math.Divisible;  /**  * This class implements the division of {@code double} values.  *   * @author Rodion  "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ public final class RealVectorDivisible          implements Divisible<Double, Double, Double> {      /**      * Returns the fraction of {@code divident} and {@code divisor}.      *       * @param divident the divident {@code double} value.      * @param divisor  the divisor {@code double} value.      * @return the fraction.      */     @Override     public Double divide(Double divident, Double divisor) {         return divident / divisor;     } } 

net.coderodde.math.impl.RealVectorInnerProduct

package net.coderodde.math.impl;  import net.coderodde.math.InnerProduct; import net.coderodde.math.Vector;  /**  * This class is responsible for computing inner products over real-valued   * vectors.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ public final class RealVectorInnerProduct          implements InnerProduct<Double, Double, Double> {      /**      * Computes and returns the inner product of the vectors {@code a} and       * {@code b}.      *       * @param a the left operand vector.      * @param b the right operand vector.      * @return the inner product of the vectors {@code a} and {@code b}.      */     @Override     public Double innerProductOf(Vector<Double> a, Vector<Double> b) {         double innerProduct = 0.0;          for (int i = 0; i < a.getNumberOfDimensions(); i++) {             innerProduct += a.get(i) * b.get(i);         }          return innerProduct;     } } 

net.coderodde.math.impl.RealVectorNegative

package net.coderodde.math.impl;  import net.coderodde.math.Negative; import net.coderodde.math.Vector;  /**  * This class implements negation operation over real vectors.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 17, 2019)  */ public final class RealVectorNegative implements Negative<Vector<Double>,                                                           Vector<Double>> {      /**      * Negates the input {@code double} vector. The input vector remains intact.      *       * @param a the {@code double} vector to negate.      * @return the negative of {@code a}.      */     @Override     public Vector<Double> negate(Vector<Double> a) {         Vector<Double> result = new Vector<>(a);          for (int i = 0; i < result.getNumberOfDimensions(); i++) {             result.set(i, -result.get(i));         }          return result;     }  } 

net.coderodde.math.impl.RealVectorProductByScalar

package net.coderodde.math.impl;  import net.coderodde.math.Product; import net.coderodde.math.Vector;  /**  * This class implements the operation of multiplying a vector by a scalar.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (May 18, 2019)  */ public final class RealVectorProductByScalar          implements Product<Double, Vector<Double>, Vector<Double>> {      /**      * This method multiplies the input vector {@code vector} component-wise by      * the {@code double} scalar and returns the result. The input vector       * remains intact.      *       * @param scalar the scalar.      * @param vector the vector to multiply by the scalar.      * @return the input vector multiplied by the input scalar.      */     @Override     public Vector<Double> multiply(Double scalar, Vector<Double> vector) {         Vector<Double> x = new Vector<>(vector);          for (int i = 0; i < vector.getNumberOfDimensions(); i++) {             x.set(i, x.get(i) * scalar);         }          return x;     } } 

net.coderodde.math.GramSchmidtProcessTest

package net.coderodde.math;  import net.coderodde.math.impl.RealVectorAdditive; import net.coderodde.math.impl.RealVectorDivisible; import net.coderodde.math.impl.RealVectorInnerProduct; import net.coderodde.math.impl.RealVectorNegative; import net.coderodde.math.impl.RealVectorProductByScalar; import org.junit.After; import org.junit.AfterClass; import org.junit.Before; import org.junit.BeforeClass; import org.junit.Test; import static org.junit.Assert.*;  public class GramSchmidtProcessTest {      private final GramSchmidtProcess<Double, Double, Double> process =              new GramSchmidtProcess<>(new RealVectorInnerProduct(),                                      new RealVectorDivisible(),                                      new RealVectorProductByScalar(),                                      new RealVectorAdditive(),                                      new RealVectorNegative());      @Test(expected = NullPointerException.class)      public void testThrowsNullPointerExceptionOnNullBasis() {         process.process(null);     }      @Test(expected = IllegalArgumentException.class)     public void testThrowsIllegalArgumentExceptionOnNoVectors() {         process.process();     }      @Test     public void testReturnsSingleVectorWhenBasisContainsOnlyOneVector() {         Vector<Double> vec = new Vector<>(1.0, 2.2, 3.0);         Vector<Double>[] result = process.process(vec);         assertEquals(1, result.length);         assertEquals(vec, result[0]);     }      @Test(expected = IllegalArgumentException.class)      public void          testThrowsIllegalArgumentExceptionWhenFirstVectorHasDimensionZero() {         Vector<Double> v1 = new Vector<>();         Vector<Double> v2 = new Vector<>(1.0);         process.process(v1, v2);     }      @Test(expected = IllegalArgumentException.class)      public void          testThrowsIllegalArgumentExceptionWhenAnotherVectorHasDimensionZero() {         Vector<Double> v1 = new Vector<>(1.0);         Vector<Double> v2 = new Vector<>();         process.process(v1, v2);     }      @Test(expected = IllegalArgumentException.class)      public void testThrowsIllegalArgumentExceptionWhenDimensionalityMismatch() {         Vector<Double> v1 = new Vector<>(1.0);         Vector<Double> v2 = new Vector<>(2.0, 3.0);         process.process(v1, v2);     }      @Test     public void testValidInput1() {         Vector<Double> v1 = new Vector<>(1., 1., 1.);         Vector<Double> v2 = new Vector<>(1., 0., 1.);         Vector<Double> v3 = new Vector<>(3., 2., 3.);         Vector<Double>[] orthogonalBasis = process.process(v1, v2, v3);         assertTrue(Demo.basisIsOrthogonal(orthogonalBasis, 0.001));     } } 

(The entire project is here.)

Critique request

As always, please tell me anything that comes to mind!

A sufficient and necessary condition for a special linear operator to be compact


Suppose $ X$ is Banach and $ T\in B(X)$ (i.e. $ T$ is a linear and continuous map and $ T:X \to X$ ). Also, suppose $ \exists c > 0$ , s.t. $ \|Tx\| \ge c\|x\|, \forall x\in X$ . Prove $ T$ is a compact operator if and only if $ X$ is finite dimensional.

$ X$ is finite dimensional $ \implies$ $ T$ is compact” is easy to show. To prove the other side, at first, I made a mistake, thinking $ X$ is reflexive. Then this work can be easily done by the fact that any sequence of a reflexive linear space has a weakly convergent subsequence and $ T$ is completely continuous (since $ T$ is compact). But this is not the situation.

So how to prove “$ T$ is compact $ \implies X$ is finite dimensional”?

Linear programming IFF with equality constrain

Is it possible to write the following logical constrain in linear programming?

Let $ v$ be an integer variable and $ k$ an integer constant. Let $ y$ be a binary variable. The logical constrain requires:

$ y=1 \Longleftrightarrow v=k$

I need this kind of contrain in linear programming to use it in AMPL, but I really can’t find a way to write it down as a linear constrain.

Thanks to who’ll help me!

Multiple linear regression: am I interpreting the methodology right?

This is the same question as 1. Since I’ve got no satisfactory answer, I decided to post it here.

To begin with, we have the normal linear model \begin{align*} \textbf{Y} = \textbf{X}\beta + \epsilon \end{align*}

where $ \epsilon\sim\mathcal{N}(\textbf{0},\sigma^{2}\textbf{I})$ , $ \mu_{i} = \beta_{0} + \beta_{1}x_{i1} + \ldots + \beta_{p}x_{ip}$ and $ \mu = \textbf{X}\beta$ . As far as I have understood, we take $ n$ observations \begin{align*} Y_{1} & = \beta_{0} + \beta_{1}x_{11} + \ldots + \beta_{p}x_{1p} + \epsilon_{1}\ Y_{2} & = \beta_{0} + \beta_{1}x_{21} + \ldots + \beta_{p}x_{2p} + \epsilon_{2}\ &\vdots\ Y_{n} & = \beta_{0} + \beta_{1}x_{n1} + \ldots + \beta_{p}x_{np} + \epsilon_{n}\ \end{align*}

and apply the least square method, for instance, to obtain $ \hat{\beta} = (\textbf{X}^{T}\textbf{X})^{-1}\textbf{X}^{T}\textbf{Y}$ .

The problem which concerns me is the interpretation of such process. Let’s suppose, for example, that $ Y$ represents the income of each person from the target population, $ x_{1}$ indicates the gender and $ x_{2}$ stands for the correspoding age. Thus we draw someone from target population and obtain the first observation

\begin{align*} Y_{1} = \beta_{0} + \beta_{1}x_{11} + \beta_{2}x_{12} + \epsilon_{1} \end{align*}

After so, we draw another person (with or without replacement) from the target population and obtain the second observation \begin{align*} Y_{2} = \beta_{0} + \beta_{1}x_{21} + \beta_{2}x_{22} + \epsilon_{2} \end{align*}

We repeat such process until $ n$ observations are made. Once we have $ \hat{\beta}$ at hand, we can estimate $ \mu$ according to $ \hat{\mu} = \textbf{X}\hat{\beta}$ . Moreover, we can also estimate the variance $ \sigma^{2}$ from the distribution $ \textbf{Y}\sim\mathcal{N}(\textbf{X}\beta,\sigma^{2}\textbf{I})$ through the estimator \begin{align*} S^{2} = \frac{(\textbf{Y} – \textbf{X}\hat{\beta})^{T}(\textbf{Y} – \textbf{X}\hat{\beta})}{n-p-1} \end{align*}

where it is assumed that $ \text{Rank}(\textbf{X}) = p+1$ and $ \textbf{X}$ has full rank.

My first question is: am I describing the observation process rightly?

My second question is: how should we interpret the distribution $ \textbf{Y} = \mathcal{N}(\textbf{X}\beta,\sigma^{2}\textbf{I})$ ?

The second question may be confusing me because, in the context of inference, we normally assume the sample consists in independent identically distributed random variables and in the multiple linear regression problem we just assume independence. In other words, the distribution of $ \textbf{Y}$ corresponds to the distribution of the sample $ (Y_{1},Y_{2},\ldots,Y_{n})$ and the means $ \mu_{i}$ do not need to be the same. Is it correct?

Any help is appreciated. Thanks in advance!